SORTING ALGORITHMS
Uzma Rifat
08/11/2015
THE SORTING PROBLEM
Input:
A sequence of n numbers a1, a2, . . . , an
Output:
A permutation (reordering) a1, a2, . . . , an of the
input sequence such that a1 a2 an
2
STRUCTURE OF DATA
3
WHY STUDY SORTING ALGORITHMS?
There are a variety of situations that we can
encounter
Do we have randomly ordered keys?
Are all keys distinct?
How large is the set of keys to be ordered?
Need guaranteed performance?
Various algorithms are better suited to some of
these situations
4
SOME DEFINITIONS
Internal Sort
The data to be sorted is all stored in the computers
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.
5
SORTING METHODS
Comparison based sorting
O(n2) methods
E.g., Insertion, bubble
Average time O(n log n) methods
E.g., quick sort
E.g., Merge sort, heap sort
Non-comparison based sorting
Integer sorting: linear time
6 E.g., Counting sort, bin sort
Radix sort, bucket sort
INSERTION SORT
Idea: like 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
7
INSERTION SORT
To insert 12, we need to
make room for it by
moving first 36 and then
24.
8
INSERTION SORT
9
INSERTION SORT
10
INSERTION SORT
Worst Case: O(n2)
Best Case: O(n)
Less efficient on larger lists
public static void Insertion Sort( int [ ] num)
{
int j; // the number of items sorted so far
int key; // the item to be inserted
int i;
for (j = 1; j < num.length; j++) // Start with 1 (not 0)
{
key = num[ j ];
for(i = j - 1; (i >= 0) && (num[ i ] < key); i--)
{
num[ i+1 ] = num[ i ];
}
num[ i+1 ] = key; // Put the key in its proper location
}
}
ANALYSIS OF INSERTION SORT
INSERTION-SORT(A) cost times
for j 2 to n c1 n
do key A[ j ] c2 n-1
13
Insert A[ j ] into the sorted sequence A[1 . . j -1]0 n-1
ij-1 c4 n-1
while i > 0 and A[i] > key c5
n
t
j 2 j
do A[i + 1] A[i] c6
n
(t j 1)
j 2
ii1 c7
n
(t j 1)
j 2
A[i + 1] key c8 n-1
tj: # of times the while statement is executed at iteration j
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
COMPARISONS AND EXCHANGES IN
INSERTION SORT
INSERTION-SORT(A) cost times
for j 2 to n c1 n
do key A[ j ] c2 n-1
Insert A[ j ] into the sorted sequence A[1 . . j -
0 n-1
1]
n2/2 comparisons c4 n-1
ij-1
c5
n
j 2 j
t
while i > 0 and A[i] > key
c6
n
(t j 1)
do A[i + 1] A[i] j 2
n2/2 exchanges c7
n
(t j 1)
ii1 j 2
c8 n-1
A[i + 1] key
14
SELECTION SORT
A very simple Algorithm
Selects smallest or largest element and places it on the
head of the array
Complexity O(n2) for best and worst case
SELECTION SORT
Idea:
Find the smallest element in the array
Exchange it with the element in the first position
Find the second smallest element and exchange it with the
element in the second position
Continue until the array is sorted
Disadvantage:
Running time depends only slightly on the amount of order
in the file
16
EXAMPLE
8 4 6 9 2 3 1 1 2 3 4 9 6 8
1 4 6 9 2 3 8 1 2 3 4 6 9 8
1 2 6 9 4 3 8 1 2 3 4 6 8 9
1 2 3 9 4 6 8 1 2 3 4 6 8 9
17
SELECTION SORT
Alg.: SELECTION-SORT(A)
8 4 6 9 2 3 1
n length[A]
for j 1 to n - 1
do smallest j
for i j + 1 to n
do if A[i] < A[smallest]
then smallest i
exchange A[j] A[smallest]
18
for(int x=0; x<n; x++)
{
int index_of_min = x;
for(int y=x; y<n; y++) {
if(array[index_of_min]>array[y]) {
index_of_min = y; }
}
int temp = array[x];
array[x] = array[index_of_min];
array[index_of_min] = temp;
}
ANALYSIS OF SELECTION SORT
Alg.: SELECTION-SORT(A) cost times
n length[A]
c1 1
for j 1 to n - 1
c2 n
do smallest j
c3 n-1
for i j + 1 to n
n2/2
do if A[i] < A[smallest] c4 nj11 (n j 1)
comparisons
then smallest i c5
n 1
j 1
(n j )
n
exchanges
exchange A[j] A[smallest] c6
n 1
j 1
(n j )
c7 n-1
n 1 n 1 n 1
T (n) c1 c2 n c3 (n 1) c4 (n j 1) c5 n j c6 n j c7 (n 1) 20
(n 2 )
j 1 j 1 j 2
BUBBLE SORT
Smaller elements bubble to the top of the list
Complexity O(n) for best case
Swaps the elements
Repeats the same steps
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1
if A[i-1] > A[i] then
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
BUBBLE-SORT RUNNING TIME
Alg.: BUBBLESORT(A)
for i 1 to length[A] c1
do for j length[A] downto i + 1 c2
Comparisons: do if A[j] < A[j -1] c3
n2/2 then exchange A[j] A[j-1] c4
Exchanges: n2/2
n
(n i )
n n
T(n) = c1(n+1) + c2 (n i 1) c3 (n i) c4
i 1 i 1 i 1
n
= (n) + (c2 + c2 + c4) (n i )
i 1
n n n
n ( n 1) n 2
n
where (n i) n i n 2
i 1 i 1 i 1 2 2 2
Thus,T(n) = (n2)
25
