Repository navigation
Expand file tree
/
Copy pathQuickSort3.java
More file actions
131 lines (129 loc) · 5.79 KB
/
Copy pathQuickSort3.java
File metadata and controls
131 lines (129 loc) · 5.79 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
// quickSort3.java - O(N*logN)
// Быстрая сортировка 2-ая версия улучшения (опорное значение регулируется (Кнут советует 9), при достижении опорного значения выполняется сортировка вставкой)
////////////////////////////////////////////////////////////////
class ArrayIns3
{
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayIns3(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);
// insertionSort(0, nElems-1); // the other option
}
//--------------------------------------------------------------
public void recQuickSort(int left, int right)
{
int size = right-left+1;
if(size < 10) // insertion sort if small
insertionSort(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()
//--------------------------------------------------------------
// insertion sort
public void insertionSort(int left, int right)
{
int in, out;
// sorted on left of out
for(out=left+1; out<=right; out++)
{
long temp = theArray[out]; // remove marked item
in = out; // start shifts at out
// until one is smaller,
while(in>left && theArray[in-1] >= temp)
{
theArray[in] = theArray[in-1]; // shift item to right
--in; // go left one position
}
theArray[in] = temp; // insert marked item
} // end for
} // end insertionSort()
//--------------------------------------------------------------
} // end class ArrayIns3
////////////////////////////////////////////////////////////////
class QuickSort3App
{
public static void main(String[] args)
{
int maxSize = 16; // array size
ArrayIns3 arr; // reference to array
arr = new ArrayIns3(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 QuickSort3App
////////////////////////////////////////////////////////////////