# 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. 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  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 Also, don’t forget to subscribe to our Newsletter.

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

Binary Tree in Python
02 September 2018

Explaining Register variables in C with examples
17 August 2018

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

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