Skip to content

Commit 47cc926

Browse files
DRMPNDRMPN
committed
added quicksort
1 parent aee7594 commit 47cc926

3 files changed

Lines changed: 157 additions & 14 deletions

File tree

‎IntensiveCourse/Lesson1/Main.java‎

Lines changed: 50 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,25 +1,26 @@
11
package IntensiveCourse.Lesson1;
22

33
import java.util.ArrayList;
4+
import java.util.Comparator;
45

56
public class Main {
6-
7+
78
public static void main(String[] args) {
89

910
System.out.println("START");
10-
11+
1112
MyArrayList<Integer> list = new MyArrayList<Integer>();
12-
13+
1314
for (int i = 0; i < 5; i++) {
1415
list.add(i);
1516
}
16-
17+
1718
// add test
1819
System.out.println(list.size() == 5);
1920
System.out.println(list.get(4) == 4);
20-
21+
2122
// add at index test
22-
list.add(4,777);
23+
list.add(4, 777);
2324
System.out.println(list.size() == 6);
2425
System.out.println(list.get(4) == 777);
2526

@@ -36,7 +37,7 @@ public static void main(String[] args) {
3637
System.out.println(list.size() == 5);
3738

3839
// remove object that exist test
39-
list.add(2,777);
40+
list.add(2, 777);
4041
System.out.println(list.remove((Object) 777));
4142
System.out.println(list.get(2) == 2);
4243
System.out.println(list.size() == 5);
@@ -46,6 +47,48 @@ public static void main(String[] args) {
4647
System.out.println(list.get(2) == 2);
4748
System.out.println(list.size() == 5);
4849

50+
// sort integer
51+
list.clear();
52+
list.sort();
53+
54+
for (int i = 0; i < 8; i++) {
55+
list.add(8 - i);
56+
}
57+
58+
for (int i = 0; i < 8; i++) {
59+
System.out.print(list.get(i));
60+
}
61+
System.out.println();
62+
63+
list.sort();
64+
65+
for (int i = 0; i < 8; i++) {
66+
System.out.print(list.get(i));
67+
}
68+
System.out.println();
69+
70+
// sort string
71+
MyArrayList<String> foo = new MyArrayList<String>();
72+
foo.add("e");
73+
foo.add("b");
74+
foo.add("g");
75+
foo.add("c");
76+
foo.add("d");
77+
foo.add("f");
78+
foo.add("a");
79+
80+
for (int i = 0; i < 7; i++) {
81+
System.out.print(foo.get(i));
82+
}
83+
System.out.println();
84+
85+
foo.sort();
86+
87+
for (int i = 0; i < 7; i++) {
88+
System.out.print(foo.get(i));
89+
}
90+
System.out.println();
91+
4992
System.out.println("DONE");
5093
}
5194
}

‎IntensiveCourse/Lesson1/MyArrayList.java‎

Lines changed: 28 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package IntensiveCourse.Lesson1;
22

33
import java.util.Collection;
4+
import java.util.Comparator;
45
import java.util.Iterator;
56
import java.util.List;
67
import java.util.ListIterator;
@@ -11,7 +12,7 @@
1112
* @author DRMPN
1213
*
1314
*/
14-
public class MyArrayList<E>{
15+
public class MyArrayList<E> implements List<E> {
1516

1617
private int size = 0;
1718
private Object[] elementData;
@@ -56,7 +57,7 @@ public boolean add(E element) {
5657
/**
5758
* Inserts the given element to the given index of this list.
5859
*
59-
* @param index - index of the element to add
60+
* @param index - index of the element to add
6061
* @param element - element to be appended to this list
6162
*/
6263
public void add(int index, E element) {
@@ -92,11 +93,13 @@ public E get(int index) {
9293
}
9394

9495
/**
95-
* Returns the index of the first occurrence of the specified element in this list,
96+
* Returns the index of the first occurrence of the specified element in this
97+
* list,
9698
* or -1 if this list does not contain the element.
9799
*
98100
* @param o - element to search for
99-
* @return the index of the first occurrence of the specified element in this list,
101+
* @return the index of the first occurrence of the specified element in this
102+
* list,
100103
* or -1 if this list does not contain the element
101104
*/
102105
public int indexOf(Object o) {
@@ -138,7 +141,8 @@ public E remove(int index) {
138141
}
139142

140143
/**
141-
* Removes the first occurrence of the specified element from this list, if it is present.
144+
* Removes the first occurrence of the specified element from this list, if it
145+
* is present.
142146
* If this list does not contain the element, it is unchanged.
143147
* Returns true if this list contained the specified element.
144148
*
@@ -155,9 +159,10 @@ public boolean remove(Object o) {
155159
}
156160

157161
/**
158-
* Replaces the element at the specified position in this list with the specified element.
162+
* Replaces the element at the specified position in this list with the
163+
* specified element.
159164
*
160-
* @param index - index of the element to replace
165+
* @param index - index of the element to replace
161166
* @param element - element to be stored at the specified position
162167
* @return the element previously at the specified position
163168
*/
@@ -179,6 +184,22 @@ public int size() {
179184
return size;
180185
}
181186

187+
/**
188+
* Sorts this list.
189+
*/
190+
public void sort() {
191+
Sort.quicksort(elementData, 0, size - 1);
192+
}
193+
194+
/**
195+
* Sorts his list using comparator.
196+
*
197+
* @param c - comparator
198+
*/
199+
public void sort(Comparator<? super E> c) {
200+
Sort.quicksort(elementData, 0, size - 1, c);
201+
}
202+
182203
private boolean ensureCapacity(int currentSize) {
183204
return currentSize + 1 == elementData.length;
184205
}

‎IntensiveCourse/Lesson1/Sort.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package IntensiveCourse.Lesson1;
2+
3+
import java.util.Comparator;
4+
5+
public class Sort {
6+
7+
/**
8+
* Recursively sorts a given list with a middle elements as
9+
* the Pivot from and to a given index.
10+
*
11+
* @param array - array to sort
12+
* @param fromIndex - first index of which to sort
13+
* @param toIndex - last index of which to sort
14+
*/
15+
public static <E> void quicksort(E[] array, int fromIndex, int toIndex) {
16+
if (fromIndex >= toIndex)
17+
return;
18+
19+
int left = fromIndex, right = toIndex;
20+
E pivot = array[(fromIndex + toIndex) / 2];
21+
22+
while (left <= right) {
23+
while (((Comparable) array[left]).compareTo(pivot) < 0)
24+
left++;
25+
while (((Comparable) array[right]).compareTo(pivot) > 0)
26+
right--;
27+
28+
if (left > right)
29+
break;
30+
31+
swap(left, right, array);
32+
left++;
33+
right--;
34+
}
35+
36+
quicksort(array, fromIndex, right);
37+
quicksort(array, left, toIndex);
38+
}
39+
40+
/**
41+
* Recursively sorts given list by a given comparator with a middle
42+
* elements as the Pivot from and to a given index.
43+
*
44+
* @param array - array to sort
45+
* @param fromIndex - first index of which to sort
46+
* @param toIndex - last index of which to sort
47+
*/
48+
public static <E> void quicksort(E[] array, int fromIndex, int toIndex, Comparator<E> c) {
49+
if (fromIndex >= toIndex)
50+
return;
51+
52+
int left = fromIndex, right = toIndex;
53+
E pivot = array[(fromIndex + toIndex) / 2];
54+
55+
while (left <= right) {
56+
while (c.compare(array[left], pivot) < 0)
57+
left++;
58+
while (c.compare(array[right], pivot) > 0)
59+
right--;
60+
61+
if (left > right)
62+
break;
63+
64+
swap(left, right, array);
65+
left++;
66+
right--;
67+
}
68+
69+
quicksort(array, fromIndex, right);
70+
quicksort(array, left, toIndex);
71+
}
72+
73+
private static <E> void swap(int i, int j, E[] array) {
74+
E temp = (E) array[i];
75+
array[i] = array[j];
76+
array[j] = temp;
77+
}
78+
79+
}

0 commit comments

Comments
 (0)