Saturday, June 19, 2021
Home coding Write a program to implement quick sort algorithm.

Write a program to implement quick sort algorithm.

We have given an integer array,we have to sort an array using quick sort algorithm

Example:

input:arr[]={1,5,3,2}
output:1,2,3,5

Logic:

Step 1- pick a pivot.
step 2-element smaller than pivot put them on the left side.
step 3-element greater than pivot put them on right side.
step 4-divide the subpart again and partition them into left and right.
step 5-finally array is sorted.

Code-

#include <iostream>
using namespace std;
void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}
int partition(int array[], int low, int high) {
  int pivot = array[high];
  int i = (low - 1);
  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) 
    {
      i++;
      swap(&array[i], &array[j]);
    }
  }

  swap(&array[i + 1], &array[high]);
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {
    int pi = partition(array, low, high);
    quickSort(array, low, pi - 1);
    quickSort(array, pi + 1, high);
  }
}
int main() {
  int array[] = {1, 2,3,4,5};
  int n = sizeof(array) / sizeof(array[0]);
  quickSort(array, 0, n - 1);
for(int i=0;i<n;i++)
{
    cout<<array[i]<<" ";
}
cout<<endl;

}

Output:

1 2 3 4 5

Time complexity:0(N*N)

Space Complexity:O(1)

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -

Most Popular

Recent Comments