# Quick Sort

In the quick sort method, an array a[1],…..,a[n] is sorted by selecting some value in the array as a key element. We then swap the first element of the list with the key element so that the key will be in the first position. We then determine the key’s proper place in the list. The proper place for the key is one in which all elements to the left of the key are smaller than the key, and all elements to the right are larger.

To obtain the key’s proper position, we traverse the list in both directions using the indices i and j, respectively. We initialize i to that index that is one more than the index of the key element. That is, if the list to be sorted has the indices running from m to n, the key element is at index m, hence we initialize i to (m+1). The index i is incremented until we get an element at the ith position that is greater than the key value. Similarly, we initialize j to n and go on decrementing j until we get an element with a value less than the key’s value.

We then check to see whether the values of i and j have crossed each other. If not, we interchange the elements at the key (mth)position with the elements at the jth position. This brings the key element to the jth position, and we find that the elements to its left are less than it, and the elements to its right are greater than it. Therefore we can split the list into two sublists. The first sublist is composed of elements from the mth position to the (j–1)th position, and the second sublist consists of elements from the (j+1)th position to the nth position. We then repeat the same procedure on each of the sublists separately.

Choice of the key

We can choose any entry in the list as the key. The choice of the first entry is often a poor choice for the key, since if the list has already been sorted, there will be no element less than the first element selected as the key. So, one of the sublists will be empty. So we choose a key near the center of the list in the hope that our choice will partition the list in such a manner that about half of the elements will end up on one side of the key, and half will end up on the other.

Therefore the function getkeyposition is

int getkeyposition(int i,j) { return(( i+j )/ 2); }

The choice of the key near the center is also arbitrary, so it is not necessary to always divide the list exactly in half. It may also happen that one sublist is much larger than the other. So some other method of selecting a key should be used. A good way to choose a key is to use a random number generator to choose the position of the next key in each activation of quick sort. Therefore, the function getkeyposition is:

int getkeyposition(int i,j) { return(random number in the range of i to j); }

#### Complete Example

#include <stdio.h> #define MAX 10 void swap(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } int getkeyposition(int i,int j ) { return((i+j) /2); } void qsort(int list[],int m,int n) { int key,i,j,k; if( m < n) { k = getkeyposition(m,n); swap(&list[m],&list[k]); key = list[m]; i = m+1; j = n; while(i <= j) { while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key)) j-; if( i < j) swap(&list[i],&list[j]); } swap(&list[m],&list[j]); qsort(list[],m,j-l); qsort(list[],j+1,n); } } void readlist(int list[],int n) { int i; printf("Enter the elements\n"); for(i=0;i<n;i++) scanf("%d",&list[i]); } void printlist(int list[],int n) { int i; printf("The elements of the list are: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); } void main() { int list[MAX], n; printf("Enter the number of elements in the list max = 10\n"); scanf("%d",&n); readlist(list,n); printf("The list before sorting is:\n"); printlist(list,n); qsort(list,0,n-1); printf("\nThe list after sorting is:\n"); printlist(list,n); }

#### Explanation

Consider the following list:

1.When qsort is activated the first time, key = 67, i =1, and j =6. i is incremented until it becomes 7, because there is no element greater than the key. j is not decremented, because at position 6, the value that we have is less than the key. Since i > j, we interchange the key element (the element at position 0) with the element at position 6, and call qsort recursively, with the left sublist made of elements from positions 0 to 5, and the right sublist empty as shown here:

2.When qsort is activated the second time on the left sublist as shown, key = 23, i =1, and j =5. i is incremented until it reaches 2. Because the element at position 2 is greater than the key, j is decremented to 4 because the value at position 4 is less than the key. Since i < j, the elements at positions 2 and 4 are swapped. i is then incremeneted to 4 and j is decremented to 3. Since i > j, we interchange the key element (the element at position 0), with the element at position 3, and call qsort recursively with the left sublist made of elements from position 0 to 2, and the right sublist made of elements from position 4 to 5, as shown here:

3. By continuing in this fashion, we eventually get the list sorted.

4. The average case-time complexity of the quick sort algorithm can be determined as follows:

We assume that every time this is done, the list gets split into two approximately equal-sized sublists. If the size of a given list is n, it gets split into two sublists of size approximately n/2. Each of these sublists gets further split into two sublists of size n/4, and this is continued until the size equals 1. When the quick sort works with a list of size n, it places the key element (which takes the first element of the list under consideration) in its proper position in the list. This requires no more than n iterations. After placing the key element in its proper position in the list of size n, quick sort activates itself twice to work with the left and right sublists, each assumed to be of size n/2. Therefore T(n) is the time required to sort a list of size n. Since the time required to sort the list of size n is equal to the sum of the time required to place the key element in its proper position in the list of size n, and the time required to sort the left and right sublists, each assumed to be of size n/2. T(n) turns out to be:

∴ T(n) = c*n + 2*T(n/2)

where c is a constant and T(n/2) is the time required to sort the list of size n/2.

5.Similarly, the time required to sort a list of size n/2 is equal to the sum of the time required to place the key element in its proper position in the list of size n/2 and the time required to sort the left and right sublists each assumed to be of size n/4. T(n/2) turns out to be:

T(n/2) = c*n/2 + 2*T(n/4)

where T(n/4) is the time required to sort the list of size n/4.

∴ T(n/4) = c*n/4 + 2*T(n/8), and so on. We eventually we get T(1) = 1.

∴ T(n) = c*n + 2(c*n(n/2) + 2T(n/4))

∴ T(n) = c*n + c*n + 4T(n/4)) = 2*c*n + 4T(n/4) = 2*c*n + 4(c*(n/4) + 2T(n/8))

∴ T(n) = 2*c*n + c*n + 8T(n/8) = 3*c*n + 8T(n/8)

∴ T(n) = (log n)*c*n + n T(n/n)= (log n)*c*n + n T(1) = n + n*(log n) *c

∴ T(n) μ n log(n)

6.Therefore, we conclude that the average complexity of the quick sort algorithm is O(nlog n). But the worst-case time complexity is of the O(n2). The reason for this is, in the worst case, one of the two sublists will always be empty and the other will be of size (n−1), where n is the size of the original list. Therefore, in the worst case, T(n) turns out to be :

7.Space complexity: The average-case space complexity is log2n, because the space complexity depends on the maximum number of activations that can exist. We find that if we assume that every time the list gets split into approximately two equal-sized lists, the maximum number of activations that will exist simultaneously will be log2n.

In the worst case, there exist n activations, because the depth of the recursion is n. So the worst-case space complexity is O(n).