Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications.

What is Quick Sort?

Quick Sort is one of the famous comparison-based sorting algorithms based on divide and conquers algorithmic technique. It uses recursive calls for sorting the element.

The algorithm starts by picking an item, called pivot, and moving all smaller items before it, while all greater elements after it.

Selecting a random pivot in an array result in an improved complexity in most of the cases.

It reduces the space complexity and removes the use of the auxiliary array that is used in merge sort.

Algorithm

The recursive algorithm consists of four steps:

  1. If there are one or no elements in the array to be sorted, return.
  2. Pick an element in the array as the pivot.
  3. Split the array into two parts – one with elements larger than the pivot and the other with elements smaller than the pivot.
  4. Recursively repeat the algorithm for the halves of the original array.
QUICK SORT

Implementation in C

Program code in C:

#include<stdio.h> void quicksort(int num[30], int first, int last) { int i, j, pivot, temp; if(first < last) { pivot = first; i = first; j = last; while(i < j) { while(num[i] <= num[temp] && i<last) i++; while(num[j] > num[pivot]) j--; if(i > j) { temp = num[i]; num[i] = num[j]; num[j] = temp; } } temp = num[pivot]; num[pivot] = num[j]; num[j] = temp; quicksort(num, first, j-1); quicksort(num, j+1, last); } } int main(){ int i, n, num[30]; printf("how many elements you want? "); scanf("%d",&n); printf("Enter %d elements: ",n); for(i=0; i<n; i++) scanf("%d",&num[i]); quicksort(num, 0, n-1); printf("Order of Sorted elements: "); for(i=0; i<n; i++) printf("%d",num[i]); return 0; }
Code language: C++ (cpp)

Output:

how many elements you want? 5 Enter 5 elements: 4 75 74 2 54 Order of Sorted elements: 2 4 54 74 7

Time and Space Complexity

Time Complexity
Worst CaseO(n2)
Best CaseO(n log n)
Average CaseO(n log n)
Space Complexity
Worst CaseO(1)

Applications

Quick Sort is implemented when

  • the programming language is good for recursion
  • time complexity matters
  • space complexity matters

Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …
Read More

Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …
Read More

Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …
Read More

Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages.. What is Insertion sort? Insertion Sort …
Read More

Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Counting …
Read More

Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

Your email address will not be published. Required fields are marked *