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.
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;
}
}