Randomized Sort

⚠️ This post was created when I was in high school and is no longer maintained.

1. Intuition

Instead of always using A(r) as the pivot, we pick a random element from the subarray A(p, r). We do so by first swapping A(r) with an element chosen at random from A(p, r). By sampling the range p...r, the pivot x = A[r] is equally likely to be any of the (r-p+1) elements.

Because the pivot is random, we expect the input array to split reasonably evenly on average.

2. Pseudocode

algorithm RandomQuickSort(array, start, end):
    if start < end then
        pivot_i = RandomPartition(array, start, end)
        
        QuickSort(array, start, pivot_i-1)
        QuickSort(array, pivot_i+1, end)

function RandomPartition(array, start, end):
    rand_i = Random(p, r)
    exchange A[r] with A[rand_i]
    return Partition(array, start, end)

function Partition(array, start, end):
    pivot = array[end]
    i = start - 1
    
    For j = start to end-1 do
        if array[j] <= pivot then
            i += 1
            exchange array[i] with array[j]
    
    exchange array[end] with array[i+1]
    
    return i+1

3. Code

// Scala
class QuickSort() {

    protected var _array: Array[Double] = _

    def this(array: Array[Double]) {
        this()
        println(">> QuickSort Constructor called")

        this._array = array
    }
    
    def quickSort(start: Int, end: Int): Unit = {
        if (start < end) {
            var pivot_i = partition( start, end)

            quickSort(start, pivot_i-1)
            quickSort(pivot_i+1, end)
        }
    }

    protected def partition(start: Int, end: Int): Int = {
        var pivot = _array(end)
        var i = start - 1

        for (j <- start until end) {
            if (_array(j) < pivot) {
                i += 1
                // swap
                var tmp = _array(i)
                _array(i) = _array(j)
                _array(j) = tmp
            }
        }
        var tmp = _array(i+1)
        _array(i+1) = _array(end)
        _array(end) = tmp

        return i+1
    }

    def printArray {
        println(_array.deep.mkString(" "))
    }

}

class RandomQuickSort(val array: Array[Double]) extends QuickSort(array) {

    println("\nBefore sorting:")
    println(array.deep.mkString(" "))

    def randomPartition(start: Int, end: Int): Int = {
        val rand_tmp = new scala.util.Random
        val rand_i = start + rand_tmp.nextInt((end - start) + 1)

        var tmp = _array(rand_i)
        _array(rand_i) = _array(end)
        _array(end) = tmp

        return partition(start, end)
    }

    override def quickSort(start: Int, end: Int): Unit = {
        if (start < end) {
            var pivot_i = randomPartition(start, end)

            quickSort(start, pivot_i-1)
            quickSort(pivot_i+1, end)
        }
    }
}


object RandomQuickSortAlgo {

    def main(args: Array[String]): Unit = {
        val array = Array(4234,234234,23,234,-134,4123,41,578,-342,55,0.2323,0.325)
        val randomQuickSort = new RandomQuickSort(array)
        
        randomQuickSort.quickSort(0, array.length-1)
        println("\nAfter sorting:")
        randomQuickSort.printArray
    }
}

# Python
import random

def random_partition(array, start, end):
    rand_i = random.randint(start, end)
    array[rand_i], array[end] = array[end], array[rand_i]

    return partition(array, start, end)

def partition(array, start, end):
    pivot = array[end]
    i = start - 1

    for j in range(start, end):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[end], array[i+1] = array[i+1], array[end]

    return i+1

def random_quick_sort(array, start, end):
    if start < end:
        pivot_i = random_partition(array, start, end)

        random_quick_sort(array, start, pivot_i-1)
        random_quick_sort(array, pivot_i+1, end)


if __name__ == "__main__":
    array = [4234,234234,23,234,-134,123,41,578,-342,55,0.9323,0.325]
    # array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

    print("Before sorting: ", array)
    random_quick_sort(array, 0, len(array)-1)
    print("After sorting:  ", array)