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 will select a randomly chosen element from the subarray A(p, r) We do so by first exchanging element A(r) with an element chosen at random from A(p, r). By randomly sampling the range p…r, we ensure that the pivot element x = A[r] is equally likely to be any of the (r-p+1) elements in the subarray.

Because we randomly choose the pivot element, we expect the split of the input array to be reasonably well balanced 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)