Facebook

Quicksort

Sorting is a technique to arrange the sequence of elements either in ascending or descending order. Quicksort is an efficient way to sort elements of array.The average running time of quicksort is O(nlogn).The steps followed in quicksort are :

  • Choose the pivot element(Say we choose the pivot element in the beginning of array).
  •  Scan from right to left and find first element in list which is less than the pivot element.Stop scanning as soon the element is found.
  • Swap it with the pivot element.
  • Now scan from left to right to find the first element which is greater than pivot element.
  • Swap the element with pivot.
  • Continue the process till the list is sorted or we get a list for which the above process fails to be followed up.
  • Divide/partition  the array with pivot in between into two sub-arrays .
  • Same process is followed on both the sub-arrays separately and further partitioning and processing is done if necessary.
  • Combine all the sub-arrays and their pivot elements to get a sorted array.

Program

#include<stdio.h>
void swap (int arr[], int left, int right)
 {
 int temp;
 temp=arr[left];
 arr[left]=arr[right];
 arr[right]=temp; 
 }
void quicksort( int arr[], int low, int high )
 {
 int pivot;
 if ( high > low )
 {
  pivot = partition( arr, low, high );
  quicksort( arr, low, pivot-1 );
  quicksort( arr, pivot+1, high );
 }
 } 
int partition( int arr[], int low, int high )
{
 int left, right;
 int item_pivot;
 int pivot = left = low; 
 item_pivot = arr[low]; 
 right = high;
 while ( left < right ) 
 {
  while( arr[left] <= item_pivot ) 
   left++;
  while( arr[right] > item_pivot) 
   right--;
  if ( left < right ) 
   swap(arr,left,right);
 }
 arr[low] = arr[right];
 arr[right] = item_pivot;
 return right;
}
void printarray(int arr[], int);
int main()
{
 int arr[30], i, n;
 //printf("\nEnter no. of elements: "); 
 scanf("%d", &n);
 //printf("\nEnter the elements: \n");
 for (i=0; i<n; i++)
  scanf ("%d", &arr[i]);
 printf("\nUnsorted array: \n");
 printarray(arr,n);
 quicksort(arr,0,n-1);
 printf("\nSorted array: \n");
 printarray(arr,n);
 }
 void printarray(int arr[], int n)
{
 int i;
 for (i=0; i<n; i++)
  printf(" %d ", arr[i]);
 printf("\n");
}

Run

 

Example

Figure 1

Say we have an array with elements 7,44,2,10,1,35,74,88,5,3,15.Scanning from right to left is done to to find element less than pivot and from left to right is done to find element greater than pivot.

Figure 1

  • The pivot element is the first element i.e 7.
  • Scan from  right to left and find element less than 7.3 is the first element so it is swapped with the pivot element.
  • Scan from left to right and find element greater than 7.44 is the first element encountered so it swapped with 7.
  • Scan from right to left.5 is less than pivot element i.e. 7 so they are swapped.
  • Scan from left to right.10 >7,so it swapped with 7.
  • Scan right-left.1 <7 so they are swapped.
  • Scan from left to right.There is no element in the list before pivot which is greater than pivot itself.Thus list is divided into two sub-lists S1 and S2 such that elements in S1 are less than pivot and elements in S2 are greater than pivot.

 

Figure 2

 

Figure 2

  • S1 has 3,5,2,1  with pivot element 3 and S2 has 35 74 88 10 44 15 with pivot element 35.(Fig 2)
  • Scan right to left in S1 and find element less than 3.1 <3 so they are exchanged.
  • Scan left-right in S1 and find element greater than 3.5>3 so they are swapped.
  • Scan right-left in S1.2<3 so they are swapped and sub-list S1 gets sorted.

 

Figure 3

Figure 3

  • Scan right-left in S2.15<35 ,so they are swapped
  • Left-right -74>35 so they are swapped.
  • Right-left-10<35 so they are swapped.
  • Left-Right - 88 >35 so they are swapped.

    Figure 4

 

 

Figure 4

  • Partition the sub-list into two further sub-lists S3 and S4.S3 has 15,10 and S4 has 88,44,74 .
  • Scan right-left in S3.10<15 so they are swapped and scanning from left-right does not gives any result.
  • S3 becomes sorted.

 

 

Figure 5

 

Figure 5

  • Scan right-left in S4.Pivot is 88.74<88 so they are swapped.
  • Scanning left to right is a failed attempt.

 

 

Figure 6

Figure 6

  • Partition S4 into S5 and S6.S5 has 74,44 and S6 is empty.
  • Scan right-left in S5.Pivot is 74.44<74 so they are swapped and list becomes sorted.

 

 

Combine sub-lists to obtain a sorted list.

 

Rate this post

Comments

This post currently has one response

  • Thank you for sharing this fine article. Very interesting ideas! (as always, btw)

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar