Sorting
Dr. M. Sohail
Week 11 (Feb 3…7)
Objectives
• Today’s lecture objectives include:
– Sorting
• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
Data Structures & Algorithms 2
Bubble Sort
Data Structures & Algorithms 3
Data Structures & Algorithms 4
Bubble sort
The first pass of a bubble sort.
The shaded items are being
compared to see if they are out of
order.
If there are n items in the list,
then there are n−1 pairs of items
that need to be compared on the
first pass.
Data Structures & Algorithms 5
Data Structures & Algorithms 6
Swapping
• temp = alist[i]
• alist[i] = alist[j]
• alist[j] = temp
Data Structures & Algorithms 7
Data Structures & Algorithms 8
Selection sort
Improves on the bubble sort
by making only one exchange for every pass through the list.
Looks for the largest value as it makes a pass and,
after completing the pass, places it in the proper location.
As with a bubble sort, after the first pass, the largest item is in the
correct place.
After the second pass, the next largest is in place.
This process continues and requires n−1 passes to sort n items,
since the final item must be in place after the (n−1)st pass.
Data Structures & Algorithms 9
selection sort
Data Structures & Algorithms 10
Selection Sort Example
• How It Works:
• The selection sort algorithm divides the input array
into two parts: the sorted part and the unsorted
part.
• Initially, the sorted part is empty, and the unsorted
part contains all the elements.
• In each iteration, the algorithm finds the minimum
element from the unsorted part and moves it to the
end of the sorted part.
• This process continues until the unsorted part
becomes empty and the sorted part contains all the
elements in sorted order.
Data Structures & Algorithms 11
#include <iostream> Selection sort C++ code
#include <vector>
void selectionSort(std::vector<int>& arr)
{
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
// Find the minimum element in the unsorted part of the array
int minIndex = i;
for (int j = i + 1; j < n; ++j)
{
if (arr[j] < arr[minIndex])
{
minIndex = j; }} // Swap the found minimum element with the first
element of the unsorted part
if (minIndex != i)
{ std::swap(arr[i], arr[minIndex]); } }}
Data Structures & Algorithms 12
int main() Selection sort C++ code..
{ std::vector<int> arr = {64, 25, 12, 22, 11};
std::cout << "Original array: ";
for (int num : arr)
{ std::cout << num << " "; }
std::cout << std::endl;
selectionSort(arr);
std::cout << "Sorted array: ";
for (int num : arr)
{ std::cout << num << " "; }
std::cout << std::endl;
return 0;}
Data Structures & Algorithms 13
Selection sort C++ code Explanation
Explanation:
1.Function Definition: The selectionSort function takes a reference to a
vector of integers.
2.Outer Loop: The outer loop runs from the beginning of the array to the second-
to-last element (n - 1), as the last element will already be sorted by the time the
loop reaches it.
3.Finding Minimum: The inner loop starts from i + 1 and finds the index of the
minimum element in the unsorted part of the array.
4.Swapping: If the minimum element found is not the current element (i), it swaps
the current element with the minimum element.
5.Main Function: The main function initializes an array, prints it before sorting,
calls the selectionSort function, and then prints the sorted array.
Data Structures & Algorithms 14
Selection sort Python code
Data Structures & Algorithms 15
Insertion Sort – Cont…
• An insertion sort inserts the next unsorted element into its
proper location within the sorted portion of an array
Data Structures & Algorithms 16
Insertion sort …
Data Structures & Algorithms 17
Insertion Sort Example
• An insertion sort of an array of integers into ascending
order
Data Structures & Algorithms 18
Insertion sort …
Data Structures & Algorithms 19
Insertion sort C++ code..
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Data Structures & Algorithms 20
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
std::cout << "Original array: "; Explanation:
for (int num : arr) { Function Definition: The insertionSort function takes a
std::cout << num << " "; reference to a vector of integers.
} Outer Loop: The outer loop starts from the second
std::cout << std::endl; element (index 1) and goes through each element in the
array.
insertionSort(arr); Key Element: The current element being sorted is stored
in key.
std::cout << "Sorted array: "; Inner Loop: The inner loop shifts elements of the sorted
for (int num : arr) { portion of the array (to the left of the current element)
std::cout << num << " "; that are greater than key to the right by one position.
} Insert Key: After shifting, the key is inserted into its
} correct position.
std::cout << std::endl; Main Function: The main function initializes an array,
prints it before sorting, calls the insertionSort function,
return 0; and then prints the sorted array.
}
Data Structures & Algorithms 21
Insertion sort python code …
Data Structures & Algorithms 22
Summary
• Bubble Sort
• Selection Sort
• Insertion Sort
Data Structures & Algorithms 23
THANK YOU
https://runestone.academy/ns/books/published/pythonds/index.html
Data Structures & Algorithms 24
