-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort1.java
More file actions
97 lines (87 loc) · 4.12 KB
/
QuickSort1.java
File metadata and controls
97 lines (87 loc) · 4.12 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// quickSort1.java - O(N*logN)
// Быстрая сортировка простая (опорное значение справа)
////////////////////////////////////////////////////////////////
class ArrayIns1 {
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayIns1(int max) // constructor
{
theArray = new long[max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
public void insert(long value) // put element into array
{
theArray[nElems] = value; // insert it
nElems++; // increment size
}
//--------------------------------------------------------------
public void display() // displays array contents
{
System.out.print("A=");
for (int j = 0; j < nElems; j++) // for each element,
System.out.print(theArray[j] + " "); // display it
System.out.println("");
}
//--------------------------------------------------------------
public void quickSort() {
recQuickSort(0, nElems - 1);
}
//--------------------------------------------------------------
public void recQuickSort(int left, int right) {
if (right - left <= 0) // if size <= 1,
return; // already sorted
else // size is 2 or larger
{
long pivot = theArray[right]; // rightmost item
// partition range
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition - 1); // sort left side
recQuickSort(partition + 1, right); // sort right side
}
} // end recQuickSort()
//--------------------------------------------------------------
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1; // left (after ++)
int rightPtr = right; // right-1 (after --)
while (true) { // find bigger item
while (theArray[++leftPtr] < pivot)
; // (nop)
// find smaller item
while (rightPtr > 0 && theArray[--rightPtr] > pivot)
; // (nop)
if (leftPtr >= rightPtr) // if pointers cross,
break; // partition done
else // not crossed, so
swap(leftPtr, rightPtr); // swap elements
} // end while(true)
swap(leftPtr, right); // restore pivot
return leftPtr; // return pivot location
} // end partitionIt()
//--------------------------------------------------------------
public void swap(int dex1, int dex2) // swap two elements
{
long temp = theArray[dex1]; // A into temp
theArray[dex1] = theArray[dex2]; // B into A
theArray[dex2] = temp; // temp into B
} // end swap(
//--------------------------------------------------------------
} // end class ArrayIns
////////////////////////////////////////////////////////////////
class QuickSort1App {
public static void main(String[] args) {
int maxSize = 16; // array size
ArrayIns1 arr;
arr = new ArrayIns1(maxSize); // create array
for (int j = 0; j < maxSize; j++) // fill array with
{ // random numbers
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
arr.display(); // display items
arr.quickSort(); // quicksort them
arr.display(); // display them again
} // end main()
} // end class QuickSort1App
////////////////////////////////////////////////////////////////