#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/quicksort-partitioning

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/quicksort-partitioning

Repovive

QuickSort - Partitioning - Sorting Algorithms | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

QuickSort - Partitioning

The Lomuto partition scheme.

Lomuto partition rearranges around pivot: $1.$ Choose last as pivot.

$2.$ Index $i$ tracks boundary of $<$ pivot.

$3.$ Scan with $j$ . If $arr[j] < pivot$ , swap with $arr[i+1]$ , increment $i$ .

$4.$ Swap pivot to $i+1$ .

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j from low to high-1:
        if arr[j] < pivot:
            i++; swap(arr[i], arr[j])
    swap(arr[i+1], arr[high])
    return i + 1

Pivot ends at final sorted position.