Sorting Algorithms
Dr. Abdul Majid
adlmjd@[Link]
1
Data Structures & Algorithms
Sorting Algorithms
An algorithm is designed to achieve
optimum solution for a given problem.
A basic solution that satisfies all the constraints
defining or in other words, one that lies within is called
a basic feasible solution.
An optimal solution is a feasible solution where the
objective function reaches its maximum (or minimum)
value – for example, the most profit or the least cost.
A globally optimal solution is one where there are no
other feasible solutions with better objective function
values.
2
Data Structures & Algorithms
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’
3
Data Structures & Algorithms
Some Definitions
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.
4
Data Structures & Algorithms
Sorting Algorithms
Sorting Algorithms
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort
Shell Sort
5
Data Structures & Algorithms
Bubble Sort ()
Idea:
Repeatedly pass through the array
Swaps adjacent elements that are out of order
i
1 2 3 n
8 4 6 9 2 3 1
Easier to implement, but slowerj than Insertion sort
Visualize :
[Link]
g/bubble-sort/visualize/
6
Example
8 4 6 9 2 3 1 1 8 4 6 9 2 3
i=1 j i=2 j
8 4 6 9 2 1 3 1 2 8 4 6 9 3
i=1 j i=3 j
8 4 6 9 1 2 3 1 2 3 8 4 6 9
i=1 j i=4 j
8 4 6 1 9 2 3 1 2 3 4 8 6 9
i=1 j i=5 j
8 4 1 6 9 2 3 1 2 3 4 6 8 9
i=1 j i=6 j
8 1 4 6 9 2 3 1 2 3 4 6 8 9
i=1 j i=7
j
1 8 4 6 9 2 3
i=1 j
7
Data Structures & Algorithms
Bubble Sort
Alg.: BUBBLESORT(A)
for i 1 to length[A]
do for j length[A] downto i + 1
do if A[j] < A[j -1]
then exchange A[j] A[j-1]
i
8 4 6 9 2 3 1
i=1 j
8
Data Structures & Algorithms
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
9
Insertion Sort
To insert 12, we need to
make room for it by moving
first 36 and then 24.
6 10 24 36
12
10
Insertion Sort
6 10 24 36
12
11
Insertion Sort
6 10 24 3
6
12
12
Data Structures & Algorithms
Insertion Sort
input array
5 2 4 6 1
3
at each iteration, the array is divided in two
sub-arrays:
left sub-array right sub-array
sorted unsorted
13
Data Structures & Algorithms
14
Insertion Sort
Data Structures & Algorithms
INSERTION-SORT
1 2 3 4 5 6 7 8
a1 a2 a3 a4 a5 a6 a7 a8
key
15
Data Structures & Algorithms
Insertion Sort - Summary
Advantages
Good running time for “almost sorted” arrays
(n)
Disadvantages
(n2) running time in worst and average case
16
Data Structures & Algorithms
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
17
1
8
Data Structures & Algorithms
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
18
Data Structures & Algorithms
Selection Sort
Alg.: SELECTION-SORT(A)
n ← length[A]
for j ← 1 to n - 1 8 4 6 9 2 3 1
do smallest ← j
for i ← j + 1 to n
do if A[i] < A[smallest]
then smallest ← i
exchange A[j] ↔ A[smallest]
19
Data Structures & Algorithms
Sorting algorithms
Heap Sort
Quick Sort
Merge Sort
Shell Sort
Comb Sort
Counting Sort
Bucket Sort
Many more……
20