Quick Sort Algorithm
Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved. develop by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a normally used algorithm for sorting. Robert Sedgewick's Ph.D. thesis in 1975 is considered a milestone in the survey of Quicksort where he resolved many open problems associated to the analysis of various pivot choice schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps.
Jon Bentley and Doug McIlroy integrated various improvements for purpose in programming library, including a technique to deal with equal components and a pivot scheme known as pseudomedian of nine, where a sample of nine components is divided into groups of three and then the median of the three medians from three groups is choose. In the Java core library mailing lists, he initiated a discussion claiming his new algorithm to be superior to the runtime library's sorting method, which was at that time based on the widely used and carefully tuned variant of classic Quicksort by Bentley and McIlroy.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.sorts
/**
* Developed by Tony Hoare in 1959, with his work published in 1961, Quicksort is an efficient sort algorithm using
* divide and conquer approach. Quicksort first divides a large array into two smaller sub-arrays: the low elements
* and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:
* 1) Pick an element, called a pivot, from the array.
* 2) Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot,
* while all elements with values greater than the pivot come after it (equal values can go either way).
* After this partitioning, the pivot is in its final position. This is called the partition operation.
* 3) Recursively apply the above steps to the sub-array of elements with smaller values and separately to
* the sub-array of elements with greater values.
*/
@ComparisonSort
@UnstableSort
class QuickSort: AbstractSortStrategy() {
override fun <T : Comparable<T>> perform(arr: Array<T>) {
sort(arr, 0, arr.size - 1)
}
private fun <T : Comparable<T>> sort(arr: Array<T>, lo: Int, hi: Int) {
if (hi <= lo) return
val j = partition(arr, lo, hi)
sort(arr, lo, j - 1)
sort(arr, j + 1, hi)
}
private fun <T : Comparable<T>> partition(arr: Array<T>, lo: Int, hi: Int): Int {
var i = lo
var j = hi + 1
val v = arr[lo]
while (true) {
while (arr[++i] < v) {
if (i == hi) break
}
while (v < arr[--j]) {
if (j == lo) break
}
if (j <= i) break
arr.exch(j, i)
}
arr.exch(j, lo)
return j
}
}
