-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort2.java
More file actions
134 lines (131 loc) · 5.78 KB
/
QuickSort2.java
File metadata and controls
134 lines (131 loc) · 5.78 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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// quickSort2.java - O(N*logN)
// Быстрая сортировка улучшенная (опорное значение выбирается из 3х, при условии, что подмассив > 3 (порог отсечения), иначе выполняется обычная сортировка)
////////////////////////////////////////////////////////////////
class ArrayIns2
{
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayIns2(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)
{
int size = right-left+1;
if(size <= 3) // manual sort if small
manualSort(left, right);
else // quicksort if large
{
long median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
} // end recQuickSort()
//--------------------------------------------------------------
public long medianOf3(int left, int right)
{
int center = (left+right)/2;
// order left & center
if( theArray[left] > theArray[center] )
swap(left, center);
// order left & right
if( theArray[left] > theArray[right] )
swap(left, right);
// order center & right
if( theArray[center] > theArray[right] )
swap(center, right);
swap(center, right-1); // put pivot on right
return theArray[right-1]; // return median value
} // end medianOf3()
//--------------------------------------------------------------
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(
//--------------------------------------------------------------
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left; // right of first elem
int rightPtr = right - 1; // left of pivot
while(true)
{
while( theArray[++leftPtr] < pivot ) // find bigger
; // (nop)
while( theArray[--rightPtr] > pivot ) // find smaller
; // (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-1); // restore pivot
return leftPtr; // return pivot location
} // end partitionIt()
//--------------------------------------------------------------
public void manualSort(int left, int right)
{
int size = right-left+1;
if(size <= 1)
return; // no sort necessary
if(size == 2)
{ // 2-sort left and right
if( theArray[left] > theArray[right] )
swap(left, right);
return;
}
else // size is 3
{ // 3-sort left, center, & right
if( theArray[left] > theArray[right-1] )
swap(left, right-1); // left, center
if( theArray[left] > theArray[right] )
swap(left, right); // left, right
if( theArray[right-1] > theArray[right] )
swap(right-1, right); // center, right
}
} // end manualSort()
//--------------------------------------------------------------
} // end class ArrayIns2
////////////////////////////////////////////////////////////////
class QuickSort2App
{
public static void main(String[] args)
{
int maxSize = 16; // array size
ArrayIns2 arr; // reference to array
arr = new ArrayIns2(maxSize); // create the 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 QuickSort2App
////////////////////////////////////////////////////////////////