**QuickSort** is an in-place sorting algorithm with worst-case time complexity of $n^{2}$.

Quicksort follows the divide and conquer algorithm. Quicksort can be done in iteratively as well as recursively, but we will be focusing on the recursive method as it is easy and simple.

First, we will partition the array about the pivot and sort the array such that the elements that are lesser than the pivot are on the left side of the pivot, and the elements that are greater than the pivot are on the right side.

Let the first element be `i`

and the last element be `j`

â€“ the pivot is `n`

. Now, we will sort the elements from `i`

to `n-1`

and `n+1`

to `j`

.

We will take input in a text file for the program. In the text, we will keep `-1`

as the last element so that the `while`

loop ends, as soon as it gets to `-1`

, and sorts the elements before it. Here, `-1`

is the endpoint for sorting.

quick_sort.c

quicksort.txt

#include<stdio.h>#include<stdlib.h>void quicksort(int a[100],int first,int last){int i,j,pivot,temp;if(first<last){pivot=first;i=first;j=last;while(i<j){while(a[i]<=a[pivot] && i<last){i++;}while(a[j]>a[pivot]){j--;}if(i<j){temp=a[i];a[i]=a[j];a[j]=temp;}}temp=a[pivot];a[pivot]=a[j];a[j]=temp;quicksort(a,0,j-1);quicksort(a,j+1,last);}}void main(){FILE *ptr;int n,a[100],i=0,num;ptr=fopen("quicksort.txt","r");if(ptr==NULL){printf("Unable to open the file");exit(0);}else{while((fscanf(ptr,"%d",&n))!=-1) //In text file we will take -1 as the last element so that only elements until -1 will be considered.//{a[i]=n;i++;}num=i-1;printf("elements of array are:\n");for(i=0;i<num;i++){printf("%d \n",a[i]);}}quicksort(a,0,num-1);printf("sorted elements are:\n");for(i=0;i<num;i++){printf("%d\n",a[i]);}}

TRENDING TOPICS