C program to perform Quick Sort Algorithm

Quick Sort is the fastest internal type of sorting algorithm with time complexity O(N log N), In this type of sorting the elements, are partitioned into two subgroups on the basis of a pivot element, all the elements to the right of the pivot should be greater than the pivot and all the left elements should be smaller than the pivot.

C program to perform quick sort algo

For example, we have following elements to sort so to partition them we will follow a simple logic.

index 0 1 2 3 4 5 6 7

7 2 3 4 8 6 8 9

We will set our pivot element as the first element of the group so in this case, our pivot will be pivot=12

Now we will take two pointers i and j and set them as i=index of first element(0) and j = index of last element(6)

Now we will move i forward until valueat(i) < pivot and we will move j backwards until valueat(j) > pivot, if i<j then we will swap valueat(i) with valueat(j) else we will swap pivot with valueat(j).

Following the algorithm, we will partition the above elements as

Quick sort in C

Quick sort program in C

C Program To Sort Arrays using Quick Sort Algorithm

#include<stdio.h> #define SIZE 20 int arr[SIZE]; void quicksort(int a[],int l,int u); int partition(int a[],int x,int y); int main(){ int i,n; printf("Enter the size of array(MAX 20):"); scanf("\%d",&n); printf("Enter array elements"); for(i=0;i<n;i++){ scanf("\%d",&arr[i]); } quicksort(arr,0,n-1); for(i=0;i<n;i++){ printf("\%d ",arr[i]); } } void quicksort(int a[],int l,int u){ int j; if(l<u){ j = partition(a,l,u); quicksort(a,l,j-1); quicksort(a,j+1,u); } } int partition(int a[],int l,int u){ int v,i,j,temp; v = a[l]; i = l; j = u+1; do{ do{ i++; //moving pointer i forward  }while(a[i]<v && i<=u);  do{           j--;     //moving pointer j backward  }while(v<a[j]);  if(i<j){               //swapping  temp = a[i];  a[i] = a[j];  a[j] = temp;  } }while(i<j); a[l] = a[j]; a[j] = v; return j; }

Output of the above code

Quick sort output

Thanks for reading

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

Also, don’t forget to subscribe to our Newsletter.

If you like this article, then please share it and help us grow.

Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV
17 August 2018

Explaining Register variables in C with examples
17 August 2018

C program to generate all combinations of N-Bit Binary String
10 July 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями:
Добавить комментарий