Lecture Notes :

Algorithms
4th week: Sorting Algorithms

Academic year : 2023-2024.

1st Year Mathematics License,

Content :
• Brief recap.
• Introduction to sorting algorithms.
• Overview of common sorting algorithms.
• Binary search algorithm.

1/16
Sorting Problem
Sorting Arrays

• Arrays allow you to store multiple elements of the same type within a single
entity. When the type of these elements has an order, you can arrange them in
ascending or descending order.
• Sorting an array means arranging the elements of an array in ascending or
descending order.

Suppose that you need to sort a sequence of numbers into monotonically increasing
or decreasing order.
Input: An array of n numbers [a1 , a2 , . . . , an ].
Output: A permutation (reordering) a′1 , a′2 , . . . , a′n of the input sequence such that
a′1 ≤ a′2 ≤ · · · ≤ a′n .

5 2 8 1 → 1 2 5 8

2/16
Let’s try!
Let T be an array of 5 elements, containing strictly positive integers. The following is simple
sorting algorithm:
Algorithm Sort_array;
Var i, p, min, T[5], ST[5]: integer ;
Begin \\ T must be filled first
min <- T[1];
For i <- 1 to 5 do
For j <- 1 to 5 do
If(T[j] < min AND T[i] != -1)
min <- T[i];
p <- j;
EndIf;
EndFor;
T[p] <- -1;
ST[i] <- min;
EndFor;
End; 3/16
Selection Sort
Selection Sort Algorithm

Principle
Selection Sort is a simple sorting algorithm.
• It divides an array into two parts: sorted and unsorted.
• It repeatedly selects the minimum element from the unsorted part and moves it
to the sorted part.
• This process continues until the entire array is sorted.

In other words,
• the minimum element in the array is searched for,
• and then swapped with the element that is currently located at the first position,
• Now the minimum element in the remaining unsorted array is searched for and put in
the second position,
• and so on.
4/16
Selection Sort Algorithm : Example, A = [7, 5, 4, 2]

5/16
Selection Sort Algorithm

Algorithm Selection_Sort;
Var i, j, min, p, T[5]: integer;
Begin \\ T must be filled first
For i <- 1 to 5 do
min <- T[i];
p <- i;
For j <- i+1 to 5 do
If(T[j] < min)
min <- T[j];
p <- j;
EndIf;
EndFor;
T[p] <- T[i];
T[i] <- min;
EndFor;
End;
6/16
Bubble Sort
Bubble Sort Algorithm

Bubble sort is based on the idea of repeatedly comparing pairs of adjacent elements and
then swapping their positions if they exist in the wrong order.

Principle
The bubble sort algorithm consists in progressively moving up the largest elements of
an array. Its principle is
• to invert two successive elements if they are not sorted in the right order,
• and to start again until no more elements can be swapped.

Assume that A is an unsorted array of elements. This array needs to be sorted in ascending
order.

7/16
Bubble Sort Algorithm : Example, A = [7, 4, 5, 2]

8/16
Bubble Sort Algorithm

Algorithm Bubble_sort;
Var i, j, n, temp, T[5]: integer;
Begin \\ T must be filled first
n <- 5;
For i <- 1 to n-1 do
For j <- 1 to n - i do
If T[j] > T[j+1] Then
temp <- T[j];
T[j] <- T[j+1];
T[j+1] <- temp;
EndIf;
EndFor;
EndFor;
End;

9/16
Dichotomy Search (Binary
Search)
Dichotomy Search
Binary Search is a fast and efficient search algorithm.
• It works on sorted arrays.
• The key idea is to repeatedly divide the search interval in half.
• Compare the middle element with the target value.
• If the middle element is equal to the target, the search is successful.
• If the target is less than the middle element, search the left half; otherwise,
search the right half.
• Continue this process until the target is found or the search interval is empty.

Example. Let A = [2, 3, 8, 20] an array of 4 elements and V = 3 the target value.
• The mid value in the array is A[2] = V = 3.

2 3 8 20 2 3 8 20
A: →
1: left 2 3 right 1: left 2: mid 3 4: right
10/16
Dichotomy Search: Example

Let A = [1, 3, 12, 14, 23, 34, 55, 65, 75, 78] an array of 10 Elements sorted in
increasing order.
• We want to find the index of value 75 in A.

11/16
Dichotomy Search: Example

Iteration 1
• The left index is 0,
• The right index is 9,
• The mid index is 4.
We have A[mid] < V (A[4] = 23 and V = 75). Hence, the target value V is at the
right half of the array. Hence,
• left ← 4,

12/16
Dichotomy Search: Example

Iteration 2
• The left index is 4,
• The right index is 9,
• The mid index is 7.
We have A[mid] < V (A[7] = 65 and V = 75). Hence, the target value V is at the
right half of the array. Hence,
• left ← 7,

13/16
Dichotomy Search: Example

Iteration 3
• The left index is 7,
• The right index is 9,
• The mid index is 8.
We have A[mid] = V. Hence, the target value V is found!!!

14/16
Dichotomy Search: Mid value (Example)

In the following table we search for the value V = 7 in an array, we can see the mid value
changes, in four iterations, until the target value 7 is found.

15/16
Dichotomy Search (Binary Search)

Algorithm Binary_search;
Var left, right, target, middle, T[10], found: integer;
Begin
read(target); // The value to search for
left <- 1; right <- 10;
found <- -1;
While left <= right do
middle <- (left + right) div 2;
If T[middle] = target Then
found <- middle;
ElseIf T[middle] < target Then
left <- middle + 1;
Else
right <- middle - 1;
EndIf;
EndWhile;
End; 16/16