ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Quicksort: illustrated step-by-step walk through

?
?
Yoshi Watanabe
Yoshi Watanabe

A step-by-step illustration of Quicksort to help you walk through a series of operations. Illustration is accompanied by actual code with bold line indicating the current operation.

1 of 58
Download to read offline
Quicksort algorithm Illustrated walkthrough
Partition function This function does the most of the heavy lifting, so we look at it first, then see it in the context of Quicksort algorithm
[0] [1] [2] [3] [4] [5] 12 7 14 9 10 11 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex;
store Index i begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i 0 store Index 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 0 0<5 is true 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 0 12 <= 11 is false 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 1 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 1 7 <= 11 is true 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 1 0 begin 12 Swap last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 1 0 begin 7 Swap last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i 1 store Index 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 2 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 2 2<5 is true 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 2 14 <= 11 is fase 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 3 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 3 3<5 is true 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 3 9 <= 11 is true 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
Swap i store Index 3 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
Swap i store Index 3 1 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 3 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
4<5 is true store Index i 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
10 <= 11 is true store Index i 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
Swap i store Index 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
Swap i store Index 4 2 begin 7 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 4 3 begin 7 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
i store Index 3 begin 7 5 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
4<5 is false store Index i 3 begin 7 5 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
Swap i store Index 3 begin 7 5 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
Swap i store Index 3 begin 7 5 last 9 10 11 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 12
i store Index 3 begin 7 5 last 9 10 11 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 12
Quicksort algorithm Now we use Partition in the context of Quicksort
pivot Index [0] [1] [2] [3] [4] 9 7 5 11 12 [5] 2 [6] 14 [7] [8] 3 int pivotIndex = 0; if (begin < last) { pivotIndex = Partition(array, begin, last); QuickSort(array, begin, pivotIndex - 1); QuickSort(array, pivotIndex + 1, last); } else { return; } 10 [9] 6
pivot Index 0 9 7 5 11 12 2 14 3 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 6
0<9 is true pivot Index 0 9 7 5 11 12 2 14 3 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 6
Partition 0..9 pivot Index 0 9 7 5 11 12 2 14 3 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 6
these are <= 6 these are > 6 pivot Index 5 2 3 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #0 pivot Index 5 2 3 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
pivot Index Call Stack #1 Call Stack #0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
pivot Index 0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
0<2 is true pivot Index 0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Partition 0..2 pivot Index 0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #1 Call Stack #0 pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 pivot Index Call Stack #1 Call Stack #0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 0<0 is false Call Stack #1 Call Stack #0 pivot Index 0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #1 Call Stack #0 pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 pivot Index Call Stack #1 Call Stack #0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 2 0 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
0<0 is false Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 2 0 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 2 0 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
Call Stack #1 Call Stack #0 pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } return (at the end of the function. Implicit ¡®return¡¯ statement 10 11
We are done with these elements! Call Stack #0 pivot Index 2 3 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
pivot Index Call Stack #1 Call Stack #0 Walkthrough ends here. The right hand side is also sorted as it recursively calls Quicksort. 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11

More Related Content

Quicksort: illustrated step-by-step walk through

  • 2. Partition function This function does the most of the heavy lifting, so we look at it first, then see it in the context of Quicksort algorithm
  • 3. [0] [1] [2] [3] [4] [5] 12 7 14 9 10 11 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex;
  • 4. store Index i begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 5. i store Index 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 6. i 0 store Index 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 7. i store Index 0 0<5 is true 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 8. i store Index 0 12 <= 11 is false 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 9. i store Index 1 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 10. i store Index 1 7 <= 11 is true 0 begin 12 last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 11. i store Index 1 0 begin 12 Swap last 7 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 12. i store Index 1 0 begin 7 Swap last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 13. i 1 store Index 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 14. i store Index 2 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 15. i store Index 2 2<5 is true 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 16. i store Index 2 14 <= 11 is fase 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 17. i store Index 3 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 18. i store Index 3 3<5 is true 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 19. i store Index 3 9 <= 11 is true 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 20. Swap i store Index 3 1 begin 7 last 12 14 9 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 21. Swap i store Index 3 1 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 22. i store Index 3 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 23. i store Index 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 24. 4<5 is true store Index i 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 25. 10 <= 11 is true store Index i 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 26. Swap i store Index 4 2 begin 7 last 9 14 12 10 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 27. Swap i store Index 4 2 begin 7 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 28. i store Index 4 3 begin 7 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 29. i store Index 3 begin 7 5 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 30. 4<5 is false store Index i 3 begin 7 5 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 31. Swap i store Index 3 begin 7 5 last 9 10 12 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 11
  • 32. Swap i store Index 3 begin 7 5 last 9 10 11 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 12
  • 33. i store Index 3 begin 7 5 last 9 10 11 14 int storeIndex = begin; for (int i = begin; i < last; i++) { if (array[i] <= array[last]) { Swap(array, i, storeIndex); storeIndex = storeIndex + 1; } } Swap(array, storeIndex, last); return storeIndex; 12
  • 34. Quicksort algorithm Now we use Partition in the context of Quicksort
  • 35. pivot Index [0] [1] [2] [3] [4] 9 7 5 11 12 [5] 2 [6] 14 [7] [8] 3 int pivotIndex = 0; if (begin < last) { pivotIndex = Partition(array, begin, last); QuickSort(array, begin, pivotIndex - 1); QuickSort(array, pivotIndex + 1, last); } else { return; } 10 [9] 6
  • 36. pivot Index 0 9 7 5 11 12 2 14 3 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 6
  • 37. 0<9 is true pivot Index 0 9 7 5 11 12 2 14 3 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 6
  • 38. Partition 0..9 pivot Index 0 9 7 5 11 12 2 14 3 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 6
  • 39. these are <= 6 these are > 6 pivot Index 5 2 3 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 40. Call Stack #0 pivot Index 5 2 3 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 41. pivot Index Call Stack #1 Call Stack #0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 42. pivot Index 0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 43. 0<2 is true pivot Index 0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 44. Partition 0..2 pivot Index 0 5 2 3 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 45. pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 46. Call Stack #1 Call Stack #0 pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 47. Call Stack #2 pivot Index Call Stack #1 Call Stack #0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 48. Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 49. Call Stack #2 0<0 is false Call Stack #1 Call Stack #0 pivot Index 0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 50. Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 51. Call Stack #1 Call Stack #0 pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 52. Call Stack #2 pivot Index Call Stack #1 Call Stack #0 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 53. Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 2 0 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 54. 0<0 is false Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 2 0 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 55. Call Stack #2 Call Stack #1 Call Stack #0 pivot Index 2 0 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 56. Call Stack #1 Call Stack #0 pivot Index 1 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } return (at the end of the function. Implicit ¡®return¡¯ statement 10 11
  • 57. We are done with these elements! Call Stack #0 pivot Index 2 3 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11
  • 58. pivot Index Call Stack #1 Call Stack #0 Walkthrough ends here. The right hand side is also sorted as it recursively calls Quicksort. 2 3 5 6 12 7 14 9 int pivotIndex = 0; if (start < end) { pivotIndex = Partition(array, start, end); QuickSort(array, start, pivotIndex - 1); QuickSort(array, pivotIndex + 1, end); } else { return; } 10 11