Divide and Conquer
(Sorting-Linear Time)
Sorting
• Given a list of data element <a 1 ,a 2 ,…,a n >,
which can be arranged in n! way.
• Taking one permutation <ak1,ak2,…akn> which
are sorted (aki<akj)
• Internal Sorting (sorted in RAM)
• External Sorting (hardisk)
Sorting
In-Place: If constant number of data elements of
an input are ever stored outside array (no
additional storage is required and hence it is
possible to sort a large list without need of
additional working storage)
Stable: two elements that are equal remain in the
same relative position after performing the
sorting
Sorting
Comparison Based: If an operation of comparing two
keys can be performed on a given list of data elements
having keys. So to find relative order of given two
elements a i and a j , we have to perform following
test(<,>,<=,>=,==)
• Quick sort
• Insertion sort
• Heap sort
• Merge sort
The Decision tree model
• It can be used to represent any comparison based
algorithm behaviour on an input of certain size.
• We only consider comparison in the algorithm
Sorting
Non-Comparison Based: If an operation of comparing
two keys can be performed on a given list of data
elements having keys. So to find relative order of given
two elements ai and aj , we have to perform following
test(<,>,<=,>=,==)
• Counting sort
• Radix sort
• Bucket sort
Counting Sort
This algorithm sorts the array a[1], ... , a[n] of integers, each in
the range 0 to m, inclusive.
Input Parameters: a,m
Output Parameters: a
counting_sort(a,m) {
// set c[k] = the number of occurrences of value k
// in the array a.
// begin by initializing c to zero.
for k = 0 to m
c[k] = 0
n = [Link]
for i = 1 to n
c[a[i]] = c[a[i]] + 1
// modify c so that c[k] = number of elements ≤ k
for k = 1 to m
c[k] = c[k] + c[k - 1]
// sort a with the result in b
for i = n downto 1 {
b[c[a[i]]] = a[i]
c[a[i]] = c[a[i]] - 1
}
// copy b back to a
for i = 1 to n
a[i] = b[i]
}
Counting Sort
Procedure Counting Sort (A, k) :
The above Procedure sorts the input elements by determining the correct position of an element in a range.
Three arrays, Ain, Aout and Ctemp are used, for holding input elements, for storing ouput elements, and for
providing temporary working storage, respectively.
Step 1 Initilaization, loop
for i ¬ 1 to k
set Ctemp [i]¬ 0.
Step 2 Ctemp holds number of elements equal to j, loop
for i ¬ 1 to n
set Ctemp [Ain [i]] ¬ Ctemp [Ain [i]] + 1
Step 3 Ctemp holds number of element less than or equal to j, loop
for i ¬ 1 to k
set Ctemp [i] ¬ Ctemp [1] + Ctemp [2] + ... + Ctemp [i]
Step 4 Placing at proper position, loop.
for i ¬ 1 to n
set index ¬ Ctemp [Ain [i]]
where to put Ain [i]
set Aout [index] ¬ Ain [i]
put Ain [i] in a position Aout [index]
set Ctemp [Ain [i] ¬ Ctemp [Ain [i]] – 1
decrement count Ctemp [Ain [i]].
Step 5 Return at the point of call
return.
Radix sort
This algorithm sorts the array
a[1], ... , a[n]
of integers. Each integer has at most k digits.
Input Parameters: a,k
Output Parameters: a
radix_sort(a,k) {
for i = 0 to k - 1
counting_sort(a,10) // key is digit in 10i’s place
}
Radix sort
Procedure Radix sort (A, d) :
The above procedure assumes that each element in the n-element array A has d
digits, where digit 1 is the low order digit and digit d is the high order digit.
Step 1 Loop, internal sort.
for i ¬ 1 to d
perform stable sort to sort and Array A on digit i.
Bucket Sort
• Works on floating point number between range 0 to 1.0
• Input should be uniformly and independently distributed across [0,1] to get a
running time of O(n)
Procedure Bucket Sort (A) :
The above procedure assumes that the input is an n-element array A, such that each
element A [1] satisfies 0 £ A [i] < 1. It also assumes that there is an auxillary array B, to
which these elements are mapped, which is an array of linked lists called buckets
which stores the sorted values.
Step 1 Initialization
set n ¬ length [A]
Step 2 insertion at proper place, loop
for i ¬ 1 to n
insert element A [i] into list B [ ë n A [i] û ]
Step 3 sort the list, loop
for i ¬ 0 to n – 1
sort list B [i] using insertion sort.
Step 4 sorting, combining.
concatenate list B [0], B [1], .... B [n – 1] together in order.