Searching and Sorting

© Oxford University Press 2014. All rights

 Linear Search

LINEAR_SEARCH(A, N, VAL, POS)

Step 1: [INITIALIZE] SET POS = -1

Step 2: [INITIALIZE] SET I = 0
Step 3: Repeat Step 4 while I<N
Step 4: IF A[I] = VAL, then
SET POS = I
PRINT POS
Go to Step 6
[END OF IF]
[END OF LOOP]
Step 5: PRINT “Value Not Present In The Array”
Step 6: EXIT

© Oxford University Press 2014. All rights

 Binary Search
BEG = lower_bound and END = upper_bound
MID = (BEG + END) / 2
If VAL < A[MID], then VAL will be present in the left segment of the array.
So,
the value of END will be changed as, END = MID – 1
If VAL > A[MID], then VAL will be present in the right segment of the
array. So,
the value of BEG will be changed as, BEG = MID + 1

© Oxford University Press 2014. All rights

 Binary Search

BINARY_SEARCH(A, lower_bound, upper_bound, VAL, POS)

Step 1: [INITIALIZE] SET BEG = lower_bound, END = upper_bound, POS = -1

Step 2: Repeat Step 3 and Step 4 while BEG <= END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL, then
POS = MID
PRINT POS
Go to Step 6
IF A[MID] > VAL then;
SET END = MID - 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]
Step 5: IF POS = -1, then
PRINTF “VAL IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT

© Oxford University Press 2014. All rights

 Binary Search
int A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
and VAL = 9, the algorithm will proceed in the following manner.
BEG = 0, END = 10, MID = (0 + 10)/2 = 5
Now, VAL = 9 and A[MID] = A[5] = 5
A[5] is less than VAL, therefore, we will now search for the value in the
later half of the array. So, we change the values of BEG and MID.
Now, BEG = MID + 1 = 6, END = 10, MID = (6 + 10)/2 =16/2 = 8
Now, VAL = 9 and A[MID] = A[8] = 8
A[8] is less than VAL, therefore, we will now search for the value in the
later half of the array. So, again we change the values of BEG and MID.
Now, BEG = MID + 1 = 9, END = 10, MID = (9 + 10)/2 = 9
Now VAL = 9 and A[MID] = 9.
Now VAL = 9 and A[MID] = 9.

© Oxford University Press 2014. All rights

 Sorting
• The term sorting means arranging the elements of the array so that
they are placed in some relevant order which may either be ascending
order or descending order. That is, if A is an array then the elements of
A are arranged in sorted order (ascending order) in such a way that,
A[0] < A[1] < A[2] < …… < A[N]

• For example, if we have an array that is declared and initialized as,

int A[] = {21, 34, 11, 9, 1, 0, 22};

• Then the sorted array (ascending order) can be given as, A[] = {0, 1, 9,
11, 21, 22, 34}

© Oxford University Press 2014. All rights

 Sorting
• A sorting algorithm is defined as an algorithm that puts elements of a list in
a certain order (that can either be numerical order, lexicographical order or
any user-defined order). Efficient sorting algorithms are widely used to
optimize the use of other algorithms like search and merge algorithms
which require sorted lists to work correctly. There are two types of sorting:

• Internal sorting which deals with sorting the data stored in computer’s
memory

• External sorting which deals with sorting the data stored in files. External
sorting is applied when there is voluminous data that cannot be stored in
computer’s memory.

© Oxford University Press 2014. All rights

 Bubble Sort
• Bubble sort is a very simple method that sorts the array elements by repeatedly moving the
largest element to the highest index position of the array (in case of arranging elements in
ascending order).

• In bubble sorting, consecutive adjacent pairs of elements in the array are compared with each
other. If the element at lower index is greater than the element at the higher index, the two
elements are interchanged so that the smaller element is placed before the bigger one. This
process is continued till the list of unsorted elements exhaust.

© Oxford University Press 2014. All rights

 Bubble Sort Example
To discuss the bubble sort let us consider an array that has the following elements
A[] = {30, 52, 29, 87, 63, 27, 18, 54}
Pass 1:
Compare 30 and 52. Since30<52, then no swapping is done
Compare 52 and 29. Since 52>29, swapping is done
30, 29, 52, 87, 63, 27, 19, 54
c) Compare 52 and 87. Since 52<87, no swapping is done
d) Compare, 87 and 63. Since, 87>83, swapping is done
30, 29, 52, 63, 87, 27, 19, 54
e) Compare87 and 27. Since 87>27, swapping is done
30, 29, 52, 63, 27, 87, 19, 54
f) Compare 87 and 19. Since 87>19, swapping is done
30, 29, 52, 63, 27, 19, 87, 54
g) Compare 87 and 54. Since 87>54, swapping is done
30, 29, 52, 63, 27, 19, 54, 87
Observe that after the end of the first pass, the largest element is placed at the highest index of the
array. All the other elements are still unsorted.

© Oxford University Press 2014. All rights

 Bubble Sort Example
Pass 2:
Compare 30 and 29. Since 30>29, swapping is done
29, 30, 52, 63, 27, 19, 54, 87
b) Compare 30 and 52. Since 30<52, no swapping is done
c) Compare 52 and 63. Since 52<63, no swapping is done
d) Compare 63 and 27. Since 63>27, swapping is done
29, 30, 52, 27, 63, 19, 54, 87
e) Compare 63 and 19. Since 63>19, swapping is done
29, 30, 52, 27, 19, 63, 54, 87
f) Compare 63 and 54. Since 63>54, swapping is done
29, 30, 52, 27, 19, 54, 63, 87
Observe that after the end of the second pass, the second largest element is placed at the second highest index of
the array. All the other elements are still unsorted.

© Oxford University Press 2014. All rights

 Bubble Sort Example
Pass 3:
Compare 29 and 30. Since 29<30, no swapping is done
Compare 30 and 52. Since 30<52, no swapping is done
Compare 52 and 27. Since 52>27, swapping is done
29, 30, 27, 52, 19, 54, 63, 87
d) Compare 52 and 19. Since 52>19, swapping is done
29, 30, 27, 19, 52, 54, 63, 87
e) Compare 52 and 54. Since 52<54, no swapping is done
Observe that after the end of the third pass, the third largest element is placed at the third highest index of the
array. All the other elements are still unsorted.

© Oxford University Press 2014. All rights

 Bubble Sort Example
Pass 4:
Compare 29 and 30. Since 29<30, no swapping is done
Compare 30 and 27. Since 30>27, swapping is done
29, 27, 30, 19, 52, 54, 63, 87
c) Compare 30 and 19. Since 30>19, swapping is done
29, 27, 19, 30, 52, 54, 63, 87
d) Compare 30 and 52. Since 30<52, no swapping is done

Observe that after the end of the fourth pass, the fourth largest element is placed at the fourth highest index of the
array. All the other elements are still unsorted.

© Oxford University Press 2014. All rights

Bubble Sort Example

BUBBLE_SORT(A, N)

Step 1: Repeat steps 2 For I = 0 to N-1

Step 2: Repeat For J = 0 to N – I
Step 3: If A[J] > A[J + 1], then
SWAP A[J] and A[J+1]
[End of Inner Loop]
[End of Outer Loop]
Step 4: EXIT

© Oxford University Press 2014. All rights

 Complexity of Bubble Sort
• The complexity of any sorting algorithm depends upon the number of
comparisons that are made. In bubble sort, we have seen that there are total
N-1 passes. In the first pass, N-1 comparisons are made to place the highest
element in its correct position. Then in Pass 2, there are N-2 comparisons and
the second highest element is placed in its position. Therefore, to compute the
complexity of the bubble sort, we need to calculate the total number of
comparisons made. For this purpose, the number f(n) of comparisons made
can be given as,

f(n) = (n – 1) + (n – 2) + (n – 3) + ….. + 3 + 2 + 1 = n (n – 1)/2 = n2/2 + O(n) = O(n2)

• Therefore, the complexity of a bubble sort algorithm is O(n2), this means that
to execute, bubble sort require time that is proportional to n2, where n is the
total number of elements in the array

© Oxford University Press 2014. All rights

 Insertion Sort
• Insertion sort is a very simple sorting algorithm, in which the sorted array (or list)
is built one element at a time.
• Insertion sort works as follows.
• The array of values to be sorted is divided into two sets. One that stores sorted
values and the other contains unsorted values.
• The sorting algorithm will proceed until there are elements in the unsorted set.
• Suppose there are n elements in the array. Initially the element with index 0
(assuming LB, Lower Bound = 0) is in the sorted set, rest all the elements are in
the unsorted set
• The first element of the unsorted partition has array index 1 (if LB = 0)
• During each iteration of the algorithm, the first element in the unsorted set is
picked up and inserted into the correct position in the sorted set.

© Oxford University Press 2014. All rights

 Insertion Sort
Example: Consider an array of integers given below. Sort the values in
the array using insertion sort.

39 9 45 63 18 81 108 54 72 36

39 9 45 63 18 81 108 54 72 36

© Oxford University Press 2014. All rights

 Insertion Sort
9 39 45 63 18 81 108 54 72 36

9 39 45 63 18 81 108 54 72 36

9 39 45 63 18 81 108 54 72 36

9 18 39 45 63 81 108 54 72 36

9 18 39 45 63 81 108 54 72 36

9 18 39 45 63 81 108 54 72 36

9 18 39 45 54 63 81 108 72 36

9 18 39 45 54 63 72 81 108 36

9 18 36 39 45 54 63 72 81 108

© Oxford University Press 2014. All rights

 Insertion Sort
Note : In Pass 1, A[0] is the only element in the sorted set.
In Pass 2, A[1] will be placed either before or after A[0], so that the array A is sorted
In Pass 3, A[2] will be placed either before A[0], in-between A[0] and A[1] or after
A[1], so that the array is sorted.
In Pass 4, A[4] will be placed in its proper place so that the array A is sorted.

In Pass N, A[N-1] will be placed in its proper place so that the array A is sorted.
Therefore, we conclude to insert the element A[K] is in the sorted list A[0], A[1], ….
A[K-1], we need to compare A[K] with A[K-1], then with A[K-2], then with A[K-3]
until we meet an element A[J] such that A[J] <= A[K].
In order to insert A[K] in its correct position, we need to move each element A[K-1],
A[K-2], …., A[J] by one position and then A[K] is inserted at the (J+1)th location.
© Oxford University Press 2014. All rights
 Insertion Sort

Insertion sort (ARR, N) where ARR is an array of N elements

Step 1: Repeat Steps 2 to 5 for K = 1 to N

Step 2: SET TEMP = ARR[K]
Step 3: SET J = K – 1
Step 4: Repeat while TEMP <= ARR[J]
SET ARR[J + 1] = ARR[J]
SET J = J – 1
[END OF INNER LOOP]
Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]
Step 6: EXIT

© Oxford University Press 2014. All rights

Complexity of Insertion Sort Algorithm
• For an insertion sort, the best case occurs when the array is already sorted. In
this case the running time of the algorithm has a linear running time (i.e., O(n)).
This is because, during each iteration, the first element from unsorted set is
compared only with the last element of the sorted set of the array.

• Similarly, the worst case of the insertion sort algorithm occurs when the array is
sorted in reverse order. In the worst case, the first element of the unsorted set
has to be compared with almost every element in the sorted set. Furthermore,
every iteration of the inner loop will have to shift the elements of the sorted set
of the array before inserting the next element. Therefore, in the worst case,
insertion sort has a quadratic running time (i.e., O(n2)).

• Even in the average case, the insertion sort algorithm will have to make at least
(K-1)/2 comparisons. Thus, the average case also has a quadratic running time.

© Oxford University Press 2014. All rights

 Selection Sort
• Consider an array ARR with N elements. The selection sort takes N-1 passes to
sort the entire array and works as follows. First find the smallest value in the
array and place it in the first position. Then find the second smallest value in the
array and place it in the second position. Repeat this procedure until the entire
array is sorted. Therefore,
• In Pass 1, find the position POS of the smallest value in the array and then swap
ARR[POS] and ARR[0]. Thus, ARR[0] is sorted.
• In pass 2, find the position POS of the smallest value in sub-array of N-1
elements. Swap ARR[POS] with ARR[1]. Now, A[0] and A[1] is sorted
• In pass 3, find the position POS of the smallest value in sub-array of N-2
elements. Swap ARR[POS] with ARR[2]. Now, ARR[0], ARR[1] and ARR[2] is
sorted
• In pass N-1, find the position POS of the smaller of the elements ARR[N-2] and
ARR[N-1}. Swap ARR[POS] and ARR[N-2] so that ARR[0], ARR[1], … , ARR[N-1] is
sorted.

© Oxford University Press 2014. All rights

 Selection Sort
Example: Sort the array given below using selection sort

39 9 81 45 90 27 72 18

PASS LOC ARR[0] ARR[1] ARR[2] ARR[3] ARR[4] ARR[5] ARR[6] ARR[7]
1 1 9 39 81 45 90 27 72 18
2 7 9 18 81 45 90 27 72 39
3 5 9 18 27 45 90 81 72 39
4 7 9 18 27 39 90 81 72 45
5 7 9 18 27 39 45 81 72 90
6 6 9 18 27 39 45 72 81 90

© Oxford University Press 2014. All rights

 Selection Sort
SMALLEST (ARR, K, N, POS)

Step 1: [Initialize] SET SMALL = ARR[K]

Step 2: [Initialize] SET POS = K
Step 3: Repeat for J = K+1 to N
IF SMALL > ARR[J], then
SET SMALL = ARR[J]
SET POS = J
[END OF IF]
[END OF LOOP]
Step 4: Exit

Selection Sort to sort an array ARR with N elements

Step 1: Repeat Steps 2 and 3 for K =1 to N-1

Step 2: CALL SMALLEST(ARR, K, N, POS)
Step 3: SWAP A[K] with ARR[POS]
[END OF LOOP]
Step 4: Exit

© Oxford University Press 2014. All rights

Complexity of Selection Sort Algorithm
• Selection sort is a sorting algorithm that is independent of the
original order of the elements in the array. In pass 1, selecting the
element with smallest value calls for scanning all n elements; thus,
n-1 comparisons are required in the first pass.

• Then, the smallest value is swapped with the element in the first
position. In pass 2, selecting the second smallest value requires
scanning the remaining n − 1 elements and so on. Therefore,

• (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 = Θ(n2) comparisons

© Oxford University Press 2014. All rights

 Merge Sort
• Merge sort is a sorting algorithm that uses the divide, conquer and combine algorithmic paradigm. Where,

• Divide means partitioning the n-element array to be sorted into two sub-arrays of n/2 elements in each
sub-array. (If A is an array containing zero or one element, then it is already sorted. However, if there are
more elements in the array, divide A into two sub-arrays, A1 and A2, each containing about half of the
elements of A).

• Conquer means sorting the two sub-arrays recursively using merge sort.

• Combine means merging the two sorted sub-arrays of size n/2 each to produce the sorted array of n
elements.

© Oxford University Press 2014. All rights

 Merge Sort
• Merge sort algorithms focuses on two main concepts to improve its performance
(running time):
• A smaller list takes few steps and thus less time to sort than a large list.
• Less steps, thus less time is needed to create a sorted list from two sorted lists rather
than creating it using two unsorted lists.

The basic steps of a merge sort algorithm are as follows:

• If the array is of length 0 or 1, then it is already sorted. Otherwise:
• (Conceptually) divide the unsorted array into two sub- arrays of about half the size.
• Use merge sort algorithm recursively to sort each sub-array
• Merge the two sub-arrays to form a single sorted list

© Oxford University Press 2014. All rights

 Merge Sort
Example: Sort the array given below using merge sort
9 9 81 45 90 27 72 18

Divide and conquer the array

39 9 81 45 90 27 72 18

39 9 81 45
90 27 72 18

90 27 72 18
39 9 81 45

90 27 72 18
39 9 81 45

39 9 81 45 00 27 18 72

9 39 45 81 27 90 18 72

9 39 45 81 18 27 72 90

9 18 39 45 72 81 90

Combine the elements to form a sorted array

© Oxford University Press 2014. All rights
 Merge Sort
• To understand the merge algorithm, consider figure 14.4 which
shows how we merge two lists to form one list. For the sake of
understanding we have taken two sub-lists each containing four
elements. The same concept can be utilized to merge 4 sub-lists
containing two elements, and eight sub-lists having just one
element.
9 39 45 81 18 27 72 90
BEG, I MID J
END

TEMP

INDEX

9 39 45 81 18 27 72 90

BEG I mID J END

© Oxford University Press 2014. All rights

 Merge Sort
TEMP

9 18

INDEX
9 39 45 81 18 27 72 90
BEG I Mid J END
TEMP

9 18 27

INDEX

9 39 45 81 18 27 72 90
BEG I Mid J END
TEMP

9 18 27 39

INDEX

© Oxford University Press 2014. All rights

 Merge Sort
9 39 45 81 18 27 72 90

BEG I Mid J END

9 18 27 39 45

INDEX

9 39 45 81 18 27 72 90

BEG I,Mid J END

9 18 27 39 45 72

INDEX

When I is greater than MID copy the remaining elements of the right sub-array in TEMP

9 18 27 39 45 72 72 81 90
INDEX

© Oxford University Press 2014. All rights

 Merge Sort
MERGE (ARR, BEG, MID, END)

Step 1: [Initialize] SET I = BEG, J = MID + 1, INDEX = 0

Step 2: Repeat while (I <= MID) AND (J<=END)
IF ARR[I] < ARR[J], then
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[END OF IF]
SET INDEX = INDEX + 1
[END OF LOOP]
Step 3: [ Copy the remaining elements of right sub-array, if any] IF I > MID, then
Repeat while J <= END
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[END OF LOOP]
[Copy the remaining elements of left sub-array, if any] Else
Repeat while I <= MID
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[END OF LOOP]
[END OF IF]
Step 4: [Copy the contents of TEMP back to ARR] SET K=0
Step 5: Repeat while K < INDEX
a. SET ARR[K] = TEMP[K]
b. SET K = K + 1
[END OF LOOP]
Step 6: END

© Oxford University Press 2014. All rights

 Merge Sort

MERGE_SORT( ARR, BEG, END)

Step 1: IF BEG < END, then

SET MID = (BEG + END)/2
CALL MERGE_SORT( ARR, BEG, MID)
CALL MERGE_SORT (ARR, MID + 1, END)
MERGE (ARR, BEG, MID, END)
[END OF IF]
Step 2: END

© Oxford University Press 2014. All rights

Complexity of Merge Sort Algorithm
• The running time of the merge sort algorithm in average case and worst
case can be given as O(n logn). Although algorithm merge sort has an
optimal time complexity but a major drawback of this algorithm is that
it needs an additional space of O(n) for the temporary array TEMP

© Oxford University Press 2014. All rights

 Quick Sort
• Quicksort is a widely used sorting algorithm developed by C. A. R. Hoare that makes
O(nlogn) comparisons in average case to sort an array of n elements. However, in the
worst case, quick sort algorithm has quadratic running time given as O(n2). Basically, the
quick sort algorithm is faster than other O(nlogn) algorithms, because efficient
implementation of the algorithm can minimize the probability of requiring quadratic
time.
The quick sort algorithm works as follows:
• Select an element pivot from the array elements
• Re-arrange the elements in the array in such a way that all elements that are less than
the pivot appear before the pivot and all elements greater than the pivot element come
after it (equal values can go either way). After such a partitioning, the pivot is placed in its
final position. This is called the partition operation.
• Recursively sort the two sub-arrays thus obtained. (One with sub-list of lesser value than
that of the pivot element and the other having higher value elements).

© Oxford University Press 2014. All rights

 Quick Sort
• The main task in the quick sort algorithm is to find the pivot element, which will partition the
array into two halves. To understand how we find the pivot element follow the steps given
below. (we will take the first element in the array as pivot)

• Set the index of the first element in the array to loc and left variables. Also set the index of
the last element of the array to the right variable.

• That is, loc =0, left = 0 and right = n-1 (where n in the number of elements in the array)

• Start from the element pointed by right and scan the array from right to left, comparing each
element on the way with the element pointed by variable loc.

• That is, a[loc]should be less than a[right]. If that is the case then simply continue comparing
until right becomes equal to loc. Because once right = loc, then it means the pivot has been
placed in its correct position.

© Oxford University Press 2014. All rights

 Quick Sort
• However, if at any point we have a[loc]>a[right] then, interchange the two values and jump to step
3.

• Set loc = right

• Start from the element pointed by left and scan the array from left to right, comparing each element on
the way with the element pointed by variable loc.

• That is, a[loc]should be greater than a[left].

• If that is the case then simply continue comparing until left becomes equal to loc. Because once left
= loc, then it means the pivot has been placed in its correct position.

• However, if at any point we have a[loc]<a[left] then, interchange the two values and jump to step 2
• Set loc = left.

© Oxford University Press 2014. All rights

 Quick Sort
Example: Consider the array given below and sort the elements using quick sort
algorithm.
27 10 36 18 25 45

We choose the first element as the pivot. Set loc = 0, left = 0,

right = 5 as,
27 10 36 18 25 45

Loc Right
Left

Scan from right to left. Since a[loc] < a[right], decrease the value of right.
27 10 36 18 25 45

Loc Right
Left

© Oxford University Press 2014. All rights

 Quick Sort

Since, a[loc] > a[right], interchange the two values and set loc = right.

25 10 36 18 27 45

Left Right, Loc

25 10 36 18 27 45

Left
Right, Loc

© Oxford University Press 2014. All rights

 Quick Sort
Start scanning from left to right. Since, a[loc] > a[right], increment
the value of left.
25 10 36 18 27 45

Left
Right, Loc

Now since, a[loc] < a[right], interchange the values and set loc = left
25 10 27 18 36 45

Left, Loc Right,

© Oxford University Press 2014. All rights

 Quick Sort
Scan from right to left. Since a[loc] < a[right], decrement the value of
right.
25 10 27 18 36 45

Left, Loc Right,

Since, a[loc] > a[right], interchange the two values and set loc =
right. 25 10 18 27 36 45

Left Right, Loc

Start scanning from left to right. Since, a[loc] > a[right], increment
the value of left. 25 10 18 27 36 45

Left, Right, Loc

© Oxford University Press 2014. All rights

 Quick Sort
PARTITION ( ARR, BEG, END, LOC)

Step 1: [Initialize] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG = 0
Step 2: Repeat Steps 3 to while FLAG = 0
Step 3: Repeat while ARR[LOC] <= ARR[RIGHT] AND LOC != RIGHT
SET RIGHT = RIGHT – 1
[END OF LOOP]
Step 4: IF LOC == RIGHT, then
SET FLAG = 1
ELSE IF ARR[LOC] > ARR[RIGHT], then
SWAP ARR[LOC] with ARR[RIGHT]
SET LOC = RIGHT
[END OF IF]
Step 5: IF FLAG = 0, then
Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFT
SET LEFT = LEFT + 1
[END OF LOOP]
Step 6: IF LOC == LEFT, then
SET FLAG = 1
ELSE IF ARR[LOC] < ARR[LEFT], then
SWAP ARR[LOC] with ARR[LEFT]
SET LOC = LEFT
[END OF IF]
[END OF IF]
Step 7: [END OF LOOP]
Step 8: END

© Oxford University Press 2014. All rights

 Quick Sort

QUICK_SORT ( ARR, BEG, END)

Step 1: IF (BEG < END), then

CALL PARTITION ( ARR, BEG, END, LOC)
CALL QUICKSORT(ARR, BEG, LOC – 1)
CALL QUICKSORT(ARR, LOC + 1, END)
[END OF IF]
Step 2: END

© Oxford University Press 2014. All rights

Complexity of Quick Sort Algorithm
• In the average case, the running time of the quick sort algorithm can be given
as, O(nlogn). The partitioning of the array which simply loops over the elements
of the array once, uses O(n) time.
• In the best case, every time we partition the array, we divide the list into two
nearly equal pieces. That is, recursive call processes a sub-array of half the size.
Since, at the most only logn nested calls can be made before we reach a sub-
array of size 1. This means that the depth of the call tree is O(logn). And
because at each level there can only be O(n), the resultant time is given as
O(nlogn) time.
• Practically, the efficiency of the quick sort algorithm very much depends on the
element is chosen as the pivot. The worst-case efficiency of the quick sort is
given as O(n2). The worst case occurs when the array is already sorted (either
in ascending or descending order) and the left-most element is chosen as the
pivot.
• However, many implementations randomly choose the pivot element. The
randomized version of the quick sort algorithm always has an algorithmic
complexity of O(n log n).
© Oxford University Press 2014. All rights
 Radix/Bucket Sort
• Radix sort is a linear sorting algorithm for integers that uses the
concept of sorting names in alphabetical order. When we have a
list of sorted names, the radix is 26 (or 26 buckets) because there
are 26 letters of the alphabet. Observe that words are first sorted
according to the first letter of the name. That is, 26 classes are
used to arrange the names, where the first class stores the names
that begins with ‘A’, the second class contains names with ‘B’, so
on and so forth.

• During the second pass, names are grouped according to the

second letter. After the second pass, the names are sorted on the
first two letters. This process is continued till nth pass, where n is
the length of the names with maximum letters.

© Oxford University Press 2014. All rights

 Radix/Bucket Sort
• After every pass, all the names are collected in order of buckets. That is,
first pick up the names in the first bucket that contains names beginning
with ‘A’. In the second pass collect the names from the second bucket, so
on and so forth.

• When radix sort is used on integers, sorting is done on each of the digits in
the number. The sorting procedure proceeds by sorting the least significant
to most significant digit. When sorting numbers, we will have ten buckets,
each for one digit (0, 1, 2…, 9) and the number of passes will depend on
the length of the number having maximum digits.

© Oxford University Press 2014. All rights

 Radix/Bucket Sort
Example: Sort the numbers given below using radix sort.

345,654, 924, 123, 567, 472, 555, 808, 911

In the first pass the numbers are sorted according to the digit at
ones place. The buckets are pictured upside down as shown below.

© Oxford University Press 2014. All rights

 Radix/Bucket Sort
Number 0 1 2 3 4 5 6 7 8 9

345 345

654 654

924 924

123 123

567 567

472 472

555 555

808 808

911 911

© Oxford University Press 2014. All rights

 Radix/Bucket Sort
Number 0 1 2 3 4 5 6 7 8 9

911 911

472 472

123 123

654 654

924 924

345 345

555 555

567 567

808 808

© Oxford University Press 2014. All rights

 Radix/Bucket Sort
Number 0 1 2 3 4 5 6 7 8 9

808 808

911 911

123 123

924 924

345 345

654 654

555 555

567 567

472 472

After this pass, the numbers are collected bucket by bucket. The new list thus formed is the final sorted result. After
the third pass, the list can be given as, 123, 345, 472, 555, 567, 654, 808, 911, 924.
© Oxford University Press 2014. All rights
 Radix/Bucket Sort

Algorithm for RadixSort ( ARR, N)

Step 1: Find the largest number in ARR as LARGE

Step 2: [Initialize] SET NOP = Number of digits in LARGE
Step 3: SET PASS = 0
Step 4: Repeat Step 5 while PASS <= NOP-1
Step 5: SET I = 0 AND Initialize buckets
Step 6: Repeat Step 7 to Step 9 while I<N-1
Step 7: SET DIGIT = digit at PASSth place in A[I]
Step 8: Add A[I} to the bucket numbered DIGIT
Step 9: INCEREMENT bucket count for bucket numbered
DIGIT
[END OF LOOP]
Step 10: Collect the numbers in the bucket
[END OF LOOP]
Step 11: END

© Oxford University Press 2014. All rights

Complexity of Radix Sort Algorithm
• To calculate the complexity of radix sort algorithm, assume that
there are n numbers that have to be sorted and the k is the
number of digits in the largest number. In this case, the radix
sort algorithm is called a total of k times. The inner loop is
executed for n times. Hence the entire Radix Sort algorithm
takes O(kn) time to execute. When radix sort is applied on a
data set of finite size (very small set of numbers, then the
algorithm runs in O(n) asymptotic time.

© Oxford University Press 2014. All rights

 Heap Sort
• Given an array ARR with n elements, the heap sort algorithm can be used to sort ARR in two phases:

• In phase 1, build a heap H using the elements of ARR

• In phase 2, repeatedly delete the root element of the heap formed in phase 1.

• In a max heap, that we have discussed so far, we know that the largest value in H is always present
at the root node. So in phase B, when the root element is deleted, we are actually collecting the
elements of ARR in decreasing order. Let us have a look at the algorithm of heap sort as below.

© Oxford University Press 2014. All rights

 Heap Sort

HEAPSORT(ARR, N)

Step 1: [Build Heap H]

Repeat for I = 0 to N-1
CALL Insert_Heap( ARR, N, ARR[I])
[END OF LOOP]
Step 2: [Repeatedly delete the root element)
Repeat while N>0
CALL Delete_Heap(ARR, N, VAL)
SET N = N + 1
[END OF LOOP]
Step 3: END

© Oxford University Press 2014. All rights

 Complexity of Heap Sort
• Heap sort algorithm uses two heap operations: insertion and root deletion. Each element
extracted from the root is placed in the last empty location of the array.

• In phase 1, when we build a heap, the number of comparisons to find the right location
of new element in H cannot exceed the depth of H. Since, H is a complete tree, its depth
cannot exceed m where m is the number of elements in the heap H.

• Thus, total number of comparisons g(n) to insert n elements of ARR in H is bounded as,
g(n) <= nlogn

• Hence, the running time of the first phase of the heap sort algorithm is given as O(nlogn).

© Oxford University Press 2014. All rights

 Complexity of Heap Sort
• In phase 2, we have H a complete tree with m elements having the left and right subtrees as
heaps. Assuming L to be the root of the tree, reheaping the tree would need 4 comparisons to
move L one step down the tree H. since, the depth of H cannot exceed O(log m), reheaping the
tree will require a maximum of 4 log m comparisons to find the right location of L in H.

• Since, n elements will be deleted from the heap H, reheaping will be done n times. Therefore,
h(n) of comparisons to delete n elements is bounded as,
h(n) <= 4n log n
• Hence, the running time of the second phase of the heap sort algorithm is given as O(nlogn).

• We see that, each phase requires time proportional to O( n log n). Therefore, running time to
sort an array of n elements using heap sort in the worst case is proportional to O(nlogn).

© Oxford University Press 2014. All rights