Quicksort

http://install4install.com

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 :

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

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

Screen Shot 2014-06-16 at 7.19.46 PM

Fig 1 : Example

 

Figure 2

Screen Shot 2014-06-16 at 7.21.49 PM

Fig 2 : Sublist S1

 

Figure 3

Screen Shot 2014-06-16 at 7.23.01 PM

Fig 3 : Sublist S2 

 

Figure 4

Screen Shot 2014-06-16 at 7.23.41 PM

Fig 4 : Sublist S3

 Figure 5

Screen Shot 2014-06-16 at 7.25.58 PM

Fig 5 : Sublist S4

Figure 6

Screen Shot 2014-06-16 at 7.25.08 PM

Fig 6 : Sublist S5

 

Combine sub-lists to obtain a sorted list.

Screen Shot 2014-06-16 at 7.32.19 PM

Fig 7 : Sorted Array

 



Short URL: http://tinyit.cc/9f8899
Author: Cusp2207 on June 18, 2014
Category: Computer Science
Tags:
1 response to “Quicksort”
  1. dramatic theater paris says:

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

Leave a Reply

Last articles