Sorting Algorithms

Two types for sorting algorithms :

1. Internal sorting algorithms
2. External sorting algorithms

TYPE
K = any ordered data type ;
T = RECORD
key : K ;
...
...
other informations ;
END;

E a collection of T ( like array or file of T )

 If E small enough to fit into internal memory (algorithm called internal sorting
algorithm).
Otherwise E too large  sorting the elements of E in a file saved in external memory
like floppy disk, hard disk,… (algorithm called external sorting algorithm).

Type of internal sorting algorithm :

1. Bubble sort
2. Insertion sort
3. Selection sort The keys saved in one dim Array A
4. Quick sort
5. Heap sort
6. Merge sort

Type of external sorting algorithm :

1. Balanced merge sort
2. Natural merge sort The keys saved in a file
3. Polyphase sorting

** Searching in sorted elements costs O(log2n).

** Searching in unsorted elements costs O(n).
 Internal sorting Algorithms
Declaration :

CONST
N = … ( the size of the array to be sorted )
TYPE
K = … ( any ordered data type )
Index = 1… N;
T = RECORD
key : K;
…
…
other informations;
END;
VAR
A: array [ index] of T;

PROCEDURE swap( VAR x , y : T );

VAR
Temp : T;
BEGIN
Temp := x;
x := y;
y := temp;
END;

Bubble sort :

The elements in the array will be sorted in (N-1) passes beginning with i = 2, in
the first pass comparing A[N] with A[N-1] , if ( A[N].key < A[N-1])  swapping
until we reach the comparing of A[i] with A[i-1].
Body of algorithm :
For i := 2 to N do
Begin
for j := N down to i do
if A[j].key < A[j-1] then
Swap( A[j-1], A[j]) ;
End;

void bubble ( int A[ ] , int n )

{ int tmp ;
for ( int i = 2 ; i <= n ; ++i )
{ for ( int j = n ; j >= i : --j )
if ( A[j] < A[j-1] )
{ tmp = A[j] ;
A[j] = A[j-1]; SWAPPING
A[j-1] = tmp;
}
}
}
 Example:
Sort the following array of integers using Bubble sort.

8 2 6 4
1 2 3 4
1. Round (Outer loop ) :

i=2  j = N to 2
j = 4  swap (A[j],A[j-1])

8 2 4 6
1 2 3 4
j = 3  nothing to do

8 2 4 6
1 2 3 4
j = 2  swap (A[j],A[j-1])

2 8 4 6
1 2 3 4
2. Round (Outer loop ) :

i = 3  j = 4 to 3
j = 4  nothing to do
2 8 4 6
1 2 3 4
j = 3  swap (A[j],A[j-1])

2 4 8 6
1 2 3 4
3. Round (Outer loop ) :

i = 4  j = 4 to 4
j = 4  swap (A[j],A[j-1])
2 4 6 8
1 2 3 4

Complexity of bubble sort :

Value of i = 2 , 3, 4 , … , N-1 , N
……….
No of comparisons for each round : N-1 , N-2 , N-3 … , 2 , 1

Comparisons in i-th round : (N - i + 1)

The number of comparisons = (N-1) + (N-2)+… + 3 + 2 + 1 = 1/2N(N-1)

 worst case complexity of bubble sort W(N) = 1/2N(N-1) , is O( ? )

lim W(N)/N2 = lim [1/2N(N-1)]/N2 = 1/2*lim (N-1)/N = 1/2 ≠ ∞

 W(N) = 1/2N(N-1) is O(N2 )
Insertion sort:

Idea :
We begin with for i = 2 to N ( N the number of elements )
Comparing i-th element with the preceding entries with index (i-1) , (i-2) ,…,2 , 1
in the array until either we reach a smaller element or reach the left hand end of the
array .

Body of algorithm :
A : array [0..N] of T;
begin
for i := 2 to N do
begin
x := A[i];
A[0] := x;
j := i-1;
while (A[j].key > x.key) do
begin
A[j+1] := A[j];
A[j] := x;
j := j-1;
end;
end;
end;

void insertion ( int A[ ] , int n )

{ int i , j , x ;
for ( i = 2 ; i <= n ; ++i )
{ x = A[i] ;
A[0] = x ;
j=i-1;
while ( A[j] > x )
{ A[j+1] = A[j] ;
A[j] = x ;
j-1;
}
}
}
Example :
Sort the following array of integers using insertion sort.

8 2 6 4
1 2 3 4
1. Round :
i=2
x = A[2] = 2
A[0] = 2
2 8 2 6 4
0 1 2 3 4
j = i-1 = 1
while : A[j] > x
8 > 2  YES
 A[j+1] = A[j]
A[2] = A[1] = 8
A[1]=2.

2 2 8 6 4
0 1 2 3 4
j := j - 1 = 0 ,
A[0] comparing with x  A[0] = x out of the loop.

2. Round :
i=3
x = A[3] = 6
A[0] = 6
6 2 8 6 4
0 1 2 3 4
j = i -1 = 2
while : A[j] > x
8 > 6  YES
 A[j+1] = A[j]
A[3] = A[2] = 8 ,
A[2] = 6.

6 2 6 8 4
0 1 2 3 4
j = j -1 = 1;
j=1
A[1] > x 
2 > 6  NO
 out of the loop
3. Round :
i=4

x = A[4] = 4
A[0] := 4
4 2 6 8 4
0 1 2 3 4
j=i–1=3
while : A[j] > x
8 > 4  YES
 A[j+1] = A[j]
A[4] = A[3] = 8
A[3] = 4

4 2 6 4 8
0 1 2 3 4
j=j–1=2
while : A[j] > x
6 > 4  YES
 A[j+1] = A[j]
A[3] = A[2] = 6
A[2] = 4

4 2 4 6 8
0 1 2 3 4
j=j–1=1
while : A[j] > x
2 > 4  NO
 Out of while (STOP)

2 4 6 8
1 2 3 4

Complexity of insertion sort :

Value of i = 2 , 3 , 4 , … , N-1 , N

No of comparisons for each round : 1 , 2 , 3 , … , N-2 , N-1

Comparisons in i-th round : ( i - 1)

The number of comparisons = (N-1) + (N-2)+… + 3 + 2 + 1 = 1/2N(N-1)

 worst case complexity of insertion sort W(N) = 1/2N(N-1) is O(N2 )

Selection sort :

Idea :
For i = 1 to N-1 :
In the i_th round comparing the key in i_th position with the keys in the (i+1)_th,
(i+2)_th ,…, N_th positions, each time we find a key less than the key in i_th
position (swap).

Body of algorithm :

For i := 1 to N-1 do
Begin
k := i;
x := A[i];
For j := i+1 to N do
if A[j].key < x.key then
Begin
k := j;
x := A[j];
End;
Swap(A[i] , A[k]);
End;
void selection ( int A[ ] , int n )
{ int i = 1 , k ;
int tmp , x ;

for ( ; i <= n - 1 ; ++i )

{ k=i;
x = A[i] ;
for ( int j = i + 1 ; j <= n ; ++j )
if ( A[j] < x )
{k=j;
x = A[j] ;
}
tmp = A[k] ;
A[k] = A[i] ; swap(A[i] , A[k])
A[i] = tmp ;
}
}
Example:
Sort the following array of integers using selection sort.
8 2 6 4
1 2 3 4
1. Round :
i=1
k=1
x = A[1] = 8

inner loop :
j = i + 1 = 2  A[2] < x  2 < 8  YES
k=j=2
x = A[2] = 2

j = 3  A[3] < x  6 < 2  NO ( nothing to do )

j = 4  A[4] < x  4 < 2  NO ( noting to do )

swap( A[i] , A[k] ) = swap(A[1],A[2]) :

2 8 6 4
1 2 3 4
2. Round :
i=2
k=2
x = A[2] = 8

inner loop :
j = i + 1 = 3  A[3] < x  6 < 8  YES
k=j=3
x = A[3] = 6

j = 4  A[4] < x  4 < 6  YES

k=j=4
x = A[4] = 4

swap( A[i] , A[k] ) = swap(A[2],A[4]) :

2 4 6 8
1 2 3 4
3. Round :
i=3
k=3
x = A[3] = 6

inner loop :
j = i + 1 = 4  A[4] < x  8 < 6  NO
 (Nothing to do )

swap( A[i] , A[k] ) = swap(A[3],A[3]) :

2 4 6 8
1 2 3 4
Complexity of selection sort :

Value of i = 1 , 2 , 3 , … , N-2 , N-1

No of comparisons for each round : N-1 , N- 2 , N - 3 , … , 2 , 1

Comparisons in i-th round : ( N - i)

The number of comparisons = (N-1) + (N-2)+… + 3 + 2 + 1 = 1/2N(N-1)

 worst case complexity of insertion sort W(N) = 1/2N(N-1) is O(N2 )