A LGORITHMS AND C OMPLEXITY T HEORY

Contents
1 Introduction 3

2 Selection Sort 3
2.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Bubble Sort 4
3.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 Insertion Sort 5
4.1 Sequential insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 binary insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2.1 principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2.3 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.3 Comments on Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 Shell Sort 9
5.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2 Comments on Shellsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6 TreeSort 10
6.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Pseudo-code of Tree sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

7 Quicksort 12
7.1 Naive Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.2 Quicksort analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.3 Quicksort complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.3.1 Average Case Analysis of QuickSort . . . . . . . . . . . . . . . . . . . . . . . . 14
7.3.2 Worst Case Analysis of Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . 15
 3

1 Introduction
More often programming problems include sorting procedures. We will in this part of the course, study
sorting algorithms from the simplest to the more sophisticated ones.

2 Selection Sort
2.1 Principles

We want to sort n elements store in an array. Simple sorting algorithms are those which start by looking
within the array, the smallest element, and then swap it with the one in the first position, then find the
element with the second smallest value and swap it with the element in the second position in the array,
and then continue until the (n−1)th element is processed. We will then obtain a sorted array. This method
is called selection sort.

E XAMPLE 2.1.1
W e want to sort the following array in ascending order:
L I C E N C E
We will have the following sequence of execution
L I C E N C E gives C I L E N C E
C I L E N C E gives C C L E N I E
C C L E N I E gives C C E L N I E
C C E L N I E gives C C E E N I L
C C E E N I L gives C C E E I N L
C C E E I N L gives C C E E I L N

In this version of selection sort algorithm, to search the smallest element of the array to be sorted , we
will compare elements between them and will only record the index of the smallest element, and when
this element is found, swap it using its index. The pseudo-code of the algorithm is :

SelectionSort(int[] t, int n)
1: begin
2: int i,j,min,q
3: for i = 1 to n-1 do
4: min = i
5: for j = i+1 TO n do
6: if t[j] < t[min] then
7: min = j
8: end if
9: end for
10: q = t[min]
11: t[min]= t[i]
12: t[i] = q
13: end for
The maximum running time of this algorithm is O(n2 ). Indeed for a given i n -i comparisons(c) are done,
4 3 BUBBLE SORT

at least four assignments (a) and at most five are done, and one addition(o) is done. In total we have

n(n−1)
(n − 1) + (n − 2) + (n − 3) + ... + 1 = 2
comparisons,

at least 4(n − 1) assignments, at most 5(n − 1) additions, thus the maximum running time is
n2
Tmax (n) = n(n−1)
2
c+5(n-1)a+no = 2
c+ (−c+10a+2o)n
2
−5a = Θ(n2 )

3 Bubble Sort
3.1 Principles
For the bubble sort we think recursively. Given an array of n elements, place the biggest element at the
end. And then apply recursively the algorithm to the n − 1 first elements, if n > 1. The greatest element
is remounted at the end of the array as follows : assuming that the element with index k is the greatest of
the k first elements of the array, the property to hold for k+1 we have :

• if the (k + 1)th element is the greatest then there is nothing to do.

• else swap k th and (k + 1)th elements.

E XAMPLE 3.1.1
W e want to sort the list C K G L B
step array operation Resulting array
1rst CKGLB No change CKGLB
CKGLB K > G , swap K and G CGKLB
CGKLB No change CGKLB
CGKLB L > B , swap L and B CGKBL
2nd CGKBL No change CGKBL
CGKBL No Change CGKBL
CGKBL K > B , swap K and B CGBKL
3rd CGBKL No change CGBKL
CGBKL G > B , swap G and B CBGKL
4th CBGKL C > B , swap C and B BCGKL
BCGKL end

The name bubble sort is given to this strategy of sort because if we visualize the process of sorting , the
greatest element remounts towards the end of the array like air bubbles that remount at the water surface.

3.2 Algorithm
The pseudo-code of the algorithm can be specify as follows:
 5

BUBBLESORT(int [] t, int
n)
int i,j,p
for i = n downto 2 do
for j = 1 to i-1 do
if t[j] > t[j + 1] then
p= t[j]
t[j]= t[j+1]
t[j+1]= p
end if
end for
end for
By applying the same method as in the selection sort it is easy to prove that the complexity of bubble sort
is O(n2 )
Bubble sort is an illustration of the mathematical property that says: ” All permutation can be written as
a product of of transpositions of two consecutive elements”.

4 Insertion Sort
Insertion sort is the natural method used when we want to sort the elements of a list as we are entered
them. If the k first element are already sorted, We will then need to place the (k + 1)th element, We will
then have to :
1. Determine its place amongst the (k + 1) elements
2. Do the necessary shifting for its placement;

4.1 Sequential insertion Sort

Here we will assume that we have an array of integers. Those elements are read and inserted one after
another in the array of the preceding elements already sorted.
4.1.1 Algorithm
We can easily derive the following pseudo-code

SEQINSERTIONSORT(int [] t ,int n)
1: int i,j,q
2: for i = 2 to n do
3: j=i
4: q = t[i]
5: while (( j>1) and (t[j-1] > q) do
6: t[j] = t[j-1]
7: j := j - 1
8: end while
9: t[j] = q
10: end for
Using the same method as in the selection sort it is shown that the complexity of sequential selection sort
is algorithm is Θ(n2 ).
6 4 INSERTION SORT

E XAMPLE 4.1.1
W e want to sort the following list: C K G A B
step array Operation resulting array
1rst C K G A B Initialization, No Change CKGAB
CKGAB
2nd C K G A B Save the value(K) at the 2nd position
Compare K to C, No change CKGAB
CKGAB
3rd C K G A B Save the value(G) at the 3rd position
Compare G to K, Move K to the right CKKAB
C K K A B compare G to C, No change CKKAB
C K K A B insert G at the second position CGKAB
CGKAB
4th C G K A B Save the value(A) at the 4th position
compare A to K, move K to the right CGKKB
C G K K B compare A to G, move G to the right CGGKB
C G G K B compare A to C, move C to the right CCGKB
C C G K B insert A at the first position ACGKB
ACGKB
5th A C G K B Save the value(A) at the 5th position
compare B and K, move K to the right ACGKK
A C G K K compare B to G, move G to the right ACGGK
A C G G K compare B to C, move C to the right ACCGK
A C C G K compare B to A, No change ACCGK
A C C G K insert B at the second position ABCGK
ABCGK

4.2 binary insertion sort

To speed up the search of the position where to insert the element in the sorted part of the array, binary
search will be used.
4.2.1 principles
The algorithm consist of : given an array t , if the k first elements are already sorted, use the binary method
to search the place of the (k + 1)th element .
4.2.2 Algorithm
word represents the element to be placed
istart and iend delimit the zone of the array within which word will be placed. The following algorithm
will search where to insert word.
4.2 binary insertion sort 7

int BinarySearh (int [] t, int word ,int istart ,int iend)

1: int j,k,position
2: position = istart; j = iend
3: while j > position do
4: k = (position+j)/ 2
5: if word ≤ t[k] then
6: j=k
7: else
8: position = k + 1
9: end if
10: end while
11: if (word > t[position]) then
12: position = position + 1
13: end if
14: return (position)
Binary sequential sort can then be performed using the following pseudo-code:

BinarySort (int [] t, int n)

1: int i,j,word,pos
2: for i = 2 to n do
3: word = t[i]
4: pos = BinarySearch(t,word,1,i-1)
5: for j=i downto pos+ 1 do
6: t[j] = t[j-1]
7: end for
8: t[pos]=word
9: end for
4.2.3 Complexity
In the binary search, intervals are split until the place to insert word is found. Assuming that we will do
m iterations to find the position of word, we then have:
2m−1 ≤ n − 1 < 2m then m = log2 (n-1) if n is the number of elements in the array.
The execution time of the binary sort algorithm is then:
X n
T(n) = (A + Blog2 (i − 1) + C + α(i))
i=2

where α(i) is the time used to place a new element in the array. There are three possible cases:

1. Worst Case
α(i) = (i − 1)(e + a) + a where a is the cost of an arithmetic operation and e the cost of an
assignment. Then
n
X
T(n) = (A1 i + Blog2 (i − 1) + C1 )
i=2
n
X n
X
but log2 i < i then T (n) ≤ (A1 i + B(i − 1) + C1 ) = (A2 i + B2 )
i=2 i=2
T(n) ≤ A2 (n − 1) − B2 + A2 n(n+1)
2
d’o T(n) = O(n2 ).
8 4 INSERTION SORT

2. Best case
α(i) = 0
X n n−1
X
T(n) = (A + Blog2 (i − 1)) = (A + Blog2 (i))
i=2 i=1
n
X n−1
Y
T(n)=A(n − 1) + B log2 (i) = A(n − 1) + Blog2 ( i)
√ i=1 i=1
but n! = 2πn( ne n [1 + O( n1 )]
then T (n) = O(n log n).

3. Average Case
Xn
T (n) = (A + Blog2 (i − 1) + C + α(i))
i=2
the average of α(i) is computed as follows:
We have :
i(i−1)
0, 1, 2 , 3, . . . i-1 displacements and by summing we have 2
, as we have i type of displacements
( from 0 to i-1) the average is αm (i) = i(i−1)
2i
= i−1
2
Xn
i−1
T(n) = (A + Blog2 (i − 1) + C + D )
i=2
2
as log2 n < n alors
T(n) = O(n2 )

4.3 Comments on Insertion sort

Insertion sort is good middle-of-the-road choice for sorting lists of few thousand items or less. The
insertion sort is over twice as fast as the bubble sort and almost 40% faster than the selection sort.
 9

E XAMPLE 4.3.2
W e want to use binary insertion sort to sort the following array
C K G A B
(1) A single element C is already sorted
(2) We will then try to insert K in the array which consists of a single el-
ement C, as K is greater than C , we will then have the array C K as
result, this will be done after one comparison , to know if we will insert
K before or after C.
(3) We want then to insert G in the array C K ; instead of trying to find the
place where to insert from C, we will
– split the array into two parts C and K ,
– compare G to C , as G is greater to C , G can only be inserted in the
second part of the list, which consists of a single element K which
is greater than G ,
– then G will be inserted between C and K, which results in the array
C G K.
(4) We then have to insert A in the array C G K:
– split C G K into two parts C G and K,
– compare A to the last element (G) of C G, as G is greater than A,
we will then recursively , using the same method, search for the
position where to insert A in C G. split the list into two parts C and
G , compare A to C , as A is smaller than C , A will be inserted in
the first part of the array, which consists of a single element C ( and
C is greater than A) , means A will be inserted at the beginning of
the array C G, which gives to the array A C G.
– We will then have at this step the list A C G K
(5) We then have to insert B in the array A C G K:
– split A C G K into two parts A C and G K,
– compare B to the last element (C) of A C, as C is greater than B, we
will then recursively , search for the position where to insert B in A
C. split the array into two parts A and C , compare B to A, as B is
greater than A , B will be inserted between A and C, which gives
the array A B C.
– We will then have as result the array A B C G K