Halving Convention
When the number of elements in a list is even, halving the list means the literal first half of the list is the first half, and the literal second half of the list is the second half. The mid (middle) element of the whole list, is the last element of the first list. This means the middle index is length / 2 – 1, as index counting begins from zero. Length is the number of elements in the list. For example, if the number of elements is 8, then the first half of the list has 4 elements and the second half of the list also has 4 elements. That is fine. Since index counting begins from 0, the middle index is 3 = 8 / 2 – 1.
What about the case, when the number of elements in the list or sub-list is odd? At the start, the length is still divided by 2. By convention, the number of elements in the first half of this division is length / 2 + 1/2. Index counting begins from zero. The middle index is given by length / 2 – 1/2. This is considered as the middle term, by convention. For example, if the number of elements in a list is 5, then the middle index is 2 = 5/2 – 1/2. And, there are three elements in the first half of the list and two elements in the second half. The middle element of the whole list is the third element at index, 2, which is the middle index because index counting begins from 0.
Division in this way is an example of integer arithmetic.
Median of Three Values
Question: What is the median of the sequence:
C B A
Solution:
Arrange the list in ascending order:
A B C
The middle term, B, is the median. It is the magnitude that lies between the other two magnitudes.
Looking for the median in a list is not that kind. For example, in a list of 19 elements unsorted, the median for the first element, middle element, and last element may be required. These three values may not be in ascending order; and so, their indexes must be taken into consideration.
With Quick Sort, the median for the whole list and sub-lists are required. The pseudocode to look for the median of three values spaced out in a list (array) is:
if arr[mid] < arr[low]
swap arr[low] with arr[mid]
if arr[high] < arr[low]
swap arr[low] with arr[high]
if arr[mid] < arr[high]
swap arr[mid] with arr[high]
pivot := arr[high]
The term “arr” means array. This code segment looks for the median and also does some sorting. This code segment looks simple, but it can be quite confusing. So, pay attention to the following explanation:
The sorting in this tutorial will produce a list where the first value is the smallest value, and the last value is the biggest value. With the alphabet, A is less than Z.
Here, the pivot is the resulting median. Low is the lowest index of the list or sub-list (not necessarily for the lowest value); high is the highest index of the list or sub-list (not necessarily for the highest value), and middle is the conventional middle index (not necessarily for the middle value of the whole list).
So, the median to be obtained is between the value of the lowest index, the value of the middle index, and the value of the highest index.
In the code, the conventional middle index is obtained first. At this start, the list is unsorted. The comparison and some rearrangement in ascending order of the three values are to take place at the same time. The first if-statement compares the value for the lowest index and that of the middle index. If that of the middle index is less than that of the lowest index, then the two values swap positions. This begins sorting and changes the arrangement of values in the list or sub-list. The second if-statement compares the value for the highest index and that of the lowest index. If that of the highest index is less than that of the lowest index, the two values swap positions. This carries on some sorting and changing of the arrangement of values in the list or sub-list. The third if-statement compares the value for the middle index and that of the highest index. If that of the highest index is less than the middle index, the two values swap positions. Some sorting or rearrangement may also occur here. This third if-condition is not like the previous two.
At the end of these three swaps, the middle value of the three values in question would be A[high], whose original content might have been changed in the code segment. For example, consider the unsorted sequence:
C B A
We already know that the median is B. However, this should be proven. The aim here is to obtain the median of these three values using the above code segment. The first if-statement compares B and C. If B is less than C, then the positions of B and C must be swapped. B is less than C, so the new arrangement becomes:
B C A
Notice, the values for the lowest index and the middle index have changed. The second if-statement compares A and B. If A is less than B, then the positions of A and B have to be swapped. A is less than B, so the new arrangement becomes:
A C B
Notice, the values for the highest index and the lowest index have changed. The third if-statement compares C and B. If C is less than B, then the positions of C and B have to be swapped. C is not less than B, so no swapping takes place. The new arrangement remains as the previous, that is:
A C B
B is the median, which is, A[high], and it is the pivot. So, the pivot is born at the extreme end of the list or sub-list.
The Swapping Function
Another feature needed by Quick Sort is the swapping function. The swapping function, exchanges the values of two variables. The pseudocode for the swapping function is:
temp := x
x := y
y := temp
Here, x and y refer to the actual values and not the copies.
The sorting in this article will produce a list where the first value is the smallest value, and the last value is the biggest value.
Article Content
Quick Sort Algorithm
The normal way to sort an unsorted list is to consider the first two values. If they are not in order, put them in order. Next, consider the first three values. Scan the first two to see where the third value fits and fit it appropriately. Then, consider the first four values. Scan the first three values to see where the fourth value fits and fit it appropriately. Continue with this procedure until the whole list is sorted.
This procedure, also known as the brute-force sort, in computer programming parlance, is too slow. The Quick Sort algorithm comes with a much faster procedure.
The steps for the quicksort algorithm is as follows:
- Make sure there are at least 2 numbers to sort in the unsorted list.
- Obtain an estimated central value for the list, called the pivot. The median, as described above, is one way of obtaining the pivot. Different ways come with their advantages and disadvantages. – See later.
- Partition the list. This means, place the pivot in the list. In such a way, all the elements on the left are less than the pivot value, and all the elements on the right are greater than or equal to the pivot value. There are different ways of partitioning. Each partition method comes with its advantages and disadvantages. Partitioning is dividing in the divide-and-conquer paradigm.
- Repeat steps 1, 2, and 3 recursively for the new sub-list pairs that emerge until the whole list is sorted. This is conquering in the divide-and-conquer paradigm.
The Quick Sort pseudocode is:
if low < high then
pivot(low, high)
p := partition(arr, low, high)
quicksort(arr, low, p - 1)
quicksort(arr, p + 1, high)
A Partition Pseudocode
The partition pseudocode used in this tutorial is:
pivot := arr[high]
i := low
j := high
do
do
++i
while (arr[i] < pivot)
do
--j
while (arr[j] > pivot)
if (i < j)
swap arr[i] with arr[j]
while (i < j)
swap arr[i] with arr[high]
return i
In the illustration of Quick Sort below, this code is used:
Illustration of Quick Sort
Consider the following unsorted list (array) of alphabetic letters:
Q W E R T Y U I O P
By inspection, the sorted list is:
E I O P Q R T U W Y
The sorted list will now be proven, using the above algorithm and pseudocode segments, from the unsorted list:
Q W E R T Y U I O P
The first pivot is determined from arr[0]=Q, arr[4]=T, and arr[9]=P, and is identified as Q and placed at the extreme right of the list. So, the list with any pivot function sorting becomes:
P W E R T Y U I O Q
The current pivot is Q. The pivot procedure did some small sorting and placed P at the first position. The resulting list has to be rearranged (partitioned), such that, all the elements on the left are smaller in value, then the pivot and all the elements on the right of the pivot, are equal to or greater than the pivot. The computer cannot do partitioning by inspection. So, it does by using the indexes and the above partition algorithm.
The low and high indexes now are 0 and 9. So, the computer will begin by scanning from the index 0 until it reaches an index, whose value is equal to or greater than the pivot and stops there temporarily. It will also scan from the high (right) end, index 9, coming down, until it reaches an index whose value is less than or equal to the pivot and stops there temporarily. This means two positions of stop. If i, the incremental index variable, from low is not yet equal to or greater than the decreasing index variable, j from high, then these two values are swapped. In the current situation, scanning from both ends stopped at W and O. So the list becomes:
P O E R T Y U I W Q
The pivot is still Q. The scanning in opposite directions continues and stops accordingly. If i is not yet equal to or greater than j, then the two values at which scanning from both ends stopped are swapped. This time, scanning from both ends stopped at R and I. So, the arrangement of the list becomes:
P O E I T Y U R W Q
The pivot is still Q. The scanning in opposite directions continues and stops accordingly. If i is not yet equal to or greater than j, then the two values at which scanning stopped, are swapped. This time, scanning from both ends stopped at T for i and I for j. i and j have met or crossed. So, there can be no swapping. The list remains the same as:
P O E I T Y U R W Q
At this point, the pivot, Q, must be placed in its final position in the sorting. This is done by swapping arr[i] with arr[high], swapping T and Q. The list becomes:
P O E I Q Y U R W T
At this point, partitioning for the whole list has ended. The pivot = Q has played its role. There are now three sub-lists, which are:
P O E I Q Y U R W T
The partition is division and conquering (sorting) in the paradigm. Q is at its correct sorting position. Every element to the left of Q is smaller than Q, and every element to the right of Q is bigger than Q. However, the left list is still not sorted; and the right list is still not sorted. The whole Quick Sort function has to be called recursively in order to sort the left sub-list and the right sub-list. This recalling of Quick Sort has to continue; new sub-lists will develop until the whole original list is completely sorted. For each recalling of the Quick Sort function, the left sub-list is attended to first before the corresponding right sub-list is attended to. A new pivot has to be obtained for each sub-list.
For the sub-list:
P O E I
The pivot (median) for P, O, and I is determined. The pivot would be O. For this sub-list, and relating to the complete list, the new arr[low] is arr[0], and the new arr[high] is the last arr[i-1] = arr[4-1] = arr[3], where i is the final pivot index from the previous partition. After the pivot() function has been called, the new pivot value, pivot = O. Do not confuse between the pivot function and the pivot value. The pivot function may do some small sorting and place the pivot at the extreme right of the sub-list. This sub-list becomes,
I P E O
With this scheme, the pivot always ends at the right end of the sub-list or list after its function call. Scanning from both ends begin from arr[0] and arr[3] until i and j meet or cross. The comparison is done with pivot = O. The first stops are at P and E. They are swapped, and the new sub-list becomes:
I E P O
Scanning from both ends continues, and the new stops are at P for i and at E for j. Now i and j have met or cross. So the sub-list remains the same as:
I E P O
Partitioning of a sub-list or list ends when the pivot has been put in its final position. So, the new values for arr[i] and arr[high] are swapped. That is, P and O are swapped. The new sub-list becomes:
I E O P
O is now at its final position for the entire list. Its role as a pivot has ended. The sub-list is currently partitioned into three more lists, which are:
I E O P
At this point, Quick Sort of the first right sub-list has to be called. However, it will not be called. Instead, it will be noted and reserved, to be called later. As the statements of the partitioning function were being executed, from the top of the function, it is the Quick Sort for the left sub-list that must be called now (after pivot() has been called). It will be called for the list:
I E
It will begin by looking for the median of I and E. Here, arr[low] = I, arr[mid] = I and arr[high] = E. So the median, pivot, should be determined by the pivot algorithm as, I. However, the above pivot pseudocode will determine the pivot as E. This error occurs here because the above pseudocode is meant for three elements and not two. In the implementation below, there is some adjustment to the code. The sub-list becomes,
E I
The pivot always ends at the right end of the sub-list or list after its function call. Scanning from both ends begin from arr[0] and arr[1] exclusive until i and j meet or cross. The comparison is done with pivot = I. The first and only stops are at I and E: at I for i and at E for j. Now i and j have met or crossed. So, the sub-list remains the same as:
E I
Partitioning of a sub-list or list ends when the pivot has been put in its final position. So, the new values for arr[i] and arr[high] are swapped. It happens here that arr[i] = I and arr[high] = I. So, the same value is swapped with itself. The new sub-list becomes:
E I
I is now at its final position for the entire list. Its role as a pivot has ended. The sub-list is now partitioned into two more lists, which are,
E I
Now, the pivots so far have been Q, O, and I. Pivots end at their final positions. A sub-list of a single element, such as the P above, also ends at its final position.
At this point, the first left sub-list has been completely sorted. And the sorting procedure is now at:
E I O P Q Y U R W T
The first right sub-list:
Y U R W T
still needs to be sorted.
Conquering the First Right Sub-List
Remember that the Quick Sort call for the first right sub-list was noted and reserved instead of being executed. At this point, it will be executed. And so, the new arr[low] = arr[5] = arr[QPivotIndex+1], and the new arr[high] remains arr[9]. A similar set of activities that happened for the first left sub-list will happen here. And this first right sub-list is sorted to:
R T U W Y
And the original unsorted list has been sorted to:
E I O P Q R T U W Y
Java Coding
Putting the algorithm in Java is just to put all the above pseudocode segments into Java methods in one class. Do not forget that there needs to be a main() method in the class that will call the quicksort() function with the unsorted array.
The pivot() Method
The Java pivot() method that returns the value, pivot, should be:
int mid = (low + high) / 2;
if (arr[mid] < arr[low])
swap (arr, low, mid);
if (arr[high] < arr[low])
swap (arr, low, high);
if ((high - low) > 2) {
if (arr[mid] < arr[high])
swap (arr, mid, high);
}
}
The swap() Method
The swap() method should be:
char temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
The quicksort() Method
The quicksort() method should be:
if (low < high) {
pivot(arr, low, high);
int p = partition(arr, low, high);
quicksort(arr, low, p - 1);
quicksort(arr, p + 1, high);
}
}
The partition() Method
The partition() method should be:
char pivot = arr[high];
int i = low;
int j = high;
do {
do
++i;
while (arr[i] < pivot);
do
--j;
while (arr[j] > pivot);
if (i < j)
swap (arr, i, j);
} while (i < j);
swap (arr, i, high);
return i;
}
The main() Method
The main() method can be:
char arr[] = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};
TheClass QuickSort = new TheClass();
QuickSort.quicksort(arr, 0, 9);
System.out.println("The Sorted Elements:");
for(int i=0; i<10; i++) {
System.out.print(arr[i]); System.out.print(' ');
}
System.out.println();
}
All the above methods can be put into one class.
Conclusion
Quick Sort is a sorting algorithm that uses the divide-and-conquer paradigm. It begins by dividing an unsorted list into two or three sub-lists. In this tutorial, Quick Sort has divided a list into three sub-lists: a left sub-list, a middle list of a single element, and a right sub-list. Conquering in Quick Sort is dividing a list or sub-list while sorting it, using a pivot value. This tutorial has explained one implementation of Quick Sort in the Java computer language.
from Linux Hint https://ift.tt/2UvWaou
0 Comments