Chapter 9- Sorting
Prof. Ashwini Rao
Asst. Prof. IT
Sorting
Refers to the operation of rearranging the contents of a list A
such that they are in increasing or decreasing.
If list A has n elements, there are n! ways the content can
appear in A.
The complexity of sorting algorithms measures the running
time as a function of the number n of items to be sorted.
Each sorting algorithm S will be made up of the following
operations.
Comparisons, which test whether Ai<Aj
Interchanges, which switch the contents of Ai and Aj
Assignments which set temp=Ai and then set Aj=Ai
Sorting Techniques
Bubble Sort
Insertion Sort
Bucket Sort
Radix Sort
Heap Sort
Radix Sort
Quick Sort
Bubble Sort
Traverse a collection of elements.
Move from the front to the end.
“Bubble” the largest value to the end using pair-wise
comparisons and swapping.
Bubble Sort
Example - Bubble Sort (Pass 1)
Example - Bubble Sort(Pass 1)
Example - Bubble Sort (After
N-1 Passes)
Number of comparisons, f(n)=(n-1)+(n-2)+……+2+1 = n(n-1)/2
Time complexity is thus O(n2)
Insertion Sort
Frequently used when n is small.
Algorithm: Insertion Sort(A,N)
1. set A[0]:= -∞
2. Repeat steps 3 to 5 for K=2,3…N
3. Set TEMP:=A[K] and PTR:=K-1
4. Repeat while TEMP<A[PTR]
a. set A[PTR+1]:=A[PTR]
b. PTR:=PTR-1
5. Set A[PTR+1]:=TEMP
6. Return
Example 1 - Insertion Sort
Ptr Temp
Example 2 - Insertion Sort
Number of comparisons, f(n)=1+2+……(n-1) = n(n-1)/2
Time complexity is thus O(n2)
Bucket Sort
Not a comparison sort of algorithm.
Sorting algorithm that works by distributing the elements of
an array into a number of buckets.
Each bucket is then sorted individually, either using a different
sorting algorithm, or by recursively applying the bucket
sorting algorithm.
Steps are:
Set up an array of initially empty "buckets".
Scatter: Go over the original array, putting each object in
its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back
into the original array.
Example: Bucket Sort
Time Complexity is O(n)
Worst case happens when all elements fall into the same bucket.
Radix Sort
Used mainly to alphabetize a large list of numbers.
Strategy used:
List of names is first sorted according to the first
letter of each name.
During second pass, each class is alphabetized
according to the second name letter of the name and
so on.
If no name contains more than 12 letters, the name are
alphabetized with at most 12 passes.
Example - Radix Sort
Units digit
Tens digit
Hundreds digit
Example - Radix Sort
Example - Radix Sort
Number of C of comparisons needed to sort 8 such 3 digit numbers is bounded as
follows:
C≤10*3*8
8 – Numbers for sorting
3 – Maximum of 3 digits in every number
10 – radix d=10 digits
C ≤ d*s*n
d: radix
S: Maximum number of digits in a number.
N: Number of digits to sort
Time complexity is thus O(n)
Heap and Heap Sort
Heap is a tree structure used in an elegant sorting
algorithm called heap sort.
If H is a complete binary tree, then H is called a
Heap or a Maxheap, if each node N of H has the
following property:
The value at N is ≥ value at any of the
descendants of N.
A Minheap is defined analogously.
Example – Heap & its
representation
Example: Building a Heap
To build a Heap H from the following list of numbers: 44,30,50,22,60,55,77,55
Insertion into a Heap
Steps to insert an ITEM into a Heap H with N nodes is as
follows:
First adjoin ITEM at the end of H so that H is still a
complete tree, but not necessarily a heap.
Then let ITEM rise to its appropriate place in H so
that H is finally a Heap.
Example: Insertion into a Heap
To insert ITEM 70 into the Heap
Example: Insertion into a Heap
Example: Deleting the root of a
Heap and Reheaping
Heap Sort
If A is an array of N elements, Heapsort algorithm to
sort A consists of the following two phases.
Phase A: build a heap H out of the elements of A.
Phase B: repeatedly delete the root element of H.
Quick Sort
Belongs to the category of Divide and Conquer
algorithms.
That is, problem of sorting a set is reduced to the problem
of sorting two smaller sets.
At every pass, this reduction step of the algorithm finds
the final position of one of the numbers.
As there would be approximately log2n levels of
reduction step, and each level uses at most n
comparisons, the complexity f(n)=O(n log n)
Example - Quick Sort
Example - Quick Sort