Skip to content

Commit 96543a5

Browse files
vbohushvbohush
committed
add quick sort
1 parent e60138b commit 96543a5

File tree

5 files changed

+163
-14
lines changed

5 files changed

+163
-14
lines changed

‎src/net/bohush/sorting/BubbleSortPanel.java‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
public class BubbleSortPanel extends SortPanel {
77
private static final long serialVersionUID = 1L;
88
private int redColumn = -1;
9+
private int blueColumn = -1;
910
private int greenColumn = -1;
1011

1112
public BubbleSortPanel(String name, int[] list, int sleepTime) {
@@ -20,10 +21,12 @@ public void run() {
2021
needNextPass = false;
2122
for (int i = 0; i < list.length - k; i++) {
2223
redColumn = i;
24+
blueColumn = i + 1;
2325
repaint();
2426
Thread.sleep(3 * sleepTime);
2527
if (list[i] > list[i + 1]) {
26-
redColumn++;
28+
redColumn = i + 1;
29+
blueColumn = -1;
2730
int temp = list[i];
2831
list[i] = list[i + 1];
2932
list[i + 1] = temp;
@@ -36,6 +39,7 @@ public void run() {
3639
}
3740
greenColumn = 0;
3841
redColumn = -1;
42+
blueColumn = -1;
3943
} catch (InterruptedException e) {
4044
}
4145
repaint();
@@ -66,6 +70,12 @@ protected void paintComponent(Graphics g) {
6670
g.setColor(Color.BLACK);
6771
g.drawRect(2 * BORDER_WIDTH + columnWidth * redColumn, getHeight() - list[redColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[redColumn] * columnHeight);
6872
}
73+
if(blueColumn != -1) {
74+
g.setColor(Color.BLUE);
75+
g.fillRect(2 * BORDER_WIDTH + columnWidth * blueColumn, getHeight() - list[blueColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[blueColumn] * columnHeight);
76+
g.setColor(Color.BLACK);
77+
g.drawRect(2 * BORDER_WIDTH + columnWidth * blueColumn, getHeight() - list[blueColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[blueColumn] * columnHeight);
78+
}
6979
}
7080

7181
}

‎src/net/bohush/sorting/InsertionSortPanel.java‎

Lines changed: 16 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
public class InsertionSortPanel extends SortPanel {
77
private static final long serialVersionUID = 1L;
88
private int redColumn = -1;
9+
private int blueColumn = -1;
910
private int greenColumn = -1;
1011

1112
public InsertionSortPanel(String name, int[] list, int sleepTime) {
@@ -17,21 +18,26 @@ public void run() {
1718
try {
1819
for (int i = 1; i < list.length; i++) {
1920
greenColumn = i;
20-
redColumn = greenColumn;
2121
Thread.sleep(3 * sleepTime);
2222
repaint();
23+
redColumn = greenColumn;
24+
blueColumn = -1;
2325
int k;
2426
for (k = i - 1; k >= 0 && list[k] > list[k + 1]; k--) {
27+
redColumn = k + 1;
28+
blueColumn = k;
29+
repaint();
30+
Thread.sleep(4 * sleepTime);
2531
int tmp = list[k + 1];
2632
list[k + 1] = list[k];
2733
list[k] = tmp;
28-
redColumn = k;
29-
repaint();
30-
Thread.sleep(4 * sleepTime);
3134
}
35+
redColumn = k + 1;
36+
blueColumn = k;
3237
repaint();
3338
}
3439
redColumn = -1;
40+
blueColumn = -1;
3541
} catch (InterruptedException e) {
3642
}
3743
repaint();
@@ -60,6 +66,12 @@ protected void paintComponent(Graphics g) {
6066
g.setColor(Color.BLACK);
6167
g.drawRect(2 * BORDER_WIDTH + columnWidth * redColumn, getHeight() - list[redColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[redColumn] * columnHeight);
6268
}
69+
if(blueColumn != -1) {
70+
g.setColor(Color.BLUE);
71+
g.fillRect(2 * BORDER_WIDTH + columnWidth * blueColumn, getHeight() - list[blueColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[blueColumn] * columnHeight);
72+
g.setColor(Color.BLACK);
73+
g.drawRect(2 * BORDER_WIDTH + columnWidth * blueColumn, getHeight() - list[blueColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[blueColumn] * columnHeight);
74+
}
6375
}
6476

6577
}

‎src/net/bohush/sorting/Main.java‎

Lines changed: 13 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -16,19 +16,24 @@ public Main() {
1616
setLayout(new GridLayout(0, 3, 0, 0));
1717
int[] list = new int[size];
1818
for (int i = 0; i < list.length; i++) {
19-
list[i] = 1 + (int)(Math.random() * size);
19+
list[i] = i + 1;
20+
}
21+
//shuffle
22+
for (int i = 0; i < list.length; i++) {
23+
int index = (int) (Math.random() * list.length);
24+
int temp = list[i];
25+
list[i] = list[index];
26+
list[index] = temp;
2027
}
2128
sortPanels[0] = new SelectionSortPanel(" Selection Sort ", list, sleepTime);
2229
sortPanels[1] = new InsertionSortPanel(" Insertion Sort ", list, sleepTime);
2330
sortPanels[2] = new BubbleSortPanel(" Bubble Sort ", list, sleepTime);
24-
/*sortPanels[3] = new SortPanel(" Merge Sort ", list);
25-
sortPanels[4] = new SortPanel(" Quick Sort ", list);
26-
sortPanels[5] = new SortPanel(" Heap Sort ", list);*/
31+
sortPanels[3] = new QuickSortPanel(" Quick Sort ", list, sleepTime);
32+
sortPanels[4] = new InsertionSortPanel(" Insertion Sort ", list, sleepTime);
33+
sortPanels[5] = new BubbleSortPanel(" Bubble Sort ", list, sleepTime);
2734

2835
for (int i = 0; i < sortPanels.length; i++) {
29-
if(sortPanels[i] != null){
30-
add(sortPanels[i]);
31-
}
36+
add(sortPanels[i]);
3237
}
3338

3439
}
@@ -37,7 +42,7 @@ public static void main(String[] args) {
3742
JFrame frame = new JFrame("Sorting Algorithm Animations");
3843
JApplet applet = new Main();
3944
frame.add(applet);
40-
//frame.setUndecorated(true);
45+
frame.setUndecorated(true);
4146
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
4247
frame.pack();
4348
frame.setLocationRelativeTo(null);

‎src/net/bohush/sorting/QuickSortPanel.java‎

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
package net.bohush.sorting;
2+
3+
import java.awt.Color;
4+
import java.awt.Graphics;
5+
6+
public class QuickSortPanel extends SortPanel {
7+
private static final long serialVersionUID = 1L;
8+
private int redColumn = -1;
9+
private int blueColumn = -1;
10+
private int cyanColumn = -1;
11+
private int greenColumn = -1;
12+
13+
public QuickSortPanel(String name, int[] list, int sleepTime) {
14+
super(name, list, sleepTime);
15+
}
16+
17+
@Override
18+
public void run() {
19+
try {
20+
quicksort(0, list.length - 1);
21+
} catch (InterruptedException e) {
22+
}
23+
redColumn = -1;
24+
blueColumn = -1;
25+
cyanColumn = -1;
26+
greenColumn = size - 1;
27+
repaint();
28+
}
29+
30+
private void quicksort(int low, int high) throws InterruptedException {
31+
int i = low;
32+
int j = high;
33+
Thread.sleep(sleepTime);
34+
repaint();
35+
int pivot = list[low + (high - low) / 2];
36+
redColumn = low + (high - low) / 2;
37+
38+
while (i <= j) {
39+
while (list[i] < pivot) {
40+
i++;
41+
blueColumn = i;
42+
Thread.sleep(3 * sleepTime);
43+
repaint();
44+
}
45+
while (list[j] > pivot) {
46+
j--;
47+
cyanColumn = j;
48+
Thread.sleep(3 * sleepTime);
49+
repaint();
50+
}
51+
52+
if (i <= j) {
53+
int temp = list[i];
54+
list[i] = list[j];
55+
list[j] = temp;
56+
if(i == redColumn) {
57+
redColumn = j;
58+
} else if (j == redColumn) {
59+
redColumn = i;
60+
}
61+
Thread.sleep(4 * sleepTime);
62+
repaint();
63+
i++;
64+
j--;
65+
}
66+
}
67+
68+
if (low < j) {
69+
quicksort(low, j);
70+
}
71+
if (i < high) {
72+
quicksort(i, high);
73+
}
74+
if(low > greenColumn) {
75+
greenColumn = low;
76+
blueColumn = -1;
77+
cyanColumn = -1;
78+
}
79+
repaint();
80+
}
81+
82+
83+
@Override
84+
protected void paintComponent(Graphics g) {
85+
super.paintComponent(g);
86+
int columnWidth = (getWidth() - 4 * BORDER_WIDTH) / size;
87+
int columnHeight = (getHeight() - 4 * BORDER_WIDTH) / size;
88+
for (int i = (greenColumn == -1 ? 0 : greenColumn); i < list.length; i++) {
89+
g.setColor(Color.WHITE);
90+
g.fillRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
91+
g.setColor(Color.BLACK);
92+
g.drawRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
93+
}
94+
for (int i = 0; i <= greenColumn; i++) {
95+
g.setColor(Color.GREEN);
96+
g.fillRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
97+
g.setColor(Color.BLACK);
98+
g.drawRect(2 * BORDER_WIDTH + columnWidth * i, getHeight() - list[i] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[i] * columnHeight);
99+
}
100+
if(redColumn != -1) {
101+
g.setColor(Color.RED);
102+
g.fillRect(2 * BORDER_WIDTH + columnWidth * redColumn, getHeight() - list[redColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[redColumn] * columnHeight);
103+
g.setColor(Color.BLACK);
104+
g.drawRect(2 * BORDER_WIDTH + columnWidth * redColumn, getHeight() - list[redColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[redColumn] * columnHeight);
105+
}
106+
if(blueColumn != -1) {
107+
g.setColor(Color.BLUE);
108+
g.fillRect(2 * BORDER_WIDTH + columnWidth * blueColumn, getHeight() - list[blueColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[blueColumn] * columnHeight);
109+
g.setColor(Color.BLACK);
110+
g.drawRect(2 * BORDER_WIDTH + columnWidth * blueColumn, getHeight() - list[blueColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[blueColumn] * columnHeight);
111+
}
112+
if(cyanColumn != -1) {
113+
g.setColor(Color.CYAN);
114+
g.fillRect(2 * BORDER_WIDTH + columnWidth * cyanColumn, getHeight() - list[cyanColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[cyanColumn] * columnHeight);
115+
g.setColor(Color.BLACK);
116+
g.drawRect(2 * BORDER_WIDTH + columnWidth * cyanColumn, getHeight() - list[cyanColumn] * columnHeight - 2 * BORDER_WIDTH, columnWidth, list[cyanColumn] * columnHeight);
117+
}
118+
119+
120+
}
121+
122+
}

‎src/net/bohush/sorting/SortPanel.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
public abstract class SortPanel extends JPanel implements Runnable {
1212
private static final long serialVersionUID = 1L;
1313
protected static final int BORDER_WIDTH = 10;
14-
private static final Dimension PREFFERED_DIMENSION = new Dimension(540, 440);
14+
private static final Dimension PREFFERED_DIMENSION = new Dimension(640, 540);
1515
protected int size;
1616
protected int[] list;
1717
protected int sleepTime;

0 commit comments

Comments
 (0)