Quick sort
Quick sort is another divide and conquer algorithm. It is a popular, fast sorting algorithm that can perform sorting in-place, so it is space efficient and has been used as the reference implementation in Java as well as the default library sort function in Unix. The algorithm works by dividing an initial array into two small subsequences, one with the lower sequences and another with the higher sequences, based on the pivot selected by a partitioning scheme. Its average running time is O(n lg n), mainly due to its tight inner loop. It can have a worst case running time of O(n2), but this can be minimized by ensuring the data is in a random order first. Additionally, ensuring that the correct pivot is selected will dramatically affect ...
Get Swift Data Structure and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
