Data Structure

and Algorithm

COURSE CODE: CS-201

TOPIC: SORTING TECHNIQUES
Sorting- Introduction
Sorting is used to arrange names and numbers in meaningful ways.

Let A be a list of n elements A1, A2, ....... An in memory.

Sorting of list A refers to the operation of rearranging the contents of A so that they are in
increasing (or decreasing) order.
Sorting Techniques
Sorting can be performed in many ways.
Over a time several methods (or algorithms) are being developed to sort data(s).

Bubble sort,
Selection sort,
Quick sort,
Merge sort,
Heap sort
Binary sort,
Shell sort
Radix sort are the few sorting techniques
Bubble Sort
If N elements are given in memory then for sorting we do the following steps
1. First compare the 1st and 2nd element of array if 1st is greater than 2nd then compare 2nd with
3rd.
2. If 2nd >3rd then interchange the value of 2nd and 3rd
3. Now compare the value of 3rd(which has the value of 2nd) with 4th.
4. Similarly compare until the N-th element is compared with Nth element.
5. Now the highest value element is reached at the Nth place.
6. Now the elements will be compared until N-1 elements.
Bubble Sort
Bubble Sort
Bubble Sort
Bubble Sort
Bubble Sort
Bubble Sort

Time Complexity: O(N^2)

Selection Sort
In selection sort, the smallest value among the unsorted elements of
the array is selected in every pass and inserted to its appropriate
position into the array.
It is an in-place comparison sorting algorithm.
Selection Sort
Selection sort is generally used when -

A small array is to be sorted

Swapping cost doesn't matter
It is compulsory to check all elements
Working of Selection Sort
Working of Selection Sort
Working of
Selection Sort
Insertion Sort
Insertion sort algorithm sorts a set of values by inserting values into proper
place.
Works in the same way you organize cards.
You pick an unsorted card one at a time and insert it into its correct position
in your hand.
It is assumed that the first card is already sorted in the card game, and then
we select an unsorted card.
If the selected unsorted card is greater than the first card, it will be placed at
the right side; otherwise, it will be placed at the left side.
Similarly, all unsorted cards are taken and put in their exact place.

The same approach is applied in insertion sort.

 Working of
insertion sort
Insertion sort splits an array into two sub-arrays.
The first sub-array is always sorted and gets larger as the sort continues.
The second sub-array gets smaller as the sort progresses.
When the sort first begins the first elements in the array is considered to sorted
array.
With each iteration of the loop, the next value in the unsorted section is placed
into its proper position in the sorted section.
This sorting procedure is efficient for smaller values
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

19
Insertion Sort

20
Insertion Sort
INSERTION-SORT 1 2 3 4 5 6 7 8

a1 a2 a3 a4 a5 a6 a7 a8
Alg.: INSERTION-SORT(A)
for j = 2 to n
key
do key =A[ j ]
Insert A[ j ] into the sorted sequence A[1 . . j -1]
i=j-1
while i > 0 and A[i] > key
do A[i + 1] = A[i]
i=i–1
A[i + 1] = key
Insertion sort – sorts the elements in place
22
Example (ascending order)

Original
Array 76 3 94 55 21 1

Iteration 1
76 3 94 55 21 1

Iteration 2
S0: Swap 3 76 94 55 21 1

Iteration 3
3 76 94 55 21 1

94>55
Interchange 3 76 94 55 21 1
Cont . . .
Iteration 4
S0:Swap 3 76 55 94 21 1

55<76 True
Swap 3 55 76 94 21 1

55<3 No
Leave 3 55 76 94 21 1
Cont . . . .
Iteration 5
3 55 76 94 21 1

S0: True
Swap 3 55 76 21 94 1

21<76 True
Swap 3 55 21 76 94 1

21<55 True
Swap 3 21 55 76 94 1

21<3 No
Leave 3 21 55 76 94 1
Cont . . .
Iteration 6
3 21 55 76 94 1

S0: true
Swap 3 21 55 76 1 94

1<76 true
Swap 3 21 55 1 76 94

1<55 true
Swap 3 21 1 55 76 94

1<21 true
Swap 3 1 21 55 76 94

1<3 true
Swap 1 3 21 55 76 94

Sorted
1 3 21 55 76 94
Task :
Cont . . .
◦ Sort the following into descending order

Un Sorted
Array 7 5 2 4 3 9
 Merging
◦ If there are two sorted lists of array then process of combining these sorted
lists into sorted order is called merging.
◦ We can take this process with two approaches.
◦ First one, take the first array, after that take second array and sort them with
any sorting.
◦ But it is not useful because both the lists are sorted and we are taking them as
unsorted list.
◦ The second approach is to take one element of each array, compare them and
then take the smaller one in third array. Repeat this process until the elements
of any array are finished. Then take the remaining elements of unfinished array
in third array.
 Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.
smallest smallest

A G L O R H I M S T

A auxiliary
array
 Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G auxiliary
array
 Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G H auxiliary
array
 Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G H I auxiliary
array
 Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G H I L auxiliary
array
 Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G H I L M auxiliary
array
Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G H I L M O auxiliary
array
Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.

smallest smallest

A G L O R H I M S T

A G H I L M O R auxiliary
array
Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.
first half
exhausted smallest

A G L O R H I M S T

A G H I L M O R S auxiliary
array
Merging
Merge.
◦ Keep track of smallest element in each sorted half.
◦ Insert smallest of two elements into auxiliary array.
◦ Repeat until done.
first half
exhausted smallest

A G L O R H I M S T

A G H I L M O R S T auxiliary
array
Merge Sort
In second approach of merging, we can take the pair of consecutive array
elements, merge them in sorted array and then take adjacent pair of array
elements and so on until the all elements of array are in single list.
Merge Sort
Based on divide and conquer strategy

List is divided into two halves (Divide)

Each half is sorted independently (Conquer)

Two halves are merged into a sorted sequence.

Merge sort Algorithm
Merge sort Algorithm
Merge Sort

Step 1 − if it is only one element in the list it is already sorted, return.

Step 2 − divide the list recursively into two halves until it can no more
be divided.
Step 3 − merge the smaller lists into new list in sorted order.
Working of Merge
sort
Working of Merge
sort
Working of Merge
sort
Working of Merge
sort
Quick Sort Algorithm
Quick sort is a highly efficient sorting algorithm and is based on
partitioning of array of data into smaller arrays.
A large array is partitioned into two arrays one of which holds values
smaller than the specified value, say pivot, based on which the partition
is made and another array holds values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort
the two resulting subarrays.
This algorithm is quite efficient for large-sized data sets as its average
and worst-case complexity are O(n2), respectively.
 Quick Sort Basics
• Quick sort uses divide and conquer to gain the same
advantages as the merge sort.
• The list is logically divided in half.
• Pivot value
– A quick sort first selects any value from array , which is called
the pivot value.
 Step: 01 Pivot Value

• What is the pivot value in above array:

– First item of array
– Last item of array
– Select Pivot Randomly
• The pivot value is used to split the list.
Step 2: Left Mark and Right
Mark
 Step 3: Rule for Pivot value
• Left: The array element on the leftmark must be less than the pivot
value.

• Right: The Array element on Right Mark must be greater than the
pivot value.
 Step 4: Rule for Pivot value
• Left: The array element on the leftmark must be less than the
pivot value.

• Right: The pivot value must be greater than the array element on
the right side right side.
 Step 5: Rule for Pivot value
• Left: The array element on the leftmark must be less than
the pivot value.

• Right: The pivot value must be greater than the array

element on the right side right side.
 Step 6: Exchange
• Left: The array element on the leftmark must be less than the
pivot value.
• Right: The pivot value must be greater than the array element
on the right side right side.
 Step 7: Continue according to
rules
• Left: The array element on the leftmark must be less
than the pivot value.
• Right: The pivot value must be greater than the array
element on the right side right side.
 Step 8: Exchange
• Left: The array element on the leftmark must be less
than the pivot value.
• Right: The pivot value must be greater than the array
element on the right side right side.
 Step 9: Continue as per rules
• Left: The array element on the leftmark must be less
than the pivot value.
• Right: The pivot value must be greater than the array
element on the right side right side.
 Exercise

10 80 30 90 40 50 70