Quick Sort
Quick sort is the fastest internal sorting algorithm with the time complexity of O (n log n). It is a highly efficient algorithm.
This algorithm uses the divide and conquer technique. A divide and conquer strategy breaks down algorithms into smaller subproblems, solves each subproblem, and then combines the results to solve the original problem.
- Divide: In Divide, select a pivot element. After that, divide the array into two sub-arrays, with each element in the left sub-array being smaller than or equal to the pivot element and each element in the right sub-array being larger.
- Conquer: Sort two subarrays recursively with Quicksort.
- Combine: Combine the sorted arrays.
Quicksort picks one element as the pivot, and then partitions the array around the pivot element.
The quick sort method divides a large array into two arrays, the first containing values that are smaller than the pivot, and the second containing values that are larger than the pivot.
Following that, left and right subarrays are also partitioned using the same method. This continues until the sub-array contains a single element.
Selecting a pivot
A good pivot is essential to the fast implementation of quicksort. However, it is common to determine a good pivot.
- The pivot can be chosen randomly from the array, i.e. select the random pivot.
- The pivot element can either be the rightmost element or the leftmost element of an array.
- Choose the median element as the pivot.
Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n log n) |
| Average Case | O(n log (n)2) |
| Worst Case | O(n2) |
- Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
- Average Case O(n log (n)2): The array elements are in a jumbled order that is not properly ascending and descending.
- Worst Case O(n2): This occurs when the array elements need to be sorted in reverse order.
Space Complexity
| Space Complexity | O(n log n) |
| Stable | No |
- The space complexity of quick sort is
O (n log n).
Shell Sort
#include <stdio.h>
/* function that consider last element as pivot,
place the pivot at its exact position, and place
smaller elements to left of pivot and greater
elements to right of pivot. */
int partition(int a[], int start, int end) {
int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++) {
// If current element is smaller than the pivot
if (a[j] < pivot) {
i++; // increment index of smaller element
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}
/* function to implement quick sort */
/* a[] = array to be sorted, start = Starting index, end = Ending index */
void quick_sort(int a[], int start, int end) {
if (start < end) {
//p is the partitioning index
int p = partition(a, start, end);
quick_sort(a, start, p - 1);
quick_sort(a, p + 1, end);
}
}
/* function to print an array */
void print(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main() {
int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
quick_sort(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
print(a, n);
return 0;
} public class QuickSort {
/* function that consider last element as pivot,
place the pivot at its exact position, and place
smaller elements to left of pivot and greater
elements to right of pivot. */
static int partition (int a[], int start, int end) {
int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++) {
// If current element is smaller than the pivot
if (a[j] < pivot) {
// increment index of smaller element
i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}
/* function to implement quick sort */
/* a[] = array to be sorted, start = Starting index, end = Ending index */
static void quickSort(int a[], int start, int end) {
if (start < end) {
// p is partitioning index
int p = partition(a, start, end);
quickSort(a, start, p - 1);
quickSort(a, p + 1, end);
}
}
/* function to print an array */
static void print(int a[], int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };
int n = a.length;
System.out.println("\nBefore sorting array elements are - ");
print(a, n);
quickSort(a, 0, n - 1);
System.out.println("\nAfter sorting array elements are - ");
print(a, n);
System.out.println();
}
}