Data Structures & Algorithms

Lecture : 04

1
Sorting Algorithms

2
 Some Definitions
• Sorting
– Is a process that organizes a collection of data into
either ascending or descending order
• Internal Sort
– The data to be sorted is all stored in the computer’s
main memory.
• External Sort
– Some of the data to be sorted might be stored in some
external, slower, device.
• In Place Sort
– The amount of extra space required to sort the data is
constant with the input size.
3
 Sorting
– We will analyze only internal sorting algorithms.

– Sorting also has indirect uses. An initial sort of the data

can significantly enhance the performance of an
algorithm.

– Majority of programming projects use a sort

somewhere, and in many cases, the sorting cost
determines the running time.

– It is estimated that 25~50% of all computing power is

used for sorting activities. 4
 Sorting Applications
– Common problem: sort a list of values, starting from
lowest to highest.
• Example: Sorting {7, 3, 5, 1, 9} into {1, 3, 5, 7, 9}.
– To prepare a list of student ID, names, and scores in a
table (sorted by ID or name) for easy checking.

– To prepare a list of scores before letter grade

assignment.

– To produce a list of horses after a race (sorted by the

finishing times) for payoff calculation.
5
 Sorting Applications…
– To prepare an originally unsorted array for ordered
binary searching.
– List of exam scores (Sorting helps to find top
students, to find lowest scores and to find median
scores).
– Words of dictionary in alphabetical order
– Generally, we are given a list of records that have
keys. These keys are used to define an ordering of
the items in the list.
– Keys are unique identifiers (e.g., student ID,
employee number, product ID).
6
 C++ Implementation of Sorting
– Use C++ templates to implement a generic sorting
function.

– This would allow use of the same function to sort items

of any class.

– However, class to be sorted must provide the following

overloaded operators:
• Assignment: =
• Ordering: >, <, ==

– In this lecture, we’ll talk about sorting integers;

however, the algorithms are general and can be applied
to any class as described above. 7
 Sorting Algorithms
• There are many sorting algorithms, such as:
– Selection Sort
– Insertion Sort
– Bubble Sort
– Merge Sort
– Quick Sort

• The first three are the foundations for faster

and more efficient algorithms.
8
 Selection Sort
• Selection sort is a simple sorting algorithm. It works by first
finding the smallest element using a linear search and swapping it
into the first position in the list,

• Then finding the second smallest element by scanning the

remaining elements, and so on.

• Selection sort is unique compared to almost any other algorithm in

that its running time is not affected by the prior ordering of the list,
it performs the same number of operations because of its simple
structure.

• A list of n elements requires n-1 passes to completely rearrange the

data.
9
 Unsorted

23 78 45 8 32 56 Original List

8 78 45 23 32 56 After pass 1

8 23 45 78 32 56 After pass 2

After pass 3
8 23 32 78 45 56

8 23 32 45 78 56 After pass 4

After pass 5
8 23 32 45 56 78
10
 Selection Sort
// Template function for Selection Sort
template <typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap elements
if (minIndex != i) {
T temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
11
 Selection Sort
template <typename T>
void printArray(T arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int intArr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(intArr) / sizeof(intArr[0]);
cout << "Before sorting (integers): ";
printArray(intArr, n);
selectionSort(intArr, n);
cout << "After sorting (integers): ";
printArray(intArr, n);
return 0;
}
12
 Selection Sort Run Time Complexity
Algorithm Steps
•Find the smallest element and swap it with the first element.
•Find the second smallest and swap it with the second element.
•Repeat this process until the array is sorted.

Time Complexity

Case Comparisons Swaps Time Complexity

Best Case (Already Sorted) O(n²) O(n) O(n²)

Worst Case (Reverse Sorted) O(n²) O(n) O(n²)

Average Case (Random Order) O(n²) O(n) O(n²)

13
 Insertion Sort
• Insertion sort is a simple sorting algorithm that is
appropriate for small inputs.
– Most common sorting technique used by card players.

• Step 1: The second element of an array is compared with

the elements that appears before it (only first element in
this case). If the second element is smaller than first
element, second element is inserted in the position of first
element. After first step, first two elements of an array
will be sorted.

14
 Insertion Sort
• Step 2: The third element of an array is compared with the elements
that appears before it (first and second element). If third element is
smaller than first element, it is inserted in the position of first element.
If third element is larger than first element but, smaller than second
element, it is inserted in the position of second element. If third
element is larger than both the elements, it is kept in the position as it
is. After second step, first three elements of an array will be sorted.

• Step 3: Similarly, the fourth element of an array is compared with the

elements that appears before it (first, second and third element) and
the same procedure is applied and that element is inserted in the
proper position.

• If there are n elements to be sorted. Then, this procedure is

repeated n-1 times to get sorted list of array.
15
 Insertion Sort
• Sorting a hand of playing cards
– Start with an empty left hand and the cards facing down
on the table.

– Remove one card at a time from the table, and insert it

into the correct position in the left hand
• compare it with each of the cards already in the hand, from
right to left

– The cards held in the left hand are sorted

• these cards were originally the top cards of the pile on the
table
16
 Insertion Sort

To insert 12, we need to

make room for it by moving
first 36 and then 24.
6 10 24 36

12

17
 Insertion Sort

6 10 24 36

12

18
 Insertion Sort

6 10 24 3
6

12

19
Sorted Unsorted

23 78 45 8 32 56 Original List

23 78 45 8 32 56 After pass 1

23 45 78 8 32 56 After pass 2

After pass 3
8 23 45 78 32 56

8 23 32 45 78 56 After pass 4

After pass 5
8 23 32 45 56 78
20
21
 Insertion Sort Algorithm
// Template function for Insertion Sort
template <typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) {
T key = arr[i]; // Store the current element
int j = i - 1;
// Move elements that are greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert the element in the correct position
}
} 22
 Insertion Sort Run Time Complexity
Algorithm Steps
•Start with the second element and insert it into the correct
position relative to the first.
•Take the third element and insert it into the correct position
among the first two.
•Repeat until the entire array is sorted.

Time Complexity
Case Comparisons Swaps Time Complexity
Best Case (Already Sorted) O(n) O(1) O(n)

Worst Case (Reverse Sorted) O(n²) O(n²) O(n²)

Average Case (Random Order) O(n²) O(n²) O(n²)

23
 Bubble Sort
• Bubble sort, sometimes incorrectly referred to as sinking
sort, is a simple sorting algorithm that works by
repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items and
swapping them if they are in the wrong order.

• The pass through the list is repeated until no swaps are

needed, which indicates that the list is sorted.

• Each time an element moves from the unsorted part to

the sorted part one sort pass is completed.
24
 Bubble Sort…

• Given a list of n elements, bubble sort requires up to n-1

passes to sort the data.

• Smaller elements "bubble" to the top of the list. Because

it only uses comparisons to operate on elements, it is a
comparison sort.

25
Bubble Sort

26
 Bubble Sort Algorithm
template <typename T>
void bubleSort(T arr[], int n)
{
for (int i = 0; i < n-1; i++)
{
for (int j=0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
T temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}
27
 Bubble Sort Run Time Complexity
Algorithm Steps
•Compare adjacent elements and swap if needed.
•Repeat the process for the entire array multiple times.
•After every pass, the largest element gets "bubbled" to its correct
position.

Time Complexity
Case Comparisons Swaps Time Complexity
Best Case (Already Sorted) O(n) O(1) O(n)

Worst Case (Reverse Sorted) O(n²) O(n²) O(n²)

Average Case (Random Order) O(n²) O(n²) O(n²)

28