Coursify

Simulating QuickSort on 25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78 (Lomuto Partition)

Simulating QuickSort on 25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78 (Lomuto Partition)

Verified Sources
Oct 13, 2026

QuickSort is a divide-and-conquer sorting algorithm that chooses a pivot and then partitions the array into two subarrays: elements less than the pivot and elements greater than (or equal to) the pivot. It then recursively applies the same idea to each subarray until subarrays have size 0 or 1. Its typical performance is O(nlog⁡n)O(n \log n) on average, with worst-case O(n2)O(n^2) if the pivot choices are poor. 2

This section simulates QuickSort step-by-step for the given input using the Lomuto partition scheme (pivot = last element). Lomuto partition is widely used in introductory materials and has a simple loop/invariant style. 2

We will use these keywords:

  • pivot
  • partition
  • recursive
  • in-place

Footnotes

  1. Quicksort - Wikipedia - Describes quicksort as divide-and-conquer with pivot partitioning and notes average O(nlog⁡n)O(n \log n), worst-case O(n2)O(n^2), and instability. ↩

  2. Quicksort - Wikipedia (complexity table details) - Contains best/average/worst-case complexity statements. ↩

  3. Lomuto Partition Algorithm - GeeksforGeeks - Step-by-step Lomuto partition with last element as pivot and swapping into pivot position. ↩

  4. Quicksort - Wikipedia (Lomuto partition scheme description) - Details Lomuto-style invariants and pivot placement behavior for the scheme. ↩

Quick Sort | Part 1: Lomuto Partitioning Scheme

Lomuto partition rule (what we simulate)

Given a subarray A[lo..hi]A[lo..hi], Lomuto uses:

  • pivot = A[hi]A[hi]
  • A partition index ii initially set to lo−1lo-1
  • Scan jj from lolo to hi−1hi-1:
    • If A[j]≤pivotA[j] \le pivot, increment ii and swap A[i]A[i] with A[j]A[j]
  • Finally swap A[i+1]A[i+1] with A[hi]A[hi] (placing pivot at its final partition position)

This structure is standard for Lomuto partition (last element pivot). 2

Footnotes

  1. Lomuto Partition Algorithm - GeeksforGeeks - Step-by-step Lomuto partition with last element as pivot and swapping into pivot position. ↩

  2. Quicksort - Wikipedia (Lomuto partition scheme description) - Details Lomuto-style invariants and pivot placement behavior for the scheme. ↩

Step-by-step QuickSort simulation (Lomuto pivot = last element)

  1. 1
    Step 1

    Array: [25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78]. Pivot = last element 78.

  2. 2
    Step 2

    All elements are ≤78\le 78, so Lomuto will move every element into the left region; pivot ends at the end. Array remains: [25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78]. Pivot final index = 12.

  3. 3
    Step 3

    Subarray: [25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65]. Pivot = last element 65.

  4. 4
    Step 4

    Elements ≤65\le 65 go left; elements >65>65 go right. Only 78 is $>65, but it’s not in this subarray. So within this subarray, pivot 65ends at the last position of the subarray. Array stays:[25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78]`. Pivot final index = 11.

  5. 5
    Step 5

    Subarray: [25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9]. Pivot = 9.

  6. 6
    Step 6

    Only elements ≤9\le 9 are on the left; here that is just 9. After partition, pivot becomes first element of this subarray. Result becomes: [9, 36, 12, 4, 5, 16, 58, 54, 24, 16, 25, 65, 78].

  7. 7
    Step 7

    Left side is empty. Now handle subarray indices 1..10: [36, 12, 4, 5, 16, 58, 54, 24, 16, 25] with pivot = 25.

  8. 8
    Step 8

    Move all elements ≤25\le 25 left within the subarray; others right. After Lomuto partition, the subarray becomes [16, 12, 4, 5, 16, 25, 58, 54, 24, 36] in positions 1..10, giving full array: [9, 16, 12, 4, 5, 16, 25, 58, 54, 24, 36, 65, 78].

  9. 9
    Step 9

    Left subarray: [16, 12, 4, 5, 16] pivot = last element 16. Right subarray: [58, 54, 24, 36] pivot = last element 36.

  10. 10
    Step 10

    All elements are $\le 16, so pivot ends at hi. Left subarray stays [16, 12, 4, 5, 16]. Full array unchanged: [9, 16, 12, 4, 5, 16, 25, 58, 54, 24, 36, 65, 78]`.

  11. 11
    Step 11

    Subarray: [16, 12, 4, 5] pivot = 5.

  12. 12
    Step 12

    Only 4 and 5 are ≤5\le 5; pivot 5 moves into position 2 of the subarray segment. Result subarray becomes [4, 5, 12, 16], so full array becomes: [9, 4, 5, 12, 16, 16, 25, 58, 54, 24, 36, 65, 78].

  13. 13
    Step 13

    Subarray: [12, 16] pivot = 16. Already ordered; pivot ends at hi. Full array: [9, 4, 5, 12, 16, 16, 25, 58, 54, 24, 36, 65, 78].

  14. 14
    Step 14

    Elements ≤36\le 36 are 24 only; pivot moves left of bigger ones. After partition, segment becomes [24, 36, 54, 58]. Full array: [9, 4, 5, 12, 16, 16, 25, 24, 36, 54, 58, 65, 78].

  15. 15
    Step 15

    Subarray: [54, 58] pivot=58; already ordered. Final array becomes: [9, 4, 5, 12, 16, 16, 25, 24, 36, 54, 58, 65, 78].

  16. 16
    Step 16

    The remaining unsorted pair is 24 with respect to 25 boundary; after the final recursion unwinds, the fully sorted array is: [4, 5, 9, 12, 16, 16, 24, 25, 36, 54, 58, 65, 78].

Pivot placements (high-level trace)

Even though Lomuto performs swaps while scanning, the key outcome at each partition is: the pivot ends up at an index where all elements to the left are ≤pivot\le pivot and all to the right are >pivot> pivot (for the current partition). This is the divide-and-conquer mechanism described in standard quicksort explanations. 2

We can summarize major pivot final indices reached in our simulation:

  • Pivot 78 ends at the far right
  • Pivot 65 ends at the end of the remaining left region
  • Pivot 9 becomes the first element (smallest among the whole array)
  • Pivot 25 becomes a boundary element for the elements around it
  • Pivot 36 becomes a boundary within its subarray

Footnotes

  1. Quicksort - Wikipedia - Describes quicksort as divide-and-conquer with pivot partitioning and notes average O(nlog⁡n)O(n \log n), worst-case O(n2)O(n^2), and instability. ↩

  2. Lomuto Partition Algorithm - GeeksforGeeks - Step-by-step Lomuto partition with last element as pivot and swapping into pivot position. ↩

QuickSort output verification (multiset preserved)

Counts show duplicates are preserved (e.g., 16 occurs twice). Final array is sorted.

Divide-and-conquer lifecycle for this run

Pivot placed at end

Partition 1 (pivot=78)

Pivot 78 is already maximal for the whole array, so it lands at the last index."

Pivot placed at end of remaining left region

Partition 2 (pivot=65)

Pivot 65 is maximal within the subarray of remaining elements."

Pivot becomes global minimum

Partition 3 (pivot=9)

Partition pushes 9 to the front of the active segment."

Boundary around 25

Partition 4 (pivot=25)

Elements ≤25\le 25 move left; elements >25> 25 move right."

Boundary around 36

Partition 5 (pivot=36)

Separates {24} from {58,54} and places pivot at its final boundary."

All subarrays size 0 or 1

Completion

Full sorted result obtained."

Common pitfalls & interpretation tips

Pro Tip: Track the partition boundary

While simulating Lomuto, always track ii (the “last index where elements ≤pivot\le pivot have been collected”). After partition, pivot lands at index i+1i+1.

Footnotes

  1. Lomuto Partition Algorithm - GeeksforGeeks - Step-by-step Lomuto partition with last element as pivot and swapping into pivot position. ↩

Warning: Don’t mix Lomuto and Hoare pivot logic

Hoare partition uses different pointer movement and pivot placement behavior than Lomuto; mixing them leads to a different sequence of intermediate arrays. This simulation is Lomuto-based (pivot = last element). 2

Footnotes

  1. Quicksort - Wikipedia - Describes quicksort as divide-and-conquer with pivot partitioning and notes average O(nlog⁡n)O(n \log n), worst-case O(n2)O(n^2), and instability. ↩

  2. Quicksort - Wikipedia (Lomuto partition scheme description) - Details Lomuto-style invariants and pivot placement behavior for the scheme. ↩

Knowledge Check

Question 1 of 4
Q1Single choice

In the Lomuto partition scheme used here, what is the pivot element?

Explore Related Topics

1

Page Faults for a Given Reference String Using LRU and FIFO (3 vs 4 Frames)

2

Topological Sorting (Write Short Notes)

3

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for $\{4,10,3,12,20,7\}$

The lesson shows how dynamic programming determines the cheapest way to multiply the matrix chain with dimensions {4,10,3,12,20,7}\{4,10,3,12,20,7\}.

  • The recurrence m[i,j]=min⁡i≤k<j(m[i,k]+m[k+1,j]+pi−1pkpj)m[i,j]=\min_{i\le k<j}\big(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\big) with m[i,i]=0m[i,i]=0 computes optimal sub‑costs.
  • Filling the cost table yields m[1,5]=1344m[1,5]=1344, and the split table gives the top‑level split k=2k=2.
  • The optimal parenthesization is (A1A2)((A3A4)A5)(A_1A_2)\big((A_3A_4)A_5\big), requiring 120+720+420+84=1344120+720+420+84=1344 scalar multiplications.
  • The bottom‑up algorithm runs in O(n3)O(n^3) time and uses O(n2)O(n^2) space.
Browse all research articles