Sorting Algorithms
Bubble, Insertion, Selection, Quick,
Merge, Bucket, Radix, Heap
Bubble Sort
• It works by comparing adjacent elements of an array
and exchanges them if they are not in order.
• After each iteration(pass),the largest element sinks to
the last position of the array. In next iteration second
largest element sinks to the second last position and
so on.
• Worst case and average case complexity is O(n2).
• Best case complexity is O(n) (In case of already
sorted array).
2
Bubble Sort
Pass 1
0 1 2 3 4 5
42
77 77
42 35 12 101 5
Bubble Sort
Pass 1
0 1 2 3 4 5
42 35
77 77
35 12 101 5
Bubble Sort
Pass 1
0 1 2 3 4 5
42 35 12
77 77
12 101 5
Bubble Sort
Pass 1
0 1 2 3 4 5
42 35 12 77 101 5
No need to swap
Bubble Sort
Pass 1
0 1 2 3 4 5
42 35 12 77 5
101 101
5
Bubble Sort
Result after Pass 1 is
0 1 2 3 4 5
42 35 12 77 5 101
Largest value correctly placed
Algorithm
BUBBLE SORT(A)
Step 1: Repeat For I=0 to N-1 do
Repeat For J=0 to N-I-2 do
If A[J]>A[J+1] then
swap A[J+1] and A[J]
End If
Done
Done
Step 2: PRINT A
Step 3: Exit
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
Insertion Sort
• It considers the number one by one from the start. If it is single
number then it is sorted by default.
• Then we consider the next number and put it in proper position
and now the list of two is sorted. Then we consider the third
number and so on.
• Before examining the record Rj , we assume that the preceding
records R1 to Rj-1 have already been sorted and we insert Rj
into its proper place among the previously sorted records.
13
Insertion Sort
P1 P2 P3 P4 P5 P6 P7
14
Algorithm
INSERTION SORT(A)
#A is the array with N elements to be sorted
Step 1: Repeat For J=1 to N-1 do
Set key=A[J]
Set I=J-1
Repeat While I>=0 AND A[I]>key do
Set A[I+1]=A[I]
Set I=I-1
Done
Set A[I+1]=key
Done
Step 2: PRINT A
Step 3: Exit 15
Insertion Sort
• Worst case and average case complexity is O(n2).
Inserting in between is costly because we have to
move remaining elements.
• Best case O(n). Works well for nearly sorted lists.
• Good for cases where whole data is not available
initially and new data values keep on adding in the
list.
16
Selection Sort
• Selection sort works by selecting the minimum from
the given sequence and swapping it with the first
element in the list.
• Then again selecting the minimum from the last n-1
element and swapping it with the second element in
the list and so on.
• Complexity is O(n2) in best, worst and average case
17
Selection Sort : Example
8 4 6 9 2 3 1
After P1 1 4 6 9 2 3 8
After P2 1 2 6 9 4 3 8
After P3 1 2 3 9 4 6 8
After P4 1 2 3 4 9 6 8
After P5 1 2 3 4 6 9 8
After P6 1 2 3 4 6 8 9
After P7 1 2 3 4 6 8 9
18
Algorithm
SELECTION SORT(A)
#A is the array with n element to be sorted
Step 1: Repeat For i=0 to N-1 do
Set min=i
Repeat For j=i+1 to N-1 do
If A[j]<A[min] then
set min=j
End If
Done
If (A[i]>A[min]) then
swap A[i] and A[min]
EndIf
Done
Step 3: PRINT A
Step 4: Exit 19
Given sequence of numbers: 6, 18, 4, 10, 3, 2, 14.
Find the sequence of numbers after Pass 4 if the sorting
(increasing order) used is:
•Bubble
•Insertion
•Selection
For reference: https://visualgo.net/en/sorting
20
Merge Sort
• Merge sort takes advantage of the ease of merging
already sorted lists into a new sorted list.
• It is a divide and conquer algorithm. It can be easily
parallelized. It takes advantage of the fact if numbers are
already sorted.
• It works better because it deals with smaller lists instead
of the full list.
• Its worst and average case running time is O(n log n). It is
better than previously discussed algorithms.
Algorithm
MERGE-SORT(A)
Step 1: If length[A]==1 then
Return A
Else
q=int(Length[A]/2)
Create arrays L[1..q] and R[q+1..length[A]]
copy A[1..q] to L
copy A[q+1.. length[A]] to R
LS=MERGE-SORT(L)
RS=MERGE-SORT(R)
Return Merge(LS, RS)
Step 2: Exit
Merge(L,R)
Step 1: Create array B of length[L] + length[R]
Step 2: Set i=1, j=1
Step 3: For k= 1 to length[B] do
If j> length[R] or ( i<=length[L] and L[i]<=R[j] ) then
B[k]=L[i]
i=i+1
Else
B[k]=R[j]
j=j+1
Step 4: Return B
At the end of each iteration of for loop in step 3 the sub array B[1..k] contains smallest k elements k elements
from L and R in sorted order
