ºÝºÝߣ

ºÝºÝߣ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
Downloaded 436 times
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

Recommended

Greedy Algorithm - Knapsack Problem
Greedy Algorithm - Knapsack ProblemGreedy Algorithm - Knapsack Problem
Greedy Algorithm - Knapsack Problem
Madhu Bala
?
Quick Sort , Merge Sort , Heap Sort
Quick Sort , Merge Sort , Heap SortQuick Sort , Merge Sort , Heap Sort
Quick Sort , Merge Sort , Heap Sort
Mohammed Hussein
?
What Is Dynamic Programming? | Dynamic Programming Explained | Programming Fo...
What Is Dynamic Programming? | Dynamic Programming Explained | Programming Fo...What Is Dynamic Programming? | Dynamic Programming Explained | Programming Fo...
What Is Dynamic Programming? | Dynamic Programming Explained | Programming Fo...
Simplilearn
?
Array data structure
Array data structureArray data structure
Array data structure
maamir farooq
?
Greedy algorithm
Greedy algorithmGreedy algorithm
Greedy algorithm
International Islamic University
?
Data structure and its types
Data structure and its typesData structure and its types
Data structure and its types
Navtar Sidhu Brar
?
Python-List.pptx
Python-List.pptxPython-List.pptx
Python-List.pptx
AnitaDevi158873
?
linked list in Data Structure, Simple and Easy Tutorial
linked list in Data Structure, Simple and Easy Tutoriallinked list in Data Structure, Simple and Easy Tutorial
linked list in Data Structure, Simple and Easy Tutorial
Afzal Badshah
?
Coin Change : Greedy vs Dynamic Programming
Coin Change : Greedy vs Dynamic ProgrammingCoin Change : Greedy vs Dynamic Programming
Coin Change : Greedy vs Dynamic Programming
Syeda Khadizatul maria
?
Algorithm: Quick-Sort
Algorithm: Quick-SortAlgorithm: Quick-Sort
Algorithm: Quick-Sort
Tareq Hasan
?
Applications of stack
Applications of stackApplications of stack
Applications of stack
eShikshak
?
Selection sort
Selection sortSelection sort
Selection sort
Jay Patel
?
Divide and Conquer - Part 1
Divide and Conquer - Part 1Divide and Conquer - Part 1
Divide and Conquer - Part 1
Amrinder Arora
?
Data Structures In Scala
Data Structures In ScalaData Structures In Scala
Data Structures In Scala
Knoldus Inc.
?
Selection sort
Selection sortSelection sort
Selection sort
stella D
?
minimum spanning trees Algorithm
minimum spanning trees Algorithm minimum spanning trees Algorithm
minimum spanning trees Algorithm
sachin varun
?
Counting Sort
Counting SortCounting Sort
Counting Sort
Faiza Saleem
?
Selection sort algorithm presentation, selection sort example using power point
Selection sort algorithm presentation, selection sort example using power point Selection sort algorithm presentation, selection sort example using power point
Selection sort algorithm presentation, selection sort example using power point
University of Science and Technology Chitttagong
?
Quick sort-170316064200
Quick sort-170316064200Quick sort-170316064200
Quick sort-170316064200
ifeanyiokeke3
?
Bfs new
Bfs newBfs new
Bfs new
sandeep54552
?
Introduction to data structure
Introduction to data structure Introduction to data structure
Introduction to data structure
NUPOORAWSARMOL
?
Binary tree
Binary treeBinary tree
Binary tree
Vanitha Chandru
?
Knapsack problem algorithm, greedy algorithm
Knapsack problem algorithm, greedy algorithmKnapsack problem algorithm, greedy algorithm
Knapsack problem algorithm, greedy algorithm
HoneyChintal
?
sparse matrix in data structure
sparse matrix in data structuresparse matrix in data structure
sparse matrix in data structure
MAHALAKSHMI P
?
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
Sahil Kumar
?
BFS
BFSBFS
BFS
jyothimonc
?
Array
ArrayArray
Array
Mehar_Aqib_Chudhary
?
List , tuples, dictionaries and regular expressions in python
List , tuples, dictionaries and regular expressions in pythonList , tuples, dictionaries and regular expressions in python
List , tuples, dictionaries and regular expressions in python
channa basava
?
3.8 quicksort
3.8 quicksort3.8 quicksort
3.8 quicksort
Krish_ver2
?
Insertion and merge sort
Insertion and merge sortInsertion and merge sort
Insertion and merge sort
Preetham Devisetty
?

More Related Content

What's hot (20)

Coin Change : Greedy vs Dynamic Programming
Coin Change : Greedy vs Dynamic ProgrammingCoin Change : Greedy vs Dynamic Programming
Coin Change : Greedy vs Dynamic Programming
Syeda Khadizatul maria
?
Algorithm: Quick-Sort
Algorithm: Quick-SortAlgorithm: Quick-Sort
Algorithm: Quick-Sort
Tareq Hasan
?
Applications of stack
Applications of stackApplications of stack
Applications of stack
eShikshak
?
Selection sort
Selection sortSelection sort
Selection sort
Jay Patel
?
Divide and Conquer - Part 1
Divide and Conquer - Part 1Divide and Conquer - Part 1
Divide and Conquer - Part 1
Amrinder Arora
?
Data Structures In Scala
Data Structures In ScalaData Structures In Scala
Data Structures In Scala
Knoldus Inc.
?
Selection sort
Selection sortSelection sort
Selection sort
stella D
?
minimum spanning trees Algorithm
minimum spanning trees Algorithm minimum spanning trees Algorithm
minimum spanning trees Algorithm
sachin varun
?
Counting Sort
Counting SortCounting Sort
Counting Sort
Faiza Saleem
?
Selection sort algorithm presentation, selection sort example using power point
Selection sort algorithm presentation, selection sort example using power point Selection sort algorithm presentation, selection sort example using power point
Selection sort algorithm presentation, selection sort example using power point
University of Science and Technology Chitttagong
?
Quick sort-170316064200
Quick sort-170316064200Quick sort-170316064200
Quick sort-170316064200
ifeanyiokeke3
?
Bfs new
Bfs newBfs new
Bfs new
sandeep54552
?
Introduction to data structure
Introduction to data structure Introduction to data structure
Introduction to data structure
NUPOORAWSARMOL
?
Binary tree
Binary treeBinary tree
Binary tree
Vanitha Chandru
?
Knapsack problem algorithm, greedy algorithm
Knapsack problem algorithm, greedy algorithmKnapsack problem algorithm, greedy algorithm
Knapsack problem algorithm, greedy algorithm
HoneyChintal
?
sparse matrix in data structure
sparse matrix in data structuresparse matrix in data structure
sparse matrix in data structure
MAHALAKSHMI P
?
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
Sahil Kumar
?
BFS
BFSBFS
BFS
jyothimonc
?
Array
ArrayArray
Array
Mehar_Aqib_Chudhary
?
List , tuples, dictionaries and regular expressions in python
List , tuples, dictionaries and regular expressions in pythonList , tuples, dictionaries and regular expressions in python
List , tuples, dictionaries and regular expressions in python
channa basava
?
Coin Change : Greedy vs Dynamic Programming
Coin Change : Greedy vs Dynamic ProgrammingCoin Change : Greedy vs Dynamic Programming
Coin Change : Greedy vs Dynamic Programming
Syeda Khadizatul maria
?
Algorithm: Quick-Sort
Algorithm: Quick-SortAlgorithm: Quick-Sort
Algorithm: Quick-Sort
Tareq Hasan
?
Applications of stack
Applications of stackApplications of stack
Applications of stack
eShikshak
?
Selection sort
Selection sortSelection sort
Selection sort
Jay Patel
?
Divide and Conquer - Part 1
Divide and Conquer - Part 1Divide and Conquer - Part 1
Divide and Conquer - Part 1
Amrinder Arora
?
Data Structures In Scala
Data Structures In ScalaData Structures In Scala
Data Structures In Scala
Knoldus Inc.
?
Selection sort
Selection sortSelection sort
Selection sort
stella D
?
minimum spanning trees Algorithm
minimum spanning trees Algorithm minimum spanning trees Algorithm
minimum spanning trees Algorithm
sachin varun
?
Counting Sort
Counting SortCounting Sort
Counting Sort
Faiza Saleem
?
Selection sort algorithm presentation, selection sort example using power point
Selection sort algorithm presentation, selection sort example using power point Selection sort algorithm presentation, selection sort example using power point
Selection sort algorithm presentation, selection sort example using power point
University of Science and Technology Chitttagong
?
Quick sort-170316064200
Quick sort-170316064200Quick sort-170316064200
Quick sort-170316064200
ifeanyiokeke3
?
Bfs new
Bfs newBfs new
Bfs new
sandeep54552
?
Introduction to data structure
Introduction to data structure Introduction to data structure
Introduction to data structure
NUPOORAWSARMOL
?
Binary tree
Binary treeBinary tree
Binary tree
Vanitha Chandru
?
Knapsack problem algorithm, greedy algorithm
Knapsack problem algorithm, greedy algorithmKnapsack problem algorithm, greedy algorithm
Knapsack problem algorithm, greedy algorithm
HoneyChintal
?
sparse matrix in data structure
sparse matrix in data structuresparse matrix in data structure
sparse matrix in data structure
MAHALAKSHMI P
?
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
ADA - Minimum Spanning Tree Prim Kruskal and Dijkstra
Sahil Kumar
?
BFS
BFSBFS
BFS
jyothimonc
?
Array
ArrayArray
Array
Mehar_Aqib_Chudhary
?
List , tuples, dictionaries and regular expressions in python
List , tuples, dictionaries and regular expressions in pythonList , tuples, dictionaries and regular expressions in python
List , tuples, dictionaries and regular expressions in python
channa basava
?

Viewers also liked (7)

3.8 quicksort
3.8 quicksort3.8 quicksort
3.8 quicksort
Krish_ver2
?
Insertion and merge sort
Insertion and merge sortInsertion and merge sort
Insertion and merge sort
Preetham Devisetty
?
Insertion sort
Insertion sortInsertion sort
Insertion sort
Lovely Professional University
?
Insertion Sort Algorithm
Insertion Sort AlgorithmInsertion Sort Algorithm
Insertion Sort Algorithm
Gail Carmichael
?
Divide and conquer - Quick sort
Divide and conquer - Quick sortDivide and conquer - Quick sort
Divide and conquer - Quick sort
Madhu Bala
?
Safe laparoscopy
Safe laparoscopySafe laparoscopy
Safe laparoscopy
Mamdouh Sabry
?
Quick sort Algorithm Discussion And Analysis
Quick sort Algorithm Discussion And AnalysisQuick sort Algorithm Discussion And Analysis
Quick sort Algorithm Discussion And Analysis
SNJ Chaudhary
?
3.8 quicksort
3.8 quicksort3.8 quicksort
3.8 quicksort
Krish_ver2
?
Insertion and merge sort
Insertion and merge sortInsertion and merge sort
Insertion and merge sort
Preetham Devisetty
?
Insertion sort
Insertion sortInsertion sort
Insertion sort
Lovely Professional University
?
Insertion Sort Algorithm
Insertion Sort AlgorithmInsertion Sort Algorithm
Insertion Sort Algorithm
Gail Carmichael
?
Divide and conquer - Quick sort
Divide and conquer - Quick sortDivide and conquer - Quick sort
Divide and conquer - Quick sort
Madhu Bala
?
Safe laparoscopy
Safe laparoscopySafe laparoscopy
Safe laparoscopy
Mamdouh Sabry
?
Quick sort Algorithm Discussion And Analysis
Quick sort Algorithm Discussion And AnalysisQuick sort Algorithm Discussion And Analysis
Quick sort Algorithm Discussion And Analysis
SNJ Chaudhary
?

More from Yoshi Watanabe (8)

Create images with AI models.pptx
Create images with AI models.pptxCreate images with AI models.pptx
Create images with AI models.pptx
Yoshi Watanabe
?
Git ¥Õ¥§¥Ã¥Á
Git ¥Õ¥§¥Ã¥ÁGit ¥Õ¥§¥Ã¥Á
Git ¥Õ¥§¥Ã¥Á
Yoshi Watanabe
?
Git ¥ê¥Ù©`¥¹
Git ¥ê¥Ù©`¥¹Git ¥ê¥Ù©`¥¹
Git ¥ê¥Ù©`¥¹
Yoshi Watanabe
?
Git ¥³¥ó¥Õ¥ê¥¯¥È
Git ¥³¥ó¥Õ¥ê¥¯¥ÈGit ¥³¥ó¥Õ¥ê¥¯¥È
Git ¥³¥ó¥Õ¥ê¥¯¥È
Yoshi Watanabe
?
Find n th fibonacci iteratively - illustrated walkthrough
Find n th fibonacci iteratively - illustrated walkthroughFind n th fibonacci iteratively - illustrated walkthrough
Find n th fibonacci iteratively - illustrated walkthrough
Yoshi Watanabe
?
Binary search tree exact match - illustrated walkthrough
Binary search tree exact match - illustrated walkthroughBinary search tree exact match - illustrated walkthrough
Binary search tree exact match - illustrated walkthrough
Yoshi Watanabe
?
Binary search: illustrated step-by-step walk through
Binary search: illustrated step-by-step walk throughBinary search: illustrated step-by-step walk through
Binary search: illustrated step-by-step walk through
Yoshi Watanabe
?
Merge sort: illustrated step-by-step walk through
Merge sort: illustrated step-by-step walk throughMerge sort: illustrated step-by-step walk through
Merge sort: illustrated step-by-step walk through
Yoshi Watanabe
?
Create images with AI models.pptx
Create images with AI models.pptxCreate images with AI models.pptx
Create images with AI models.pptx
Yoshi Watanabe
?
Git ¥Õ¥§¥Ã¥Á
Git ¥Õ¥§¥Ã¥ÁGit ¥Õ¥§¥Ã¥Á
Git ¥Õ¥§¥Ã¥Á
Yoshi Watanabe
?
Git ¥ê¥Ù©`¥¹
Git ¥ê¥Ù©`¥¹Git ¥ê¥Ù©`¥¹
Git ¥ê¥Ù©`¥¹
Yoshi Watanabe
?
Git ¥³¥ó¥Õ¥ê¥¯¥È
Git ¥³¥ó¥Õ¥ê¥¯¥ÈGit ¥³¥ó¥Õ¥ê¥¯¥È
Git ¥³¥ó¥Õ¥ê¥¯¥È
Yoshi Watanabe
?
Find n th fibonacci iteratively - illustrated walkthrough
Find n th fibonacci iteratively - illustrated walkthroughFind n th fibonacci iteratively - illustrated walkthrough
Find n th fibonacci iteratively - illustrated walkthrough
Yoshi Watanabe
?
Binary search tree exact match - illustrated walkthrough
Binary search tree exact match - illustrated walkthroughBinary search tree exact match - illustrated walkthrough
Binary search tree exact match - illustrated walkthrough
Yoshi Watanabe
?
Binary search: illustrated step-by-step walk through
Binary search: illustrated step-by-step walk throughBinary search: illustrated step-by-step walk through
Binary search: illustrated step-by-step walk through
Yoshi Watanabe
?
Merge sort: illustrated step-by-step walk through
Merge sort: illustrated step-by-step walk throughMerge sort: illustrated step-by-step walk through
Merge sort: illustrated step-by-step walk through
Yoshi Watanabe
?

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
AboutCopyright
? 2025 ºÝºÝߣ