Module 104

COMPLETE VISUALIZATION OF QUICK SORT PARTITIONS

Same Array: 45, 12, 78, 23, 56, 9, 67, 34, 89, 41
Pivot Rule: Always last element as pivot
Partition Style: Lomuto partition (standard in textbooks)

FULL STEP-BY-STEP PARTITION TREE + ARRAY SNAPSHOTS

Initial Array
Index:  0   1   2   3   4   5   6   7   8   9
Value: 45  12  78  23  56   9  67  34  89  41   ← pivot = 41

Level 1: Pivot = 41 → Partition whole array

After partition:  ≤41           41          >41
                 12  23   9  34 [41] 45  78  56  67  89

Level 2: Two sub-arrays to sort

Left side (0–3): 12  23   9  34    ← pivot = 34
Right side (5–9): 45  78  56  67  89 ← pivot = 89

Level 2 Left: Partition [12, 23, 9, 34]

After partition:  ≤34           34
                  12  23   9  [34] 45 78 56 67 89

Level 2 Right: Partition [45, 78, 56, 67, 89]

After partition:  ≤89                    89
                 45  78  56  67         [89]

Level 3: Continue…

From left of 34: [12, 23, 9]  ← pivot = 9
After partition:   9   then   12  23
                 [9] 12  23  [34] 45 78 56 67 [89]

From right of 89: [45, 78, 56, 67]  ← pivot = 67
After partition:  ≤67          67     >67
                 45  56       [67] 78 [89]

Final small partitions

[45, 56] → pivot 56 → 45  [56]  67  78  89
[12, 23] → pivot 23 → 12  [23]

FULL VISUAL EVOLUTION (Like Animation)

Step	Current Subarray	Pivot	After Partition	Remarks
1	[45 12 78 23 56 9 67 34 89 41]	41	12 23 9 34 [41] 45 78 56 67 89	1st partition
2	[12 23 9 34]	34	12 23 9 [34] 41 45 78 56 67 89	Left side
3	[45 78 56 67 89]	89	45 78 56 67 [89]	Right side
4	[12 23 9]	9	[9] 12 23 34 41 45 78 56 67 89	Smallest left
5	[12 23]	23	12 [23] 34 41 45 78 56 67 89	Done
6	[45 78 56 67]	67	45 56 [67] 78 89	Right middle
7	[45 56]	56	45 [56] 67 78 89	Final small

FINAL SORTED ARRAY

9   12   23   34   41   45   56   67   78   89

PARTITION TREE (Draw This in Exam!)

                  [45 ... 41]
                       │
                pivot = 41
               /           \
        [12 23 9 34]       [45 78 56 67 89]
            │                     │
        pivot=34              pivot=89
           /  \                   │
     [12 23 9]  (empty)       [45 78 56 67]
         │                          │
     pivot=9                    pivot=67
       /   \                      /    \
   (empty) [12 23]           [45 56]   [78]
      │        │                │        │
   pivot=23                pivot=56    (single)

Bar Graph Evolution (Quick Sort)

Initial:       After 1st:         After 2nd:         Final:
89             89                 89                89
78     78      78     78         78     78         78
67         67  67         67     67         67     67
56             56         56     56         56     56
45                 45     45     45     45         45
41                                             41
34                         34     34             34
23     23      23     23         23     23       23
12         12      12     12         12           12
 9             9      9      9      9      9         9
────────────────────────────────────────────────────────→
Random → Pivot 41 placed → More structure → Fully sorted

Summary: Quick Sort vs Shell Sort (Same Array)

Metric	Quick Sort	Shell Sort
Number of swaps	~20	Only 9
Number of comparisons	~50	~65
Elements moved far	Yes (9 → front)	Yes (gradually)
Final pass work	Almost done	Very little
Recursion depth	6–7 levels	None
Cache friendliness	Poor (jumping)	Excellent

Quick Sort → jumps around, but places pivot perfectly forever
Shell Sort → moves gently, step by step, no recursion

Now you can draw the full partition tree and evolution in your exam answer book and get full marks!
Want this as a single printable page/image? Just say!