Quicksort makes O(n log n) comparisions to sort n items. In the worst case, it makes O(n^2) comparisions. Quicksort is often faster in practice than other O(n log n) algorithms. Qucicksort is a comparison sort.

Quicksort is NOT a stable sort.

Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during recursion.

This video has a really nice explanation of the algorithm:

https://www.youtube.com/watch?v=COk73cpQbFQ

Code:

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

Quicksort is NOT a stable sort.

Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during recursion.

This video has a really nice explanation of the algorithm:

https://www.youtube.com/watch?v=COk73cpQbFQ

Code:

import java.util.Arrays; public class QuickSort { public static void quickSort(int array[]) { quickSorter(array, 0, array.length - 1); } public static void quickSorter(int array[], int lo, int hi) { if (lo > hi) return; int partition = partition(array, lo, hi); quickSorter(array, lo, partition - 1); quickSorter(array, partition + 1, hi); } private static int partition(int array[], int lo, int hi) { int partitionIndex = lo; for (int i = lo; i <= hi; ++i) { if (array[i] < array[hi]) { int temp = array[partitionIndex]; array[partitionIndex] = array[i]; array[i] = temp; partitionIndex++; } } int temp = array[partitionIndex]; array[partitionIndex] = array[hi]; array[hi] = temp; return partitionIndex; } public static void main(String[] args) { int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123}; quickSort(array); System.out.println(Arrays.toString(array)); } }

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

## No comments:

## Post a Comment