Skip to content

Commit 6c7001f

Browse files
MusicTheoristMusicTheorist
committed
version 3.2
1 parent 466a1a7 commit 6c7001f

18 files changed

+641
-666
lines changed

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,9 @@ java -cp bin;lib/classgraph-4.8.47.jar main.ArrayVisualizer
2323
- Toggle Timo Bingmann's "end sweep" animation
2424
- Refactored / optimized code
2525

26+
## 6/4/2020 - Version 3.2
27+
_changelog coming soon_
28+
2629
## 6/3/2020 - Version 3.12
2730
- Counting Sort fixed
2831
- Optimized Bubblesort now optimized for already sorted inputs

‎dist/arrayVisualizer.jar‎

-12.5 KB
Binary file not shown.

‎src/prompts/SortPrompt.java‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -139,8 +139,7 @@ public void valueChanged(javax.swing.event.ListSelectionEvent evt) {
139139

140140
jScrollPane2.setViewportView(this.jList1);
141141

142-
//TODO: Better time estimate
143-
jButton1.setText("Run All (approx. " + (int) Math.max(Math.ceil(30 * (ArrayVisualizer.getCurrentLength() / 2048d)), 2) + " minutes)");
142+
jButton1.setText("Run All (approx. 30-60 minutes)");
144143
jButton1.addActionListener(new java.awt.event.ActionListener() {
145144
@Override
146145
public void actionPerformed(java.awt.event.ActionEvent evt) {
@@ -189,7 +188,7 @@ private void jButton1ActionPerformed() {//GEN-FIRST:event_jButton1ActionPerforme
189188
public void run(){
190189
try {
191190
RunAllSorts RunAllSorts = new RunAllSorts(ArrayVisualizer);
192-
RunAllSorts.ReportAllSorts(array, 0, 0);
191+
RunAllSorts.reportAllSorts(array);
193192
} catch (Exception e) {
194193
JErrorPane.invokeErrorMessage(e);
195194
}

‎src/sorts/BinaryGnomeSort.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ public void runSort(int[] array, int length, int bucketCount) {
3535
Highlights.markArray(3, mid);
3636
Highlights.markArray(2, hi);
3737

38-
Delays.sleep(0.05);
38+
Delays.sleep(1);
3939

4040
if (Reads.compare(num, array[mid]) < 0) { // do NOT shift equal elements past each other; this maintains stability!
4141
hi = mid;
@@ -52,7 +52,7 @@ public void runSort(int[] array, int length, int bucketCount) {
5252

5353
int j = i;
5454
while (j > lo) {
55-
Writes.swap(array, j, j - 1, 0.01, true, false);
55+
Writes.swap(array, j, j - 1, 0.05, true, false);
5656
j--;
5757
}
5858
}

‎src/sorts/IntroSort.java‎

Lines changed: 31 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
package sorts;
22

3+
import java.util.Arrays;
4+
5+
import templates.JErrorPane;
36
import templates.Sort;
47
import utils.Delays;
58
import utils.Highlights;
@@ -37,6 +40,33 @@ private static int floorLogBaseTwo(int a) {
3740
return (int) (Math.floor(Math.log(a) / Math.log(2)));
3841
}
3942

43+
// Swaps the median of arr[left], arr[mid], and arr[right] to index left.
44+
// taken from gcc source code found here: https://gcc.gnu.org/onlinedocs/gcc-4.7.2/libstdc++/api/a01462_source.html
45+
private int gccmedianof3(int[] arr, int left, int mid, int right) {
46+
if (Reads.compare(arr[left], arr[mid]) < 0) {
47+
if (Reads.compare(arr[mid], arr[right]) < 0) {
48+
Writes.swap(arr, left, mid, 1, true, false);
49+
}
50+
else if (Reads.compare(arr[left], arr[right]) < 0) {
51+
Writes.swap(arr, left, right, 1, true, false);
52+
}
53+
}
54+
else if (Reads.compare(arr[left], arr[right]) < 0) {
55+
middle = left;
56+
Highlights.markArray(3, left);
57+
return arr[left];
58+
}
59+
else if (Reads.compare(arr[mid], arr[right]) < 0) {
60+
Writes.swap(arr, left, right, 1, true, false);
61+
}
62+
else {
63+
Writes.swap(arr, left, mid, 1, true, false);
64+
}
65+
middle = left;
66+
Highlights.markArray(3, left);
67+
return arr[left];
68+
}
69+
4070
private int medianof3(int[] arr, int left, int mid, int right) {
4171
if(Reads.compare(arr[right], arr[left]) == -1) {
4272
Writes.swap(arr, left, right, 1, true, false);
@@ -95,7 +125,7 @@ private void introsortLoop (int[] a, int lo, int hi, int depthLimit) {
95125
return;
96126
}
97127
depthLimit--;
98-
int p = partition(a, lo, hi, medianof3(a, lo, lo + ((hi - lo) / 2) + 1, hi - 1));
128+
int p = partition(a, lo, hi, medianof3(a, lo, lo + ((hi - lo) / 2), hi - 1));
99129
introsortLoop(a, p, hi, depthLimit);
100130
hi = p;
101131
}

‎src/sorts/SmartCocktailSort.java‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
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+
MIT License
12+
13+
Copyright (c) 2019 w0rthy
14+
15+
Permission is hereby granted, free of charge, to any person obtaining a copy
16+
of this software and associated documentation files (the "Software"), to deal
17+
in the Software without restriction, including without limitation the rights
18+
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
19+
copies of the Software, and to permit persons to whom the Software is
20+
furnished to do so, subject to the following conditions:
21+
22+
The above copyright notice and this permission notice shall be included in all
23+
copies or substantial portions of the Software.
24+
25+
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26+
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27+
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28+
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
29+
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
30+
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
31+
SOFTWARE.
32+
*
33+
*/
34+
35+
final public class SmartCocktailSort extends Sort {
36+
public SmartCocktailSort(Delays delayOps, Highlights markOps, Reads readOps, Writes writeOps) {
37+
super(delayOps, markOps, readOps, writeOps);
38+
39+
this.setSortPromptID("Smart Cocktail");
40+
this.setRunAllID("Optimized Cocktail Shaker Sort");
41+
this.setReportSortID("Optimized Cocktail Shaker Sort");
42+
this.setCategory("Exchange Sorts");
43+
this.isComparisonBased(true);
44+
this.isBucketSort(false);
45+
this.isRadixSort(false);
46+
this.isUnreasonablySlow(false);
47+
this.setUnreasonableLimit(0);
48+
this.isBogoSort(false);
49+
}
50+
51+
private void smartCocktailShaker(int[] array, int start, int end, double sleep) {
52+
int i = start;
53+
while(i < ((end / 2) + start)) {
54+
boolean sorted = true;
55+
for(int j = i; j < end + start - i - 1; j++) {
56+
if(Reads.compare(array[j], array[j + 1]) == 1) {
57+
Writes.swap(array, j, j + 1, sleep, true, false);
58+
sorted = false;
59+
}
60+
61+
Highlights.markArray(1, j);
62+
Highlights.markArray(2, j + 1);
63+
64+
Delays.sleep(sleep / 2);
65+
}
66+
for(int j = end + start - i - 1; j > i; j--){
67+
if(Reads.compare(array[j], array[j - 1]) == -1) {
68+
Writes.swap(array, j, j - 1, sleep, true, false);
69+
sorted = false;
70+
}
71+
72+
Highlights.markArray(1, j);
73+
Highlights.markArray(2, j - 1);
74+
75+
Delays.sleep(sleep / 2);
76+
}
77+
if(sorted) break;
78+
else i++;
79+
}
80+
}
81+
82+
public void customSort(int[] array, int start, int end) {
83+
this.smartCocktailShaker(array, start, end, 1);
84+
}
85+
86+
@Override
87+
public void runSort(int[] array, int length, int bucketCount) {
88+
this.smartCocktailShaker(array, 0, length, 0.1);
89+
}
90+
}

‎src/templates/MultipleSortThread.java‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@
55
import utils.Delays;
66
import utils.Highlights;
77
import utils.Reads;
8-
import utils.Shuffles;
98
import utils.Sounds;
109
import utils.Timer;
1110
import utils.Writes;
@@ -36,7 +35,7 @@ public MultipleSortThread(ArrayVisualizer ArrayVisualizer) {
3635
this.Timer = ArrayVisualizer.getTimer();
3736
}
3837

39-
protected synchronized void RunIndividualSort(Sort sort, int bucketCount, int[] array, int length, double speed) throws InterruptedException {
38+
protected synchronized void runIndividualSort(Sort sort, int bucketCount, int[] array, int length, double speed) throws InterruptedException {
4039
Delays.setSleepRatio(2.5);
4140

4241
if(length != ArrayVisualizer.getCurrentLength()) {
@@ -58,7 +57,10 @@ protected synchronized void RunIndividualSort(Sort sort, int bucketCount, int[]
5857
this.sortNumber++;
5958
}
6059

61-
public abstract void ReportAllSorts(int[] array, int current, int total) throws Exception;
60+
protected abstract void executeSortList(int[] array) throws Exception;
61+
protected abstract void runThread(int[] array, int current, int total, boolean runAllActive) throws Exception;
62+
public abstract void reportCategorySorts(int[] array) throws Exception;
63+
public abstract void reportAllSorts(int[] array, int current, int total) throws Exception;
6264

6365
public int getSortCount() {
6466
return this.sortCount;

‎src/threads/RunAllSorts.java‎

Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,6 @@
22

33
import java.util.ArrayList;
44

5-
import javax.swing.JOptionPane;
6-
75
import main.ArrayVisualizer;
86
import templates.JErrorPane;
97
import templates.MultipleSortThread;
@@ -34,12 +32,13 @@ of this software and associated documentation files (the "Software"), to deal
3432
*
3533
*/
3634

37-
final public class RunAllSorts extends MultipleSortThread {
35+
final public class RunAllSorts {
36+
private ArrayVisualizer ArrayVisualizer;
3837
private ArrayList<MultipleSortThread> allSortThreads;
3938

4039
public RunAllSorts(ArrayVisualizer ArrayVisualizer) {
41-
super(ArrayVisualizer);
42-
this.allSortThreads = new ArrayList<MultipleSortThread>();
40+
this.ArrayVisualizer = ArrayVisualizer;
41+
this.allSortThreads = new ArrayList<>();
4342
this.allSortThreads.add(new RunExchangeSorts(ArrayVisualizer));
4443
this.allSortThreads.add(new RunSelectionSorts(ArrayVisualizer));
4544
this.allSortThreads.add(new RunInsertionSorts(ArrayVisualizer));
@@ -51,8 +50,7 @@ public RunAllSorts(ArrayVisualizer ArrayVisualizer) {
5150
this.allSortThreads.add(new RunImpracticalSorts(ArrayVisualizer));
5251
}
5352

54-
@Override
55-
public void ReportAllSorts(int[] array, int current, int total) throws Exception {
53+
public void reportAllSorts(int[] array) throws Exception {
5654
int totalSortCount = 0;
5755
for(MultipleSortThread category : this.allSortThreads) {
5856
totalSortCount += category.getSortCount();
@@ -61,7 +59,7 @@ public void ReportAllSorts(int[] array, int current, int total) throws Exception
6159
try {
6260
int currentSort = 1;
6361
for(MultipleSortThread thread : this.allSortThreads) {
64-
thread.ReportAllSorts(array, currentSort, totalSortCount);
62+
thread.reportAllSorts(array, currentSort, totalSortCount);
6563
this.ArrayVisualizer.getSortingThread().join();
6664
currentSort += thread.getCategoryCount();
6765
}

‎src/threads/RunComparisonSort.java‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package threads;
22

3-
import java.io.PrintWriter;
4-
import java.io.StringWriter;
53
import java.lang.reflect.Constructor;
64

75
import javax.swing.JOptionPane;

0 commit comments

Comments
 (0)