SORTING

SORTING

• Sorting is a process of arranging items of

the data structure in some sequence or
order. There are several sorting algorithm:
1. Bubble Sort 10.Bucket Sort
2. Selection Sort 11.Radix Sort
3. Insertion Sort 12.Distribution Sort
4. Merge Sort 13.Time Sort
5. Comb Sort
6. Shell Sort
7. Heap Sort
8. Quick Sort
9. Counting Sort
BUBBLE SORT

• The simplest sorting algorithm is bubble sort.

• It is not used for large or medium size data bases.
• Let A be a list of numbers. Sorting A refers to the
operation of arranging the elements of A so they
are in increasing order, so that
A[1]< A[2]< A[3]< A[4]<… A[N]
e.g. 32, 51, 27, 85, 66, 23, 13, 57
BUBBLE SORT

• (Bubble Sort) BUBBLE (DATA, N)

• Here DATA is an array with N elements. This
algorithm sort the elements in DATA.
• 1. Repeat the step 2 and 3 for K=1 to N-1
• 2. Set PTR=1 [Initialize pass pointer PTR]
• 3. repeat while PTR<=N-K
• a) if DATA[PTR]>DATA[PTR+1] then
interchange DATA[PTR] and DATA[PTR+1]
[end of if structure]
b) Set PTR=PTR+1
[end of inner loop]
[end of step 1 outer loop]
4. Exit
COMPLEXITY OF BUBBLE SORT

• Traditionally, Time of sorting algorithm is measured

in term of the number of comparisons.
• There are n-1 comparison in first pass which place
the largest element in the last position.
• There are n-2 comparison in second pass which place
the second largest element in the next to last
position and so on. Thus
• F(n)=(n-1)+(n-2)+…+2+1
• = n(n-1)/2
• =n2/2+O(n)
• =O(n2)
Time required to execute the bubble sort algorithm is
proportional to n2 . Where n is the number of input
items.
SELECTION SORT

• Suppose an array A with n elements

A[1], A[2],…, A[N]
The selection sort algorithm finds the smallest
element in the list and put it in the first position.
Then find the second smallest number in the list
and put it in the second position. And so on
EXAMPLE

Pass A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

K=1,Loc=4 77 33 44 11 88 22 66 55
K=2,Loc=6 11 33 44 77 88 22 66 55
K=3,Loc=6 11 22 44 77 88 33 66 55
K=4,Loc=6 11 22 33 77 88 44 66 55
K=5,Loc=8 11 22 33 44 88 77 66 55
K=6,Loc=7 11 22 33 44 55 77 66 88
K=7,Loc=7 11 22 33 44 55 66 77 88
sorted 11 22 33 44 55 66 77 88
• Procedure MIN(A,K,N,LOC) A is an Array in
memory. This procedure finds the location LOC of
the smallest element among A[k],A[k+1],…,A[N]
• 1- Set MIN=A[K] and LOC=K
• 2- Repeat for J=k+1,k+2 to N
If (MIN>A[J]) then
Set MIN=A[J] and LOC=J
3- Return
SELECTION SORT

• (selection sort)SELECTION(A,N)
• This algorithm sorts the array A with N Elements.
• 1- repeat step 2 and 3 for k=1,2,…,N-1
• 2- call MIN(A,K,N,LOC)
• 3- Interchange A[k] and A[LOC]
• [end of step 1loop]
• 4- Exit.
INSERTION SORT

• This algorithm scan Array A from A[1] to A[N], inserting

each element A[k] into its proper position in the
previously sorted subarray A[1],A[2]],…,A[k-1] that is
• Pass1 A[1] by itself is trivially sorted.
• Pass2 A[2] is inserted either before or after A[1] so that
A[1], A[2] is sorted.
• Pass3 A[3] is inserted in proper place in A[1],A[2] that
is before A[1],between A[1] and A[2] or after A[2] so
that A[1],A[2], A[3] is sorted
• - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - -
• PassN A[N] is inserted in to proper place in A[1], A[2],
…,A[N-1] so that A[1], A[2],…,A[N] is sorted.
EXAMPLE

Pass A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]
K=1 -∞ 77 33 44 11 88 22 66 55
K=2 -∞ 77 33 44 11 88 22 66 55
K=3 -∞ 33 77 44 11 88 22 66 55
K=4 -∞ 33 44 77 11 88 22 66 55
K=5 -∞ 11 33 44 77 88 22 66 55
K=6 -∞ 11 33 44 77 88 22 66 55
K=7 -∞ 11 22 33 44 77 88 66 55
K=8 -∞ 11 22 33 44 66 77 88 55
Sorted -∞ 11 22 33 44 55 66 77 88
INSERTION ALGORITHM

• (insertion Sort)INSERTION(A,N)
• This algorithm sort the array A with N elements.
• 1. repeat step 2 to 4 for k=1,2,3,….,N
• 2. Set TEMP=A[k] and PTR=K-1
• 3. Repeat while TEMP<A[PTR]
• a) Set A[PTR+1]=A[PTR]
• b) Set PTR=PTR-1
• [end of loop]
4. Set A[PTR+1]=TEMP [insert element in proper
place]
5. [end of step 1 loop]
6. Return
MERGING

• Suppose A is sorted list with r elements and B is a

sorted list with s elements. The operation that
combines elements of A and B into a single sorted
list C with n=r+s elements is called Merging.
• One simple way to merge is to place the elements
of B after the elements of A then use the sorting
algorithm on entire list.
MERGING ALGORITHM
• MERGING(A,R,B,S,C)
• Let A and B be sorted arrays with R and S elements
respectively. This algorithm merge A and B into an array C
with N=R+S elements.
• 1- [Initialize] Set NA=1,NB=1 and PTR=1
• 2- [compare] Repeat while NA<=R and NB<=S
• If(A[NA]<B[NB]) then
• a) [assign element from A to C] set C[PTR]=A[NA]
• b) [update pointer] set PTR=PTR+1 and NA=NA+1
• Else
• a) [assign element from B to C] set C[PTR]=B[NB]
• b) [update pointer] set PTR=PTR+1 and NB=NB+1
[End of Loop]
3- [Assign remaining elements to C]
If (NA> R ) then
Repeat for k=0,1,2,…,S-NB
Set C[PTR+k]= B[NB+k]
Else
Repeat for k=0,1,2,…,R-NA
COMB SORT

• Comb Sort is mainly an improvement over Bubble

Sort. Bubble sort always compares adjacent
values. So all inversions are removed one by one.
Comb Sort improves on Bubble Sort by using gap
of size more than 1. The gap starts with a large
value and shrinks by a factor of 1.3 in every
iteration until it reaches the value 1. Thus Comb
Sort removes more than one inversion count with
one swap and performs better than Bublle Sort.
• The shrink factor has been empirically found to
be 1.3 (by testing Comb sort on over 200,000
random lists)
INVERSION

• Inversion Count for an array indicates

• How far (or close) the array is from being
sorted. If array is already sorted then inversion
count is 0. If array is sorted in reverse order
that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j]
form an inversion if a[i] > a[j] and i < j
• Example:
The sequence 2, 4, 1, 3, 5 has three inversions
• (2, 1), (4, 1), (4, 3).
Initially gap value = 10
After shrinking gap value => 10/1.3 = 7;
8 4 1 56 3 -44 23 -6 28 0
-6 4 1 56 3 -44 23 8 28 0
-6 4 0 56 3 -44 23 8 28 1

New gap value => 7/1.3 = 5;

-44 4 0 56 3 -6 23 8 28 1
-44 4 0 28 3 -6 23 8 56 1
-44 4 0 28 1 -6 23 8 56 3
New gap value => 5/1.3 = 3;
-44 1 0 28 4 -6 23 8 56 3
-44 1 -6 28 4 0 23 8 56 3
-44 1 -6 23 4 0 28 8 56 3
-44 1 -6 23 4 0 3 8 56 28

New gap value => 3/1.3 = 2;

-44 1 -6 0 4 23 3 8 56 28
-44 1 -6 0 3 23 4 8 56 28
-44 1 -6 0 3 8 4 23 56 28
New gap value => 2/1.3 = 1;
-44 -6 1 0 3 8 4 23 56 28
-44 -6 0 1 3 8 4 23 56 28
-44 -6 0 1 3 4 8 23 56 28
-44 -6 0 1 3 4 8 23 28 56
no more swaps required
(Array sorted)
SHELL SORT

• Shell sort is a highly efficient sorting algorithm

and is based on insertion sort algorithm. This
algorithm avoids large shifts as in case of
insertion sort, if the smaller value is to the far
right and has to be moved to the far left.
• This algorithm uses insertion sort on a widely
spread elements, first to sort them and then sorts
the less widely spaced elements. This spacing is
termed as interval. This interval is calculated
based on Knuth's formula as
• Knuth's Formula
• h = h * 3 + 1 where h is interval with initial value
1
HOW SHELL SORT WORKS?

• The values of an Array are

• 35 33 42 10 14 19 27 44
• Make a virtual sub-list of all values located at the
interval of 4 positions.
• Here these values are
• {35, 14}, {33, 19}, {42, 27} and {10, 14}
• According to following slide
• We compare values in each sub-list and swap
them (if necessary) in the original array. After this
step, the new array should look like this
• Then, we take interval of 2 and this gap
generates two sub-lists {14, 27, 35, 42}, {19,
10, 33, 44}
`

• We compare and swap the values, if required, in

the original array. After this step, the array should
look like this