Quick sort in Data structure is another simple algorithm for sorting an array.
Quick Sort

Page Contents

## Quick Sort

What is Quick sort in Data structure?: Another divide and conquer algorithm in Data structure. The special variable is declared which is known as the pivot element. According to the pivot element, the array is divided into sub-array. Choosing of pivot element is very important otherwise the performance might degrade.

Quick sort in Data structure is the fastest internal sorting algorithm without any additional memory for sorting data.

### Quick sort technique

In quick sort algorithm, first, we choose the key element in the list which is called Pivot element. Then we reorder the list with the rule that all elements which are less than the pivot come before pivot element and so that all greater will come after the pivot. After this partitioning, the pivot is in its final position.
Then, recursively reorder the list.

Choosing the pivot element is very important. The different way to choose a pivot element.
Always pick the first element as a pivot.
Always pick the last element as the pivot (implemented below)
Pick a random element as pivot.
Pick median as a pivot.

### Quick sort algorithm

1. Choose the highest index value has a pivot.
2. Take two variables to point left and right of the list excluding pivot.
3. left points to the low index
4. right points to the high
5. while value at left is less than pivot move right
6. while value at the right is greater than pivot move left
7. if both step 5 and step 6 does not match swap left and right
8. if left ≥ right, the point where they met is a new pivot

### Quick sort program in c

```#include<stdio.h>
#include<conio.h>

#define MAX_SIZE 5

void quick_sort(int, int);
int arr_sort[MAX_SIZE];

int main() {
int i;

printf(" Quick Sort\n");
printf("\nEnter %d Elements for Sorting\n", MAX_SIZE);
for (i = 0; i < MAX_SIZE; i++)
scanf("%d", &arr_sort[i]);

printf("Given array: ");
for (i = 0; i < MAX_SIZE; i++) {
printf(" %d", arr_sort[i]);
}

quick_sort(0, MAX_SIZE - 1);

printf("\n\nSorted array:");
for (i = 0; i < MAX_SIZE; i++) {
printf(" %d", arr_sort[i]);
}
getch();
}

void quick_sort(int f, int l) {
int i, j, t, p = 0;
if (f < l) {
p = f;
i = f;
j = l;
while (i < j) {
while (arr_sort[i] <= arr_sort[p] && i < l)
i++;
while (arr_sort[j] > arr_sort[p])
j--;
if (i < j) {
t = arr_sort[i];
arr_sort[i] = arr_sort[j];
arr_sort[j] = t;
}
}

t = arr_sort[p];
arr_sort[p] = arr_sort[j];
arr_sort[j] = t;
quick_sort(f, j - 1);
quick_sort(j + 1, l);
}
}```

### The complexity of Quick sort

The time complexity for Quicksort
The worst-case and average-case complexity: O(n2).
The Best case complexity of Quick sort: O(nlogn).
Space complexity for Quick sort: O(logn)