# What is Quick Sort - Lomuto

**Quicksort**is a popular sorting algorithm used to arrange a list of items in a specific order. Imagine you have a bunch of papers with different numbers written on them, and you need to put them in order from smallest to largest. Quicksort is one way to do that.

The basic idea behind quicksort is to divide the list of items into two smaller lists, one with items that are smaller than a chosen pivot (a random number from the list), and one with items that are larger. You then repeat this process with each of the smaller lists until the whole list is sorted.

Here's an example to help illustrate the process:

Let's say you have the following list of numbers: 7, 3, 9, 2, 5, 8, 1, 6, 4.

- Choose a pivot: Let's say we choose 5 as our pivot.
- Divide the list: We'll divide the list into two smaller lists, one with items smaller than 5 and one with items larger. The first list would be: 3, 2, 1, 4 and the second list would be: 7, 9, 8, 6.
- Repeat the process: We'll repeat this process with each of the smaller lists until the whole list is sorted. Let's focus on the first list (3, 2, 1, 4) for now. We'll choose 2 as our new pivot and divide the list into two smaller lists again. The first list would be: 1 and the second list would be: 3, 2, 4. We'll repeat this process with each of the smaller lists until the whole list is sorted.
- Merge the lists: Once each of the smaller lists is sorted, we can merge them back together to get the final sorted list: 1, 2, 3, 4, 5, 6, 7, 8, 9.

## Who invented it?

Quicksort was invented by Tony Hoare, a British computer scientist, in 1959 while he was a student at Moscow State University. Hoare developed quicksort as part of his research on the ALGOL programming language. The algorithm was initially published in the Communications of the ACM (Association for Computing Machinery) in 1961 and has since become one of the most widely used sorting algorithms.

## Pseudocode

```
function quicksort(list)
if length of list is 1 or less, return list
select a pivot element from the list
create two empty lists: left and right
for each element in list (except the pivot):
if element is less than or equal to pivot, append to left
else, append to right
return concatenate(quicksort(left), pivot, quicksort(right))
```

In this pseudocode, quicksort is a function that takes a list as an input and returns a sorted list. The function first checks if the length of the list is 1 or less. If so, the list is already sorted, and the function returns the list as is.

If the length of the list is greater than 1, the function selects a pivot element from the list. Then it creates two empty lists, left and right, to hold elements that are less than or equal to the pivot and greater than the pivot, respectively.

The function then iterates through each element in the list (except the pivot) and appends it to either the left list or the right list, depending on whether it's less than or equal to the pivot or greater.

Finally, the function recursively calls quicksort on the left and right lists, and concatenates the sorted left list, the pivot element, and the sorted right list into a single sorted list.

If the length of the list is greater than 1, the function selects a pivot element from the list. Then it creates two empty lists, left and right, to hold elements that are less than or equal to the pivot and greater than the pivot, respectively.

The function then iterates through each element in the list (except the pivot) and appends it to either the left list or the right list, depending on whether it's less than or equal to the pivot or greater.

Finally, the function recursively calls quicksort on the left and right lists, and concatenates the sorted left list, the pivot element, and the sorted right list into a single sorted list.

## Sample Code

```
// C++ code snippet
void quicksort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
// Partition the array
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
// Recursively sort the subarrays
if (left < j) quicksort(arr, left, j);
if (i < right) quicksort(arr, i, right);
}
int main() {
int arr[] = { 7, 3, 9, 2, 5, 8, 1, 6, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
quicksort(arr, 0, n - 1);
cout << "\nSorted array:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```

```
# Python code snippet
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Example usage
arr = [7, 3, 9, 2, 5, 8, 1, 6, 4]
sorted_arr = quicksort(arr)
print(sorted_arr)
```

```
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {7, 3, 9, 2, 5, 8, 1, 6, 4};
System.out.println("Unsorted array: " + Arrays.toString(arr));
quicksort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
public static void quicksort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quicksort(arr, left, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```

## Time and Space Complexity

- The time complexity of quicksort is O(n log n) on average, where n is the number of elements in the array. This means that the running time of quicksort grows in proportion to the size of the input, but at a rate that is less than linear.

The worst-case time complexity of quicksort is O(n^2), which occurs when the pivot element is either the smallest or largest element in the array, and the array is already sorted in ascending or descending order. In this case, quicksort will make n recursive calls, each of which processes a subarray of size n - 1, leading to a total running time of O(n^2).

- The space complexity of quicksort is O(log n) on average, as it uses the call stack to keep track of the recursive calls. In the worst case, the space complexity can be O(n) if the partitioning always results in unbalanced subarrays.

It's worth noting that the space complexity of quicksort can be reduced to O(1) by using an in-place partitioning algorithm, which swaps elements within the input array rather than creating separate subarrays. This requires careful implementation and can affect the running time of the algorithm, but can be useful in situations where memory usage is a concern.

## Advantages

- Quicksort is very fast and efficient, with an average-case time complexity of O(n log n), which is faster than many other popular sorting algorithms such as merge sort and heap sort.
- Quicksort is a widely used and well-known algorithm, with many well-documented implementations and optimizations available.
- Quicksort can be used on large datasets, as it has good memory efficiency due to its ability to sort elements in place, and it can be parallelized for even faster performance.

## Disadvantages

- Quicksort's worst-case time complexity is O(n^2), which can occur when the pivot element is either the smallest or largest element in the array. This worst-case scenario can be avoided by choosing a good pivot element, but doing so requires additional computation and can add complexity to the algorithm.
- Quicksort is not a stable sorting algorithm, which means that the order of equal elements in the input array may not be preserved in the output array. This can be a disadvantage in some applications.
- Quicksort may not be suitable for sorting data that is already mostly sorted, as this can lead to unbalanced partitions and a worst-case time complexity of O(n^2).
- Quicksort may require additional memory if the implementation uses a recursive approach, as each recursive call adds a new frame to the call stack. This can be mitigated by using an iterative approach or optimizing the algorithm to reduce the depth of the recursion.