Quick Sort Program in C/C++

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.
Additionally, quicksort's sequential and localized memory references work well with a cache.
Quicksort is a comparison sort and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.



Below is a C program based on Quick Sort Algorithm.


#include<stdio.h>
void quicksort(int[10], intint);
int main(){
 int x[20], size, i;
 printf("\nEnter size of the array: ");
 scanf("%d", &size);
 printf("\nEnter %d elements:\n ", size);
 for (i = 0; i < size; i++)
  scanf("%d", &x[i]);
 quicksort(x, 0, size - 1);
 printf("\nSorted elements : ");
 for (i = 0; i < size; i++)
  printf(" %d", x[i]);
 return 0;
}
void quicksort(int x[10], int first, int last){
 int pivot, j, temp, i;
 if (first < last){
  pivot = first;
  i = first;
  j = last;
  while (i < j){
   while (x[i] <= x[pivot] && i<last)
    i++;
   while (x[j]>x[pivot])
    j--;
   if (i < j){
    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
   }
  }
 
  temp = x[pivot];
  x[pivot] = x[j];
  x[j] = temp;
  quicksort(x, first, j - 1);
  quicksort(x, j + 1, last);
 }
}
 

Check out other methods of sorting in Data Structure :
1. Implementation of Insertion Sort in C
2. Implementation of Selection Sort in C
3. Implementation of Quick Sort in C
4. Implementation of Bubble Sort in C
5. Implementation of Heap sort in C
6. Implementation of Merge Sort in C
7. Implementation of Radix Sort in C

2 comments

Post a Comment