# Quick sort

#### Stable: No

Quick sort is similar to merge sort making it a divide and conquer algorithm. You can make quick sort to choose its pivot point, like at the start or the end of the array. If the array is already sorted then you get the worst case scenario.

• Pivot with first element
• Pivot Last element
• Pivot middle element
• Pivot a random element

The following example makes use of thye last element to be the pivot but you can change to any pivot if you so with to.

## C++/C example

```
//Swaps the values
void QuickSwap(int* x, int* y)
{
int t = *x;
*x = *y;
*y = t;
}

//Grabs the last element and pivots it to the correct position in the sorted array
int QuickPartition (int A[], int low, int high) {

int piv = A[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++)
{
//Checks if the current element is smaller or equal to the pivot point
if (A[j] <= piv)
{
i++;
QuickSwap(&A[i], &A[j]);
}
}
QuickSwap(&A[i + 1], &A[high]);
return (i + 1);
}

//Main function that implements the quick sort algorithm
void QuickSort(int A[], int low, int high)
{
if (low < high)
{
//the partition for the index that is in the correct positiion
int pi = QuickPartition(A, low, high);

//sort the elements before the partition
QuickSort(A, low, pi - 1);
//Sorts it after the partition
QuickSort(A, pi + 1, high);
}
}

int main()
{
double random;

//create an empty array with 100 elements
int A;

//creating random number generator
srand (time(NULL));

//get the size of array
int size = (sizeof(A)/sizeof(A));

//loops through and inserts into array with a random int between 1-1000
for (int i = 0; i < size; i++)
{
random = rand() % 10001 + 0;
A[i] = random;
}

//begin sorting
QuickSort(A, 0, size-1);

//print through sorted array
for (int i = 0; i < size; i++)
{
std::cout << A[i] << std::endl;
}

return 0;
}
```

## Summary

Fast algorithm and requires very little code and is easy to implement only downside is that it can be inefficient if the data is already sorted.