Oct 10th, 2013 at 01:07 PM

Quick sort algorithm in C

Quick sort As one of the more advanced sorting algorithms, you might think that the Quicksort Algorithm is steeped in complicated theoretical background, but this is not so. Like Insertion Sort, this algorithm has a fairly simple concept at the core, but is made complicated by the constraints of the array structure. The basic concept is to pick one of the elements in the array as a pivot value around which the other elements will be rearranged. Everything less than the pivot is moved left of the pivot (into the left partition). Similarly, everything greater than the pivot goes into the right partition. At this point each partition is recursively quicksorted. The Quicksort algorithm is fastest when the median of the array is chosen as the pivot value. That is because the resulting partitions are of very similar size. Each partition splits itself in two and thus the base case is reached very quickly. In practice, the Quicksort algorithm becomes very slow when the array passed to it is already close to being sorted. Because there is no efficient way for the computer to find the median element to use as the pivot, the first element of the array is used as the pivot. So when the array is almost sorted, Quicksort doesn't partition it equally. Instead, the partitions are lopsided like in Figure 2. This means that one of the recursion branches is much deeper than the other, and causes execution time to go up. Thus, it is said that the more random the arrangement of the array, the faster the Quicksort Algorithm finishes. Quick sort is a divide and conquer algorithm. Its divided large list in mainly three parts: 1. Elements less than pivot element. 2. Pivot element. 3. Elements greater than pivot element. Where pivot as middle element of large list. Let’s understand through example: List : 3 7 8 5 2 1 9 5 4 In above list assume 4 is pivot element so rewrite list as: 3 1 2 4 5 8 9 5 7 Here, I want to say that we set the pivot element(4) which has in left side elements are less than and right hand side elements are greater than. Now you think, how’s arrange the less than and greater than elements? Be patient, you get answer soon. Now let’s start understand the concept of quick sort. The steps are: 1. Pick a pivot element. 2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. 3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion are lists of size zero or one, which never need to be sorted These are the steps taken to sort an array using QuickSort: Elements in red indicate swaps. Elements in blue indicate comparisons. Special commentary is in green. 3 1 4 5 9 2 6 8 7 Calling quickSort on elements 0 to 8 Definitions: a "small" element is one whose value is less than or equal to the value of the pivot. Likewise, a "large" element is one whose value is larger than that of the pivot. At the beginning, the entire array is passed into the quicksort function and is essentially treated as one large partition. At this time, two indices are initialized: the left-to-right search index, i, and the right-to-left search index, k. The value of i is the index of the first element in the partition, in this case 0, and the value of k is 8, the index of the last element in the partition. The relevance of these variables will be made apparent in the code below. 3 1 4 5 9 2 6 8 7 The first element in the partition, 3, is chosen as the pivot element, around which two subpartitions will be created. The end goal is to have all the small elements at the front of the partition, in no particular order, followed by the pivot, followed by the large elements. To do this, quicksort will scan rightwards for the first large element. Once this is found, it will look for the first small element from the right. These two will then be swapped. Since i is currently set to zero, the pivot is actually compared to itself in the search of the first large element. 3 1 4 5 9 2 6 8 7 The search for the first large element continues rightwards. The value of i gets incremented as the search moves to the right. 3 1 4 5 9 2 6 8 7 Since 4 is greater than the pivot, the rightwards search stops here. Thus the value of i remains 2. 3 1 4 5 9 2 6 8 7 Now, starting from the right end of the array, quicksort searches for the first small element. And so k is decremented with each step leftwards through the partition. 3 1 4 5 9 2 6 8 7 3 1 4 5 9 2 6 8 7 3 1 4 5 9 2 6 8 7 Since 2 is not greater than the pivot, the leftwards search can stop. 3 1 2 5 9 4 6 8 7 Now elements 4 and 2 (at positions 2 and 5, respectively) are swapped. 3 1 2 5 9 4 6 8 7 Next, the rightwards search resumes where it left off: at position 2, which is stored in the index i. 3 1 2 5 9 4 6 8 7 Immediately a large element is found, and the rightwards search stops with i being equal to 3. 3 1 2 5 9 4 6 8 7 Next the leftwards search, too, resumes where it left off: k was 5 so the element at position 5 is compared to the pivot before k is decremented again in search of a small element. 3 1 2 5 9 4 6 8 7 This continues without any matches for some time... 3 1 2 5 9 4 6 8 7 3 1 2 5 9 4 6 8 7 The small element is finally found, but no swap is performed since at this stage, i is equal to k. This means that all the small elements are on one side of the partition and all the large elements are on the other. 2 1 3 5 9 4 6 8 7 Only one thing remains to be done: the pivot is swapped with the element currently at i. This is acceptable within the algorithm because it only matters that the small element be to the left of the pivot, but their respective order doesn't matter. Now, elements 0 to (i - 1) form the left partition (containing all small elements) and elements k + 1 onward form the right partition (containing all large elements. Calling quickSort on elements 0 to 1 The right partition is passed into the quicksort function. 2 1 3 5 9 4 6 8 7 2 is chosen as the pivot. It is also compared to itself in the search for a small element within the partition. 2 1 3 5 9 4 6 8 7 The first, and in this case only, small element is found. 2 1 3 5 9 4 6 8 7 Since the partition has only two elements, the leftwards search begins at the second element and finds 1. 1 2 3 5 9 4 6 8 7 The only swap to be made is actually the final step where the pivot is inserted between the two partitions. In this case, the left partition has only one element and the right partition has zero elements. Calling quickSort on elements 0 to 0 Now that the left partition of the partition above is quicksorted: there is nothing else to be done Calling quickSort on elements 2 to 1 The right partition of the partition above is quicksorted. In this case the starting index is greater than the ending index due to the way these are generated: the right partition starts one past the pivot of its parent partition and goes until the last element of the parent partition. So if the parent partition is empty, the indices generated will be out of bounds, and thus no quicksorting will take place. Calling quickSort on elements 3 to 8 The right partition of the entire array is now being quicksorted 5 is chosen as the pivot. 1 2 3 5 9 4 6 8 7 1 2 3 5 9 4 6 8 7 The rightwards scan for a large element is initiated. 9 is immediately found. 1 2 3 5 9 4 6 8 7 Thus, the leftwards search for a small element begins... 1 2 3 5 9 4 6 8 7 1 2 3 5 9 4 6 8 7 1 2 3 5 9 4 6 8 7 At last, 4 is found. Note k = 5. 1 2 3 5 4 9 6 8 7 Thus the first large and small elements to be found are swapped. 1 2 3 5 4 9 6 8 7 The rightwards search for a large element begins anew. 1 2 3 5 4 9 6 8 7 Now that it has been found, the rightward search can stop. 1 2 3 5 4 9 6 8 7 Since k was stopped at 5, this is the index from which the leftward search resumes. 1 2 3 5 4 9 6 8 7 1 2 3 4 5 9 6 8 7 The last step for this partition is moving the pivot into the right spot. Thus the left partition consists only of the element at 3 and the right partition is spans positions 5 to 8 inclusive. Calling quickSort on elements 3 to 3 The left partition is quicksorted (although nothing is done. Calling quickSort on elements 5 to 8 The right partition is now passed into the quicksort function. 1 2 3 4 5 9 6 8 7 9 is chosen as the pivot. 1 2 3 4 5 9 6 8 7 The rightward search for a large element begins. 1 2 3 4 5 9 6 8 7 1 2 3 4 5 9 6 8 7 No large element is found. The search stops at the end of the partition. 1 2 3 4 5 9 6 8 7 The leftwards search for a small element begins, but does not continue since the search indices i and k have crossed. 1 2 3 4 5 7 6 8 9 The pivot is swapped with the element at the position k: this is the last step in splitting this partition into left and right subpartitions. Calling quickSort on elements 5 to 7 The left partition is passed into the quicksort function. 1 2 3 4 5 7 6 8 9 6 is chosen as the pivot. 1 2 3 4 5 7 6 8 9 The rightwards search for a large element begins from the left end of the partition. 1 2 3 4 5 7 6 8 9 The rightwards search stops as 8 is found. 1 2 3 4 5 7 6 8 9 The leftwards search for a small element begins from the right end of the partition. 1 2 3 4 5 7 6 8 9 Now that 6 is found, the leftwards search stops. As the search indices have already crossed, no swap is performed. 1 2 3 4 5 6 7 8 9 So the pivot is swapped with the element at position k, the last element compared to the pivot in the leftwards search. Calling quickSort on elements 5 to 5 The left subpartition is quicksorted. Nothing is done since it is too small. Calling quickSort on elements 7 to 7 Likewise with the right subpartition. Calling quickSort on elements 9 to 8 Due to the "sort the partition startitng one to the right of the pivot" construction of the algorithm, an empty partition is passed into the quicksort function. Nothing is done for this base case. 1 2 3 4 5 6 7 8 9 Finally, the entire array has been sorted.

public void quickSort(int array[]){
// pre: array is full, all elements are non-null integers
// post: the array is sorted in ascending order

	quickSort(array, 0, array.length - 1);              // quicksort all the elements in the array
}


public void quickSort(int array[], int start, int end){
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1)                   // check that there are at least two elements to sort
        {
                int pivot = array[start];       // set the pivot as the first element in the partition

                while (k > i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k > i)                                       // if the left seekindex is still smaller than
                                swap(array, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array, start, k);          // after the indices have crossed, swap the last element in
                                                // the left partition with the pivot 
                quickSort(array, start, k - 1); // quicksort the left partition
                quickSort(array, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}

public void swap(int array[], int index1, int index2) 
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
	int temp = array[index1];           // store the first value in a temp
	array[index1] = array[index2];      // copy the value of the second into the first
	array[index2] = temp;               // copy the value of the temp into the second
}