Data Structures & Algorithms - Lecture 1

Data Structures and Algorithms using C++ programming language.

1. Data Structures and
Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024
C++

2. Resources
•Textbooks:
•Data Structures and Algorithm Analysis in C++ 4th Ed. by Mark Allen
•Introduction to the Design and Analysis of Algorithms 3rd Ed. by Levitin
•Grokking Algorithms by Aditya Y. Bhargava
•Other Resources

3. The topics of today’s lecture:
Agenda

5. What are Data Structures?
–A data structure is a branch of computer science to store and organize data.
–Data structures are the building blocks of any program or software.
–Choosing the appropriate data structure for a program is the most difficult task for
a programmer.
–Data structures give us the possibility to manage large amounts of data efficiently
for uses such as large databases, searching, sorting, and internet indexing services.
–Data structures are essential for managing and organizing data for fast and
powerful algorithms by to reduce complexity and increase efficiency.
A simple analogy is to consider a
family tree, this is an example of
a data structure.

6. Primitive Data Structuresare basic data structures provided by programming languages.
Classification of Data Structures
Abstract Data Structures are higher-level data structures that are built using primitive
data types and provide more complex and specialized operations.
▪Integer, float, char, …, etc.
▪Array, Linked lists, Stacks, Queues, Trees, Graphs, …, etc.
Linear Non-Linear

7. Float Double
Abstract Data Types(ADT)

8. Some obvious benefits of knowing data structures
–You will be able to write efficient (fast and memory-efficient) code for solving cornerstone
computational problems.
–Efficiently handle Big Data.
–Secure high-profile industry jobs and internships.
–Advanced studies.
“Algorithms + Data Structures = Programs” – Niklaus Wirth
Most data structures we will study will be designed from scratch to illustrate how
they work under the hood. But in industry, programmers should use the built-in
ones for precision and to save time.

9. What is an Algorithm?
–An algorithm is a finite set of instructions which to be followed to solve a particular
problem.
–There can be more than one algorithm to solve a given problem.
–Usually written in pseudocode form and can be implemented using different
programming languages.
–We employ mathematical analysis techniques to analyze algorithms independently.
–There’re two aspects of Algorithm Performance:
Time
•How to estimate the time required
for an algorithm
•How to reduce the time required
Space
•Data structures take memory space
•What kind of data structures can be used?
•How does choice of data structure affect the runtime?

10. Example: Adding two numbers (Algorithm)
1.Get the first number.
2.Get the second number.
3.Add the first and second numbers together.
4.Display the result of the addition.
5.End the program.
First number = 5
Second number = 10
Addition = First number + second number
= 5 + 10
= 15

11. First number = 5
Second number = 10
Addition = First number + second number
= 5 + 10
= 15
Algorithm

13. The Execution Time of Algorithms
Example: Simple Loop
int i = 1;
int sum = 0;
while (i <= n) {
i = i + 1;
sum = sum + i;
}
Cost Times
1 1
1 1
1 n + 1
2 n
2 n
Total cost = 1 + 1+??????+1+ 2?????? + 2??????=5??????+3
The time required for this algorithm is
proportional to ??????

14. The Execution Time of Algorithms
Example: Simple Loop
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
Cost Times
1 1
1 + 1 + 11 + (n + 1) + n
2 n
1 1
Total cost = 1+2+2??????+2??????+1=4??????+4
The time required for this algorithm is
proportional to ??????

15. The Execution Time of Algorithms
int i = 1;
int sum = 0;
while (i <= n) {
j = 1;
while (j <= n) {
sum = sum + i;
j = j + 1;
}
i = i + 1;
}
Cost Times
1 1
1 1
1 n + 1
1 n
1 n * (n + 1)
2 n * (n)
2 n * (n)
2 n
Total cost =1+1+??????+1+??????+????????????+1+??????∗??????∗2+??????∗??????∗2+2?????? =5??????
2
+5??????+3
The time required for this algorithm is proportional to
??????
2
Example: Nested Loops

16. The Execution Time of Algorithms
if (a > b && c < d) {
for (j = 0; j < n; j++)
a[j] += j;
}
else {
for (j = 0; j < n; j++)
for(k = 1; k <= n; k++)
a[j] += k * j;
}
Cost Times
1 + 1 + 1 1
1 + 1 + 1 1 + (n + 1) + n
2 n
1 + 1 + 1 1 + (n + 1) + n
1 + 1 + 1n*(1 + (n + 1) + n)
3 n * (n)
Maximum cost is for S2 which is
proportional to ??????
2
Example: if-else statement
S1
S2

17. The Execution Time of Algorithms
if (a > b && c < d) {
for (j = 0; j < n; j++)
a[j] += j;
}
else {
for (j = 0; j < n; j++)
for(k = 1; k <= n; k++)
a[j] += k * j;
}
Cost Times
1 + 1 + 1 1
1 + 1 + 1 1 + (n + 1) + n
2 n
1 + 1 + 1 1 + (n + 1) + n
1 + 1 + 1n*(1 + (n + 1) + n)
3 n * (n)
Maximum cost is for S2 which is
proportional to ??????
2
.
Example: if-else statement
S1
S2

18. The Execution Time of Algorithms
if (n > 3) {
print(n)
} else {
for(i = 1; i <= n; i*=2)
print(n)
}
Cost Times
1 1
1 1
1 + 1 + 11 + log n + log n
1 log n*(1)
Maximum cost is for S2 which is
proportional to log??????
Example: if-else statement
S1
S2

19. Operation: doesn’t depend on input size. O(1)
for/while Loops:
++ increment: i = i + 1, i = i + 2, i = i + 5
– – decrement: i = i - 1, i = i – 3, i = i – 10
multiplication: i = i * 2, i = i * 5
division: i = i / 2, i = i / 9
Conditions (if-else statements): maximum time of the conditions.
Summary
O(??????)
O(log??????)

20. Asymptotic Notations – The Big O Notation
–An algorithm’s proportional time requirement is known as growth rate.
–The function ??????(??????) is called the algorithm’s growth-rate function.
–Since the capital ‘O’ is used in the notation, this notation is called the Big O notation.
•If Algorithm ‘A’ requires time proportional to ??????
2
, it is ??????(??????
2
).
•If Algorithm ‘A’ requires time proportional to ??????
2
, it is ??????(??????).

21. Orders of growth from the lowest to highest.
O1 Best
Olog??????
O2log??????
O(??????)
O??????log??????
O(??????
2
)
O(??????
3
)
O(2
??????
)
O(??????!) Worst

22. Common orders of magnitude

23. What to Analyze?
–An algorithm can require different times to solve different problems of the same size.
–Worst-Case Analysis (Big O): The maximum amount of time that an algorithm require to solve a
problem of size n.
–This gives an upper bound for the time complexity of an algorithm.
–Normally, we try to find worst-case behavior of an algorithm.
–Best-Case Analysis (Big ??????): The minimum amount of time that an algorithm require to solve a
problem of size n.
–The best-case behavior of an algorithm is NOT so useful.
–Average-Case Analysis (Big ??????): The average amount of time that an algorithm require to solve a
problem of size n.
–Sometimes, it is difficult to find the average-case behavior of an algorithm.
–We have to look at all possible data organizations of a given size n, and their distribution probabilities of
these organizations.
Worst-case analysis is more common than average-case analysis.

24. –An algorithm is considered stable if it preserves the relative order
of duplicate elements in its output as they appeared in its input.
Stability for algorithms

25. Algorithm Visualizer (algorithm-visualizer.net)

27. What is Sorting?
–Arranging the data in ascending or descending order is known as sorting.
–The best example of sorting can be phone numbers in our phones. If, they are not
maintained in an alphabetical order we would not be able to search any number
effectively.
–Sorting Algorithms:
1)Selection sort
2)Bubble sort
3)Insertion sort
4)Merge sort
5)Quicksort
7 2 5 1
1 2 5 7
Sorting

28. Brute-force

29. 1) Selection Sort
2 8 5 3 9 4 1
–The list is divided into two sub lists, sorted and unsorted.
–We find the smallest element from the unsorted sub-list and swap it with the element at the
beginning of the unsorted data.
–After each selection and swapping, the wall between the two sub-lists moves one element ahead,
increasing the number of sorted elements and decreasing the number of unsorted ones.
–A list of ?????? elements requires ??????−1 passes to completely rearrange the data.

30. Selection Sort Algorithm
1)Find the minimum value in the array.
2)Swap it with the first element of the array.
3)Move to the next position and repeat steps 1-2 for the remaining elements.
4)Continue until the entire array is sorted.
2 8 5 3 9 4 1

32. void selectionSort(int arr[], int n)
{
int minIdx;
for(inti = 0; i < n-1; i++)
{
minIdx = i;
for(intj = i + 1; j < n; j++)
if (arr[j] < arr[minIdx]) // Change '<' to '>' to sort in
descending order
minIdx = j;
swap(arr[minIdx], arr[i]);
}
}

33. #include <iostream>
using namespace std;
void selectionSort(int arr[], int n);
void swap(int& x, int& y);
void print(int arr[], int size);
int main()
{
int arr[] = { 2, 8, 5, 3, 9, 4, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "After Selection Sort: ";
print(arr, n);
return 0;
}
void selectionSort(int arr[], int n)
{
int minIdx;
for(inti = 0; i < n-1; i++)
{
minIdx = i;
for(intj = i + 1; j < n; j++)
if (arr[j] < arr[minIdx]) // Change '<' to '>' to sort in descending order
minIdx = j;
swap(arr[minIdx], arr[i]);
}
}
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void print(int arr[], int size)
{
for(inti = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
Selection Sort
C++
implementation

34. Complexity:
▪Worst Case: ??????(??????
2
)
▪Average Case: ??????(??????
2
)
▪Best Case: ??????(??????
2
)
Advantages:
▪It’s simple and easy to implement.
▪It can be used for small data sets.
▪In-place sorting algorithm, however, it is not stable.
Disadvantages:
▪Running time of Selection sort algorithm is very poor of ??????(??????
2
).
▪However, in case of large data sets, the efficiency of selection sort drops.

35. Brute-force

36. 2) Bubble Sort
–In bubble sorting, consecutive adjacent pairs of elements in the array are
compared with each other.
–If the element at the lower index is greater than the element at the higher index,
the two elements are interchanged so that the element is placed before the
bigger one.
–This process will continue till the list of unsorted elements exhausts.
–This procedure of sorting is called bubble sorting because elements ‘bubble’ to
the top of the list.

37. Bubble Sort Algorithm
1)Start from the beginning of the array and compare each pair of adjacent elements.
2)Swap the elements if they are in the wrong order.
3)Repeat this process for the entire array, moving the largest element to the end in each pass.
4)Reduce the range of elements to be compared by one and repeat until no more swaps are
needed.
5)The array is sorted when no more swaps are required in a complete pass.
2 8 5 3 9 4 1

39. void bubbleSort(int arr[], int n)
{
for(inti = 0; i < n-1; i++)
{
for(intj = 0; j < n-i -1; j++)
{
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}

40. bool swapped = true;
for(inti = 0; i < n -1; i++)
{
for(intj = 0; j < n -i -1; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
swapped = false;
}
}
// List is already sorted
if (swapped == true)
break;
}

41. #include <iostream>
using namespace std;
void print(int arr[], int n);
void swap(int& x, int& y);
void bubbleSort(int arr[], int n);
int main()
{
int arr[] = { 2, 8, 5, 3, 9, 4, 1 };
//int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "After Bubble Sort: ";
print(arr, n);
return 0;
}
void bubbleSort(int arr[], int n)
{
bool swapped = true;
int c = 0, swaps = 0;
for(inti = 0; i < n-1; i++)
{
for(intj = 0; j < n-i -1; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
swapped = false;
swaps++;
}
c++;
}
// List is already sorted
if (swapped == true)
break;
}
cout << "Number of rounds: " << c << endl;
cout << "Number of swaps: " << swaps << endl;
}
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void print(int arr[], int n)
{
for(inti = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
Bubble Sort
C++
implementation

42. Complexity:
▪Worst Case: ??????(??????
2
)
▪Average Case: ??????(??????
2
)
▪Best Case: ??????(??????)
Advantages:
▪Simple and easy to implement
▪In this sort, elements are swapped in place without using additional
temporary storage, so the space requirement is at a minimum.
▪A stable sorting algorithm.
Disadvantages:
▪It’s a slow method — ??????(??????
2
)
▪Inefficient for large sorting lists.

43. Divide N Conquer

44. 3) Insertion Sort
1)Simple Algorithm:
–Insertion Sort is one of the simplest sorting algorithms, making it easy to understand and implement.
2)Useful for Small Inputs:
–It is efficient for small datasets or arrays that are already mostly sorted.
3)Common in Everyday Life:
–The algorithm mimics the way card players sort a hand of cards, by picking and placing cards in the
correct position.
4)Takes Advantage of Pre-sorting:
–If the array is already partially sorted, Insertion Sort can be very efficient.
5)Fewer Comparisons:
–Insertion Sort typically requires fewer comparisons than Bubble Sort.
6)Shifts Elements:
–To insert an element into its correct position, it shifts larger elements to the right.

45. Insertion Sort Algorithm
1)Iterate through the array starting from the second element.
2)For each element, compare it with the elements in the sorted portion of the array (to the
left of it).
3)Shift elements in the sorted portion to the right until the correct position for the current
element is found.
4)Insert the current element into its correct position in the sorted portion.
5)Repeat steps 2-4 until the entire array is sorted.
2 8 5 3 9 4

47. void InsertionSort(int list[], int n)
{
int i, curr, j;
for(i = 1; i < n; i++)
{
curr = list[i];
j = i - 1;
while (j >= 0 && list[j] > curr)
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = curr;
}
}

48. #include <iostream>
using namespace std;
void start(int list[], int n);
void InsertionSort(int list[], int n);
void print(int list[], int size);
int main()
{
int n;
cout << "Enter the list size: ";
cin >> n;
int* list = new int[n]; // dynamic array
start(list, n); // Sample: n = 7, elements = { 2, 8, 5, 3, 9, 4, 1 }
delete[] list;
return 0;
}
void start(int list[], int n)
{
for(inti = 0; i < n; i++)
{
cout << "Enter list item " << i << " : ";
cin >> list[i];
}
cout << "Before Sorting: ";
print(list, n);
InsertionSort(list, n);
cout << "After Sorting: ";
print(list, n);
}
void InsertionSort(int list[], int n)
{
int i, curr, j;
for(i = 1; i < n; i++)
{
curr = list[i];
j = i - 1;
while (j >= 0 && list[j] > curr)
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = curr;
}
}
void print(int list[], int size)
{
for(inti = 0; i < size; i++)
cout << list[i] << " ";
cout << endl;
}
Insertion Sort
C++
implementation

49. Complexity:
▪Worst Case: ??????(??????
2
)
▪Average Case: ??????(??????
2
)
▪Best Case: ??????(??????)
Advantages:
▪Relatively simple and easy to implement.
▪Efficient to use on small sets of data.
▪Can be efficiently implemented on datasets that are already substantially sorted.
▪The insertion sort is an in-place sorting algorithm, so the space requirement is minimal.
▪Insertion sort is stable because it maintains the relative order of equal elements.
Disadvantages:
▪Inefficient for large sorting lists — ??????(??????
2
)

51. #include <iostream>
using namespace std;
// Using non-recursive method
intfactorial_nonRec(intn)
{
int total = 1;
for(inti = n; i > 1; i--)
total *= i;
return total;
}
// Using recursion
int factorial(int n)
{
// base case
if (n == 0)
return 1;
returnfactorial(n-1) * n;
}
int main()
{
int x = 5;
cout << "Factorial of " << x << " is " << factorial(x) << endl;
return 0;
}
Factorial
Recursion Example
C++
Implementation

52. Divide N Conquer

53. 4) Merge Sort
–Merge Sort uses the divide-and-conquer approach to break the problem into
smaller sub-problems, solve each sub-problem recursively, and then combine the
results.
–Merge Sort is a comparison-based sorting algorithm that repeatedly compares
pairs of elements to determine their order.
–Merge Sort is typically implemented using recursion, although it can also be
implemented iteratively.

54. Merge Sort Algorithm
1)Divide the array into two halves.
2)Recursively apply Merge Sort to each half.
3)Merge the two sorted halves back together:
a)Compare the elements of the two halves and arrange them in order.
b)Continue merging elements until all elements from both halves are merged into a single sorted array.
4)Repeat the process until the entire array is sorted.
2 8 5 3 9 4 1 7

56. #include<iostream>
using namespace std;
void Merge(int arr[], int left, int mid, int right);
void MergeSort(int arr[], int left, int right);
void swap(int& x, int& y);
void print(int arr[], int n);
int main() {
int A[] = { 30, 10, 12, 5, 90, 7, 120 };
int n = sizeof(A) / sizeof(A[0]);
cout << "Before Sorting: ";
print(A, n);
MergeSort(A, 0, n -1);
cout << "After Sorting: ";
print(A, n);

return 0;
}
void Merge(int arr[], int left, int mid, int right) {
inti, j, k, nl, nr;
// size of left and right sub -arrays
nl = mid - left + 1;
nr = right - mid;
int lA[nl], rA[nr];
// fill left and right sub-arrays
for(i = 0; i < nl; i++)
lA[i] = arr[left + i];
for(j = 0; j < nr; j++)
rA[j] = arr[mid + 1 + j];
i = 0; j = 0; k = left;
// merge temp arrays to real array
while(i < nl && j < nr)
if(lA[i] <= rA[j])
arr[k++] = lA[i++];
else
arr[k++] = rA[j++];
// extra element in left array
while (i < nl) arr[k++] = lA[i++];
// extra element in right array
while(j < nr) arr[k++] = rA[j++];
}
void MergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
void swap(int& x, int& y) {
int temp = x;
x = y;
y = temp;
}
void print(int arr[], int n) {
for(inti = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
Merge Sort
C++
implementation

57. #include<iostream>
using namespace std;
void Merge(int A[], int l, int m, int r);
void MergeSort(int A[], int l, int r);
void swap(int& x, int& y);
void print(int A[], int n);
int main()
{
int A[] = { 30, 10, 12, 5, 90, 7, 120 };
int n = sizeof(A) / sizeof(A[0]);
cout << "Before Sorting: ";
print(A, n);
MergeSort(A, 0, n -1);
cout << "After Sorting: ";
print(A, n);
}
void Merge(int A[], int l, int m, int r)
{
inti, j, k, nl, nr;
// size of left and right sub -arrays
nl = m - l + 1;
nr = r - m;
int lA[nl], rA[nr];
// fill left and right sub -arrays
for(i = 0; i < nl; i++)
lA[i] = A[l+ i];
for(j = 0; j < nr; j++)
rA[j] = A[m + 1 + j];
i = 0; j = 0; k = l;
// nl = 4, nr = 4
// 0 1 2 3
// lA = [ 2 3 5 8 ]
// rA = [ 1 4 7 9 ]
// A = [ ]

// i = 0, j = 0, k = 0

// merge temp arrays to real array
while(i < nl && j < nr)
{
if(lA[i] <= rA[j])
{
A[k] = lA[i];
i++;
}
else
{
A[k] = rA[j];
j++;
}
k++;
}
// extra element in left array
while (i < nl)
{
A[k] = lA[i];
i++; k++;
}
// extra element in right array
while (j < nr)
{
A[k] = rA[j];
j++; k++;
}
}
void MergeSort(int A[], int left, int right)
{
// 0 1 2 3 4 5 6 7
// A = [ 2 8 5 3 9 4 1 7 ]
// left = 0, right = 7, middle = 3
if (left < right)
{
int middle = left + (right - left) / 2;
// middle = 0 + (7 - 0) / 2 = 3.5 = 3
MergeSort(A, left, middle);
MergeSort(A, middle + 1, right);
Merge(A, left, middle, right);
}
}
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void print(int A[], int n)
{
for(inti = 0; i < n; i++)
cout << A[i] << " ";
cout << endl;
}
Merge Sort
C++
implementation
(Trace Version)

58. Complexity:
▪Worst Case: ??????(??????log??????)
▪Average Case: ??????(??????log??????)
▪Best Case: ??????(??????log??????)
Advantages:
▪Merge Sort is well-suited for sorting large datasets that do not fit into memory (external sorting)
because it accesses data sequentially and has good performance with large datasets.
▪Merge Sort is a stable sort, meaning that it preserves the relative order of equal elements in the
sorted array.
Disadvantages:
▪Merge Sort is not in-place sorting algorithm since it requires additional space proportional to the
size of the array being sorted.

59. Divide N Conquer

60. 5) Quick Sort
–Quick Sort uses the divide-and-conquer approach to break the problem into
smaller sub-problems, sort each sub-problem recursively, and then combine the
results.
–Quick Sort is typically implemented using recursion, although it can also be
implemented iteratively.
–The choice of the pivot element is crucial for the performance of Quick Sort.
Good pivot selection strategies can significantly improve its efficiency.

61. Quick Sort Algorithm
1)Choose a pivot element from the array.
2)Partition the array into two halves:
a)Elements less than the pivot go to the left.
b)Elements greater than the pivot go to the right.
3)Recursively apply Quick Sort to the left and right halves.
4)Combine the sorted halves with the pivot to form a fully sorted array.
5)Repeat the process until the entire array is sorted.
2 8 5 3 9 4 1 7

62. Pivot: right-most element (may differ).
Merge: Left + Pivot + Right
Quick Sort in action

64. #include <iostream>
using namespace std;
void quickSort(int arr[], int left, int right);
int partition(int arr[], int left, int right);
void swap(int& x, int& y);
void printArray(int arr[], int size);
int main()
{
int arr[] = { 2, 8, 5, 3, 9, 4, 1, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n -1);
printArray(arr, n);
return 0;
}
void quickSort(int arr[], int left, int right)
{
if (left < right)
{
int pivot = partition(arr, left, right); // pivot index
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
int partition(int arr[], int left, int right)
{
int pivot = arr[right]; // last element as pivot
int i = left - 1;
for (int j = left; j <= right; j++)
{
if (arr[j] < pivot)
swap(arr[++i], arr[j]);
}
swap(arr[i + 1], arr[right]);
return i + 1;
}
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void printArray(int arr[], int size)
{
cout << "\nArray: ";
for(inti = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
Quick Sort
C++
implementation
Method #1

65. #include <iostream>
using namespace std;
int HoarePartition(int A[], int l, int r);
void QuickSort(int A[], int l, int r);
void swap(int& x, int& y);
void print(int A[], int size);
int main()
{
int A[] = { 8, 3, 2, 9, 7, 1, 5, 4 };
int n = sizeof(A) / sizeof(A[0]);
cout << "Before Sorting: ";
print(A, n);
QuickSort(A, 0, n -1);
cout << "After Sorting: ";
print(A, n);
return 0;
}
int HoarePartition(int A[], int l, int r)
{
int pivot = A[l];
inti = l, j = r+ 1;
do
{
do {
i++;
} while (A[i] < pivot); // until A[i] >= p
do {
j--;
} while (A[j] > pivot); // until A[j] <= p
swap(A[i], A[j]);
} while (i < j); // until i >= j
swap(A[i], A[j]); // undo last swap when i >= j
swap(A[l], A[j]);
return j;
}
void QuickSort(int A[], int l, int r)
{
if (l < r)
{
int s = HoarePartition(A, l, r);
QuickSort(A, l, s - 1);
QuickSort(A, s + 1, r);
}
}
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void print(int A[], int size)
{
for(inti = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
Quick Sort
C++
implementation
Method #2

66. #include <iostream>
#include <vector>
using namespace std;
vector<int> quick_sort(vector<int> &S)
{
// base case
if (S.size() <= 1) {
return S;
}
vector<int> left;
vector<int> right;

int pivot = S[0]; // first element as pivot
for(inti = 0; i < S.size(); i++)
{
int element = S[i];
if (element >= pivot)
right.push_back(element);
else
left.push_back(element);
}
vector<int> sorted_left = quick_sort(left);
vector<int> sorted_right(right.begin() + 1, right.end()); // excluding pivot
sorted_right = quick_sort(sorted_right);
// Combine 'left + pivot + right'
sorted_left.push_back(pivot);
sorted_left.insert(sorted_left.end(), sorted_right.begin(), sorted_right.end());
return sorted_left;
}
int main()
{
vector<int> arr = { 85, 24, 63, 45, 17, 31, 96, 50 };
vector<int> sorted_arr = quick_sort(arr);
cout << "After Sorting: ";
for (int i : sorted_arr)
cout << i << " ";
return 0;
}
Quick Sort
C++
implementation
Method #3

67. Complexity:
▪Worst Case: ??????(??????
2
)
▪Average Case: ??????(??????log??????)
▪Best Case: ??????(??????log??????)
Advantages:
▪Quick Sort is in-place sorting algorithm, meaning it requires only a small, constant amount of additional
memory space.
▪Despite its worst-case scenario, Quick Sort is often faster in practice compared to other ????????????log??????
algorithms like Merge Sort due to its good cache performance and low overhead.
Disadvantages:
▪The worst-case time complexity is ??????(??????
2
), which occurs when the pivot selection consistently results in
highly unbalanced partitions.
▪Quick Sort is not stable, which means it may not preserve the relative order of equal elements.

68. Which algorithm would Obama pick?
Source: http://www.youtube.com/watch?v=k4RRi_ntQc8

69. End of lecture 1
Thank You!