QUICK SORT ALGORITHM IN C AND C++
If you want to learn another sorting algorithm, visit the webpage: Sorting arrays
|
The sorting algorithm that proved to be the fastest. It consists of a recursive repetition of the separation of the elements of an array around some value that has been adopted as "middle value". This element is called PIVOT and there is few different ways to choosing it. In this text, the last element of subarray in the current iteration is choosed for PIVOT. If e.g. performs sorting of the array in ascending order, passing through the array, from left to right, separates so after the end of the iteration on the left side of PIVOT there are values which are less than or equal to PIVOT, and on the right are larger values. The process is repeated until all elements up to PIVOT are examined. In the end, PIVOT will be puting in the right place, ie. in place after the elements arranged on the left, those whose values were less than PIVOT.
Let's we consider e.g. the following unsorted array: |
VIDEO: Quick-sort, algorithm |
Figure 1: Quick sort in C. Initial array
For PIVOT, the element at the end of the array was adopted, ie. at position 9, whose value is 14. Orange frame indicate the current element of the array whose value we compare with PIVOT. The figure above shows the situation in the second cycle. This value is compared to the pivot and if it is smaller, it is replaced with an element framed by a dashed red line. The red box actually shows the first next position to the right of the last replaced element. On the left side on the all positions elements must be smaller than PIVOT, in this case less than 14.
So, if there is a replacement of the current element (orange) and the element (red), the position for the next possible replacement is moved one place to the right. If the current element is less than the pivot, there is no replacement, but the next element to the right is taken, ie the orange frame is moved. In the first cycle, the number 25 was compared with 14, considering that it is already there, there was no replacement. In the second cycle, which is shown in the previous picture, the number 13 is compared with PIVOT, and since it is smaller, the numbers 13 and 25 will be replaced, that is. numbers in positions 0 and 1 (see next picture).
Figure 2: Quick sort. Replacement of elements
Element 13 is then located at the beginning of the array, and the next position for eventual replacement is to the right at position no. 1. In the next cycle, the number 10 is compared with 14 (PIVOT), and then -2. Both of these values are less than 14, so they will also be replaced and located on the left side of the position for next replacement, which is now moved to position 3 (Red rectangle in Figure 3). The next member of the array, 16 is greater than 14 so just it is moved on to the next element in position 5, see Figure 3:
Figure 3: Quick sort. Moving to next position
At the end of the observed iteration, when all elements of the array to the left of PIVOT compared, the PIVOT is placed in the appropriate place to the right of all moved members on the left. This position is marked with a red rectangle, see Figure 4:
Figure 4: Quick sort. Moving PIVOT
The code that performs the separations shown above is shown using the function shown below:
C, C++
/*A method that separates the elements of an array. The array is passed to the method as a parameter a [] . The first left position of the observed array(subarray) "l" and the last right position "r" also are passed.*/
void elementSeparation(int a[ ], int l,int r)
{
void elementSeparation(int a[ ], int l,int r)
{
int p = a[ r ];// Pivot is element at last position
int i, j;
i=l-1;
for(j=l; j<=r-1; j++)
{
}int i, j;
i=l-1;
for(j=l; j<=r-1; j++)
{
if(a[j] < p)
{
}{
if(i != j)
{
}{
swap(&a[i+1],&a[j]);
i++;
}i++;
The position that is represented in the figure by a red rectangle, ie. the position of the last moved element is represented in the code by the letter "i". On the other hand, the position of the current element of the array being compared to PIVOT is denoted by "j". So, the red rectangle in the figures is in the "i + 1" position.
It is passed through all elements of the array from the initial "l" to the end of "r", the position in the current iteration. This is done with the loop. After that it is check to see if the current element is greather than the pivot, using the if command inside the loop. If the condition is true, the position "i" will be replaced and moved by one place, but in the opposite, value of "i" will be same, only the position "j" is increment, in order the next element of the array will be taken for consideration.
At the end, the PIVOT is moved to the "i + 1" position and this value is returned from the functions.
It is passed through all elements of the array from the initial "l" to the end of "r", the position in the current iteration. This is done with the loop. After that it is check to see if the current element is greather than the pivot, using the if command inside the loop. If the condition is true, the position "i" will be replaced and moved by one place, but in the opposite, value of "i" will be same, only the position "j" is increment, in order the next element of the array will be taken for consideration.
At the end, the PIVOT is moved to the "i + 1" position and this value is returned from the functions.
|
When the iteration has finished, the pivot is at position
pi = i + 1 and divides array to the left (l, pi) and right part (pi + 1, d). It should be noted that on the left side all the elements are less than the pivot, and on the right greater , see Figure 5. The procedure is further repeated by calling the same function "elementSeparation( )" once with the passed values (l, pi), and the second time with the parameters of the start and end position (pi + 1, d). |
Figure 5: Quick sort. Array sharing using PIVOT
|
Recursive function:
C,C++
/* A method that initiates recursive sorting of the initial array. */
void quickSort(int a[ ], int l,int d)
{
void quickSort(int a[ ], int l,int d)
{
if(l >= d)
{
int pi=elementSeparation(a,l,d);
printf("Pivot %d is on the position %d\n",a[pi],pi);
quickSort( a,l,pi-1);
printArray(a,n);
quickSort( a,pi+1,d);
}{
return;
}int pi=elementSeparation(a,l,d);
printf("Pivot %d is on the position %d\n",a[pi],pi);
quickSort( a,l,pi-1);
printArray(a,n);
quickSort( a,pi+1,d);
|
Recursion will be finish when the start and end positions of the subarray will be same, in other words,while the condition wont be satisfy ( l> = d). In the example shown, the final iteration of the left part of the array (Figure 5) ends when if array size will be one 1, as shown in Figure 6.
Figure 6: Quick sort. Final iteration of the left part of the array
|
Figure 7: Quick-sort. The last iteration of the right part of the array
At the end of the sorting of the right part, the complete array was sorted. The main method is shown below, as well as an auxiliary method for replacing as well as for printing array elements
|
C
#include < stdio.h > void printArray(int a[ ], int n){
for(int i = 0; i < n; i++)
}
printf("%d ",a[ i ]);
printf("\n");void swap(int *a, int* b){
int temp=(*a);
}(*a)=(*b); (*b)=temp; int main() {
int n;
}int A[ ] = { 24, 18, 38,43,14,40,1,54}; n = sizeof(a) / sizeof(a[ 0 ]); quickSort( a,0,n-1); printArray(a, n); return 0; |
C++
#include < iostream > using namespace std; void printArray(int a[ ], int n){
for(int i = 0; i < n; i++)
}
cin << a[ i ] << endl;
cin << endl;void swap(int *a, int* b){
int temp=(*a);
}(*a)=(*b); (*b)=temp; int main() {
int n;
}int A[ ] = { 24, 18, 38,43,14,40,1,54}; n = sizeof(a) / sizeof(a[ 0 ]); quickSort( a,0,n-1); printArray(a, n); return 0; |
The complete code is shown below with added "printf" commands for debugging:
C
#include < stdio.h > #include < stdlib.h > /*The method for printing an array*/ void printArray(int a[ ], int n){
for(int i = 0; i < n; i++)
}
printf("%d ",a[ i ]);
printf("\n");/*The method for swaping the two elements of an array*/ void swap(int *a, int* b){
int temp=(*a);
}(*a)=(*b); (*b)=temp; /*A method that separates the elements of an array. The array is passed to the method as a parameter a [] . The first left position of the observed array(subarray) "l" and the last right position "r" also are passed.*/ void elementSeparation(int a[ ], int l,int r) {
int p = a[ r ];// Pivot is element at last position
}int i, j; i=l-1; for(j=l; j<=r-1; j++) {
if(a[j] < p)
}{
if(i != j)
}{
swap(&a[i+1],&a[j]);
}printf("TRUE,i=%d, j=%d; i++, j++, swap %3d width %3d\n",i,(j+1),a[i],a[j]); i++; else {
printf("FALSE,i=%d, j=%d; j++, isn't swap anything\n",i,(j+1));
}/* A method that initiates recursive sorting of the initial array. */ void quickSort(int a[ ], int l,int d,int n) {
if(l >= d)
}{
return;
}int pi=elementSeparation(a,l,d); printf("Pivot %d is on the position %d\n",a[pi],pi); quickSort( a,l,pi-1,n); printArray(a,n); quickSort( a,pi+1,d,n); int main() {
int n;
}int A[ ] = { 24, 18, 38,43,14,40,1,54}; n = sizeof(A) / sizeof(A[ 0 ]); quickSort( A,0,n-1,n); printArray(a, n); return 0; |
C++
#include < iostream > using namespace std; /*The method for printing an array*/ void printArray(int a[ ], int n){
for(int i = 0; i < n; i++)
}
cin << a[ i ] << endl;
cin << endl;/*The method for swaping the two elements of an array*/ void swap(int *a, int* b){
int temp=(*a);
}(*a)=(*b); (*b)=temp; /*A method that separates the elements of an array. The array is passed to the method as a parameter a [] . The first left position of the observed array(subarray) "l" and the last right position "r" also are passed.*/ void elementSeparation(int a[ ], int l,int r) {
int p = a[ r ];// Pivot is element at last position
}int i, j; i=l-1; for(j=l; j<=r-1; j++) {
if(a[j] < p)
}{
if(i != j)
}{
swap(&a[i+1],&a[j]);
}printf("TRUE,i=%d, j=%d; i++, j++, swap %3d width %3d\n",i,(j+1),a[i],a[j]); i++; else {
printf("FALSE,i=%d, j=%d; j++, isn't swap anything\n",i,(j+1));
}/* A method that initiates recursive sorting of the initial array. */ void quickSort(int a[ ], int l,int d,int n) {
if(l >= d)
}{
return;
}int pi=elementSeparation(a,l,d); printf("Pivot %d is on the position %d\n",a[pi],pi); quickSort( a,l,pi-1,n); printArray(a,n); quickSort( a,pi+1,d,n); int main() {
int n;
}int A[ ] = { 24, 18, 38,43,14,40,1,54}; n = sizeof(A) / sizeof(A[ 0 ]); quickSort( A,0,n-1,n); printArray(a, n); return 0; |
After starting this application in console:
Figure 7: Quick Sort Application Execution
|
Previous
|< Merge-Sort |
Next
Binary search >| |