Skip to content

Commit 1df1839

Browse files
MusicTheoristMusicTheorist
authored
Merge pull request MusicTheorist#6 from landfillbaby/master
flipped min heap sort
2 parents 738a3df + 990c7cf commit 1df1839

File tree

2 files changed

+69
-0
lines changed

2 files changed

+69
-0
lines changed

‎src/sorts/FlippedMinHeapSort.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package sorts;
2+
3+
import templates.Sort;
4+
import utils.Delays;
5+
import utils.Highlights;
6+
import utils.Reads;
7+
import utils.Writes;
8+
9+
/*
10+
*
11+
Copyright (c) rosettacode.org.
12+
Permission is granted to copy, distribute and/or modify this document
13+
under the terms of the GNU Free Documentation License, Version 1.2
14+
or any later version published by the Free Software Foundation;
15+
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
16+
Texts. A copy of the license is included in the section entitled "GNU
17+
Free Documentation License".
18+
*
19+
*/
20+
21+
/*
22+
modified by Lucy Phipps from ../templates/HeapSorting.java and MinHeapSort.java
23+
the only real changes are subtracting every array access from (length - 1)
24+
and removing the Writes.reverse() at the end
25+
the rest is just compacting tbe code a bit
26+
*/
27+
28+
final public class FlippedMinHeapSort extends Sort {
29+
public FlippedMinHeapSort(Delays delayOps, Highlights markOps, Reads readOps, Writes writeOps) {
30+
super(delayOps, markOps, readOps, writeOps);
31+
this.setSortPromptID("Flipped Min Heap");
32+
this.setRunAllID("Flipped Min Heap Sort");
33+
this.setReportSortID("Flipped Reverse Heapsort");
34+
this.setCategory("Selection Sorts");
35+
this.isComparisonBased(true);
36+
this.isBucketSort(false);
37+
this.isRadixSort(false);
38+
this.isUnreasonablySlow(false);
39+
this.setUnreasonableLimit(0);
40+
this.isBogoSort(false);
41+
}
42+
private void siftDown(int[] array, int length, int root, int dist) {
43+
while (root <= dist / 2) {
44+
int leaf = 2 * root;
45+
if (leaf < dist && Reads.compare(array[length - leaf], array[length - leaf - 1]) == 1) {
46+
leaf++;
47+
}
48+
if (Reads.compare(array[length - root], array[length - leaf]) == 1) {
49+
Writes.swap(array, length - root, length - leaf, 1, true, false);
50+
root = leaf;
51+
} else break;
52+
}
53+
}
54+
@Override
55+
public void runSort(int[] array, int length, int bucketCount) {
56+
for (int i = length / 2; i >= 1; i--) {
57+
siftDown(array, length, i, length);
58+
}
59+
for (int i = length; i > 1; i--) {
60+
Writes.swap(array, length - 1, length - i, 1, true, false);
61+
siftDown(array, length, 1, i - 1);
62+
}
63+
}
64+
}

‎src/threads/RunSelectionSorts.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import sorts.DoubleSelectionSort;
66
import sorts.MaxHeapSort;
77
import sorts.MinHeapSort;
8+
import sorts.FlippedMinHeapSort;
89
import sorts.PoplarHeapSort;
910
import sorts.SelectionSort;
1011
import sorts.SmoothSort;
@@ -62,6 +63,7 @@ public void run() {
6263
Sort CycleSort = new CycleSort(Delays, Highlights, Reads, Writes);
6364
Sort MaxHeapSort = new MaxHeapSort(Delays, Highlights, Reads, Writes);
6465
Sort MinHeapSort = new MinHeapSort(Delays, Highlights, Reads, Writes);
66+
Sort FlippedMinHeapSort = new FlippedMinHeapSort(Delays, Highlights, Reads, Writes);
6567
Sort WeakHeapSort = new WeakHeapSort(Delays, Highlights, Reads, Writes);
6668
Sort TernaryHeapSort = new TernaryHeapSort(Delays, Highlights, Reads, Writes);
6769
Sort SmoothSort = new SmoothSort(Delays, Highlights, Reads, Writes);
@@ -79,6 +81,7 @@ public void run() {
7981
RunSelectionSorts.this.RunIndividualSort(CycleSort, 0, array, 128, 0.01);
8082
RunSelectionSorts.this.RunIndividualSort(MaxHeapSort, 0, array, 2048, 1.5);
8183
RunSelectionSorts.this.RunIndividualSort(MinHeapSort, 0, array, 2048, 1.5);
84+
RunSelectionSorts.this.RunIndividualSort(FlippedMinHeapSort, 0, array, 2048, 1.5);
8285
RunSelectionSorts.this.RunIndividualSort(WeakHeapSort, 0, array, 2048, 1);
8386
RunSelectionSorts.this.RunIndividualSort(TernaryHeapSort, 0, array, 2048, 1);
8487
RunSelectionSorts.this.RunIndividualSort(SmoothSort, 0, array, 2048, 1.5);
@@ -116,6 +119,7 @@ public void run() {
116119
Sort CycleSort = new CycleSort(Delays, Highlights, Reads, Writes);
117120
Sort MaxHeapSort = new MaxHeapSort(Delays, Highlights, Reads, Writes);
118121
Sort MinHeapSort = new MinHeapSort(Delays, Highlights, Reads, Writes);
122+
Sort FlippedMinHeapSort = new FlippedMinHeapSort(Delays, Highlights, Reads, Writes);
119123
Sort WeakHeapSort = new WeakHeapSort(Delays, Highlights, Reads, Writes);
120124
Sort TernaryHeapSort = new TernaryHeapSort(Delays, Highlights, Reads, Writes);
121125
Sort SmoothSort = new SmoothSort(Delays, Highlights, Reads, Writes);
@@ -134,6 +138,7 @@ public void run() {
134138
RunSelectionSorts.this.RunIndividualSort(CycleSort, 0, array, 128, 0.01);
135139
RunSelectionSorts.this.RunIndividualSort(MaxHeapSort, 0, array, 2048, 1.5);
136140
RunSelectionSorts.this.RunIndividualSort(MinHeapSort, 0, array, 2048, 1.5);
141+
RunSelectionSorts.this.RunIndividualSort(FlippedMinHeapSort, 0, array, 2048, 1.5);
137142
RunSelectionSorts.this.RunIndividualSort(WeakHeapSort, 0, array, 2048, 1);
138143
RunSelectionSorts.this.RunIndividualSort(TernaryHeapSort, 0, array, 2048, 1);
139144
RunSelectionSorts.this.RunIndividualSort(SmoothSort, 0, array, 2048, 1.5);

0 commit comments

Comments
 (0)