# Randomized Sort

Updated:

⚠️ 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)



Tags: