C Program to Implement Quick Sort
This is the C Program to sort an array using quicksort,it uses divide and conquer mechanism to sort the array
|
Visualization of the quicksort algorithm. The horizontal lines are pivot values.
|
|
| Class | Sorting algorithm |
|---|---|
| Worst case performance | O(n2) |
| Best case performance | O(n log n) (simple partition) or O(n) (three-way partition and equal keys) |
| Average case performance | O(n log n) |
| Worst case space complexity | O(n) auxiliary (naive) O(log n) auxiliary (Sedgewick 1978) |
#include<stdio.h> int arr[100],n;
main() { int i,j; printf("ENTER THE NO"); scanf("%d",&n);
for(i=0;i<n;i++) { scanf("%d",&arr[i]); } quicksort(0,n-1); for(i=0;i<n;i++) { printf("%dn",arr[i]); } getch(); }
quicksort(int minsize,int maxsize) { int temp,low,high,pivot; if(minsize>maxsize) return; else { pivot=arr[minsize]; low=minsize+1; high=maxsize; while(low<=high) { while((arr[low]<=pivot)&&(low<=maxsize)) { low++; } while((arr[high]>pivot)&&(high>=minsize)) { high--; } if(low<high) swap(low,high); }
swap(high,minsize); quicksort(minsize,high-1); quicksort(high+1,maxsize); } }
swap(int a,int b) { int temp; temp=arr[a]; arr[a]=arr[b]; arr[b]=temp; }
Recent Comments