Quick Sort - Implementation in C

Quick Sort - Implementation in C

Like Merge Sort, Quick Sort is also based on divide and conquer algorithm. It piccks an element as pivot and partitions the array around the pivot element.

Algorithm For Quick Sort

Basically two functions are required to perform quick sort

a. Quicksort(arr, low, high)

b. Partition(arr, low, high)

Quicksort(arr, low, high) 

Here arr is an array of size n, low is lowerbound of array i..e. 0 and high is n-1.

1. The condition is checked for low < high.
2. If the condition is true, then in a variable named test, the returning value of function partition is assigned. 
3. Also a recursive function Quicksort is called with parameters - base address, lower bound and test - 1.
4. Also a recursive function Quicksort with parameters - base address, test +1, and upperbound is called.

Partition(arr[], low, high)

Partition is a function that is called to divide the array into wo parts around the pivot point after iteration.

1. The last element of array is assumed to be the pivot element..
2. (low-1) i.e. 0 is assigned to a variable 'i'.
3. A loop is run from j=low to j<=high-1.
4. Inside the loop, if the jth element of array is smaller than the pivot element, the value of 'i' is incremented by 1 and the values of ith element of array is swapped with jth element.
5. After the first iteration, the values of pivot element and the (i+1)th element are swapped.
6. The value of (i+1) is returned by the function.

---

PROGRAM

#include<stdio.h> int partition(int arr[],int low,int high) { int t,t2; int pivot=arr[high]; int i=(low-1); for(int j=low;j<=high-1;j++) { if(arr[j]<=pivot) { i++; t=arr[i]; arr[i]=arr[j]; arr[j]=t; } } t2=arr[i+1]; arr[i+1]=arr[high]; arr[high]=t2; return i+1; } void quicksort(int arr[],int low,int high) { if(low<high) { int test=partition(arr,low,high); quicksort(arr,low,test-1); quicksort(arr,test+1,high); } } int main() { int i,n; int arr[100]; printf("Enter size of array"); scanf("%d",&n); printf("enter array"); for(i=0;i<n;i++) scanf("%d",&arr[i]); quicksort(arr,0,n-1); printf("sorted array"); for(i=0;i<n;i++) printf(" %d",arr[i]); }

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.