10
SORTING
10.1 INTRODUCTION
Sorting is a fundamental operation in computer science. A good deal of effort in computing is related to making data available to users in some particular order. The concept of an ordered set of data is one that has considerable impact on our daily lives. For example, lists of names are frequently printed in alphabetical order and mailing labels are often printed in pin-code order. Sorting refers to arranging data in some given order, such as increasing or decreasing, with numeric data or alphabetically, with character data.
In this chapter we are concerned with rearranging the data so that it is in sorted order. There are two important and largely disjoint categories related to sorting data—internal sorting and external sorting. Internal sorting takes place in the main memory of a computer, where we can use the random access capability of the main memory to take advantage in various ways. External sorting is necessary when the data to be sorted is too large to fit in the main memory.
Many different sorting algorithms have been invented, and we will describe some of the common sorting techniques and the advantages and disadvantages of one technique over the other.
10.2 SORTING TECHNIQUES
10.2.1 Insertion Sort
The sorting method that we shall consider first is called ‘insertion sort’. Insertion sort works the way we might put a hand of cards in order. The hand is scanned for the first card that is lower than the one to the left. When such a case is found, the smaller card is picked out and moved to or inserted at the correct location. Fig. 10.1 illustrates the proceess for five elements, each of which is an interger. The input data, an array of five integers, is shown in Fig. 10.1(a).
Fig. 10.1 Insertion sort. The integers that are known to be sorted at the beginning of each step are underlined
In the insertion sort, the first two numbers are compared. If the one on the right is larger than the one on the left, the second number is inserted in front of the number.
The first number slides over and takes the place of the second number. The process goes on by scanning to the right until a smaller number is found. It is inserted at the correct location, and the rest of the numbers slide one position to the right. This process is repeated until the end of the list is reached. The list is then sorted. The basic operation is thus the insertion of a single element into a sequence of sorted elements so that the resulting sequence is still sorted.
Consider the figure containing an array of five integers. When the fifth element, 235, is considered by itself, it is a sorted list of length one. The transition from Figs. 10.1(a)–10.1(b) consists of inserting 46 in the list of elements that is already sorted. Since 46 is less than 235, the insertion of 46 is at top of the list and the sorted segment of the list now has a length of two. Next, 162 is between 46 and 235, it is inserted between them by moving 46 up to make room. The sorted subset of the list has now grown to a length of three. This is shown in Fig. 10.1(c).
Fig. 10.1(d) is obtained by inserting 205 into the list of elements that is already sorted. This is accomplished by moving 46 and 162 up to make room. Finally, Fig. 10.1(e) is obtained by inserting 390 into the list of elements (of length four) that is already sorted.
Algorithm 10.1 implements insertion sort as we just described it.
Algorithm 10.1: Insertion sort
Input: An array A with n elements, A [1],…, A [n]
Output: Sort the array A into ascending order
Step 1: for k=n-1 to 1 by -1 do
Step 2: j =k+1
Step 3: s=A [k]
Step 4: A [n+1] = S
Step 5: while (S>A [j]) do
Step 6: A [j-1] = A [j]
Step 7: j = j+1
End
Step 8: A [j - j] = S
End
Step 9: Stop
The program for insertion sort is as follows.
Example 10.1
/* Program for insertion sort */
# define n 6
int x[]={42, 34, 56, 23, 78, 90};
main( )
{
int I, t, j,.
printf(“
Input data:
”);
for(I=0; I<n; I++)
printf(*%3d*, x[I]);
printf(*
*);
for I=1; I<n; I++)
for(j=1, j>0 && x[j]<x[j-1]; j — —)
{
t=x[j];
x[j]=x[j-1];
x[j-1]=t;
}
printf(“
Output data:
”);
for(I=0; I<6; I++)
printf(“%3d”, x[I]);
printf(“n”);
}
input data:
42 34 56 23 78 90
output data:
23 34 42 56 78 90
10.2.2 Selection Sort
The idea behind selection sort is the selection of the smallest (or largest) element from a sequence of elements. Suppose an array A contains five elements as follows:
390, 205,182, 45, 235
The selection-sort algorithm for sorting A works as follows.
First, find the smallest element in the list and put it in the first position. Then find the second smallest element in the list and put it in the second position and so on. We now illustrate the process in Fig. 10.2 for a sequence of five elements.
Fig. 10.2 Selection sort (smallest element after each step is underlined)
The smallest element, 45, is selected and exchanged with the first element, 390. This produces a sorted list of length one. Next, the smallest element among the second through the last element is selected and then exchanged with the second integer in the list. This produces a sorted list of length two. In the next step the transition is accomplished by selecting the smallest integer among the third through the last element in the array. This element is then exchanged with the third element in the sequence. The list is now of length three. Finally, the smallest integer is selected among the fourth and fifth elements and that element is exchanged with the fourth element. The entire list is now sorted.
The following algorithm implements the selection sort as we just described.
Algorithm: 10.2: Selection Sort
Input: An array A with n elements, A [1],…, A [n]
Output: Sort the array A into ascending order
Step 1: while (n>l) do
Step 2: for k=1 to n-1 do
Step 3: Small = k
Step 4: for j=k+1 to n do
Step 5: if (A[j] < A [small]) then do
Step 6: small = j
Step 7: X = A [k]
Step 8: A [k] = A [small]
Step 9: A[Small] = X
end
end
end
Step 10: stop
The program for selection sort is as follows.
Example 10.2
/* Program for selection sort */
# define n 6
int X[] = {6, 5, 4, 3, 2, 1};
main( )
{
int i, t, j, small;
printf(“
Input data:
”);
for(i=0; i<n; i++)
printf(“%3d”, X[i];
printf(“
”);
for(i=0; i<n; i++)
{
small=i;
for(j=i+1; <n; j++)
if(X[j] <X[small])
Small = j;
T= X [i];
X[i]=X[small];
X[small]= t;
}
printf(“
Output data:
”);
for(i=0; i<6; i++)
printf(“%3d”, X[i]);
printf(“
”);
}
Input data:
6 5 4 3 2 1
Output data:
1 2 3 4 5 6
10.2.3 Bubble Sort
The basic operation in an bubble sort is the exchange of an adjacent pair of key elements. The overall sorting process consists of a number of passes over the keys. Bubble sort is an exchange sort. The basic idea behind bubble sort is to imagine that the records to be sorted are kept in an array vertically. The records with low key values are’ light’ and bubble up to the top. We make repeated passes over the array, from bottom to top. As we move, if two adjacent elements are out of order, that is, if the lighter one is below, we reverse it. Consider Fig. 10.3 for viewing the process of bubble sort in ascending order.
Fig. 10.3 The first pass of bubble sort in ascending order
In Fig. 10.3, the first pass is made over the data given in Fig. 10.3(a). In Fig. 10.3(a) 390 is compared with 206. They are interchanged since 206 is smaller. The result is shown in Fig. 10.3 (b).
Next, 390 is compared with 162, and they are exchanged. This is shown in Fig. 10.3(c). The process is then repeated and finally the result is seen in Fig. 10.3(e).
The first pass moves the largest element to nth position, forming a sorted list of length one. The second pass moves the second largest element to the n–1th position. In general, after ith pass, the i largest elements will be in the last i positions, so pass i+1 need only consider i–1 elements. In the mean time the small elements are moving slowly, or bubbling, towards the top. So this sorting method is refered to as bubble sort.
If no exchange is made during one pass over the data, the data are sorted and the process teminates. The following algorithm shows how an exchange or bubble sort can be implemented.
Algorithm 10.3: Bubble sort
Input: An array A with n elements, A [1]…………A [n]
Output: Sort the array A into ascending order
Step 1: K = n
Step 2: While (K > 1) do
Step 3: for j = 1 to K–1
Step 4: if(A[j] > A[j+1]) then do
Step 5: p = A [j]
Step 6: A[j] = A[j + 1]
Step 7: A [j + 1] = p
end
Step 8: K= K–1
end
end
end
Step 9: stop
The program for bubble sort is given below.
Example 10.3
/* Bubble sort program */
# include<stdio.h>
# define n 10
int X[]={12,15,5,9,4,7,3,19,4,20,};
main ( )
{
int i, j, k, temp, min;
/* Unsorted list */
printf(“
Unsorted List
”);
for(i=0; i<n; i++)
printf(“% 4d”, X[i]);
printf(“
”);
for(i=0; i<n-1; i++)
{
min=i;
for(j =i + 1; j<n; j++)
if(X[j] <X[min])
min = j;
temp = X[i];
X[i] = X(min);
X[min] = temp;
printf(“
pass = %4d
”, i+1);
for(k = 0; k < n; K++)
printf(“%3d”, X[K];
printf(“
”);
}
/* Sorted list */
printf(“
Sorted List
”);
for(i=0; i<n; i++)
printf(“%3d”, X[i];
}
10.2.4 Complexity Analysis
Complexity of bubble sort Traditionally, the time complexity for a sorting algorithm is measured in terms of the number of comparisons. The f(n), number of comparisons, in the bubble sort can be easily computed. The bubble-sort program was implemented with two loops. One is inner loop and the sother is outer loop. The inner loop is executed the following number of times:
(n–1) + (n–2) +…+ (n–k) =1/2 (2n–k–1) (k)
where k indicates the number of executions of the outer loop before there is a pass during which there are no exchanges. The inner loop contains one comparison and sometimes an exchange. In other words, there are (n–1) comparisons during the first pass which places the largest element in the last position; there are (n–2) comparisons needed to place the second largest in the next-to-last position, and so on. We now consider two cases—best case and worst case—de-pending on the value of k.
The best case occurs when the value of k is 1. It indicates that no exchange is required since the original data were sorted. So the value of f(n) is
F(n) = n–1 = O(n) (order of n)
The worst case occurs when K is n -1. The inner loop is executed 1 / 2n (n -1) number of times. Thus
F(n) = (n-1) + (n-2) +…+ (n(n-1))
= (n–1) + (n–2) +…+ 1
= n(n–l)/2
= O(n2)
In other words, the time required to execute the bubble-sort algorithm is proportional to n2 where n is the number of input items.
The bubble-sort method has two serious drawbacks. First, its inner loop contains an ex-change that requires three moves. Second, when an element is moved, it is always moved to an adjacent position. So it is expensive in most cases.
Complexity Of insertion sort The number f(n) of comparisons in the insertion-sort algorithm can be easily calculated. The outer loop of the insertion-sort algorithm is always executed n–1 times, where n is the number of items to be sorted. In this case it is executed the following number of times
1+2 +…+n–l = n(n–l)/2
the f(n) is expressed as
f(n) = 1+2 +…+ (n–1)= n(n–l)/2 = O(n2)
Given all possible combinations of initial ordering of data, on the average, the inner loop is executed half as many times as in the worst case.
Accordingly, for the average case
f(n) = 1/2+ 2/2 +…+ (n–l)/2 = n(n–l)/4 = O(n2)
This is because the inner loop of insertion-sort algorithm is producing a sorted list looking for the element that is larger than the one being inserted. On the average, this requires probing half the list. Thus an insertion sort will give the best performance for small elements or for elements with sorted items that are time consuming to compare.
Complexity of selection sort The selection sort algorithm consists of two loops, outer loop and inner loop. In the algorithm, each of these is implemented using ‘for’ statement. There are n-1 comparisons to find the smallest element, there are n–2 comparisons during pass2 to find the second smallest element, and so on. Thus, f(n) is calculated as in worst case as
f(n) = (n–1) + (n–2)…+ 2+1 = n(n–l)/2 = O(n2)
The number of interchanges and assignments is independent of the data being sorted. The selection sort always requires 0(n2) comparisons no matter how the data are initially ordered, but it never requires more than 0 (n) moves. So selection sort will give the best performance for large elements with minimum sorted items. It requires fewer moves than an insertion sort, and comparing sort items is not the dominant activity.
The following table presents the comparative study between three algorithms discussed so far.
Table 10.1
| Method | Worst Case | Average Case |
| Bubble sort | n(n–1)/2=O(n2) | n(n–1)/2=O(n2) |
| Insertion sort | n(n–1)/2=O(n2) | n(n–1)/4=O(n2) |
| Selection sort | n(n–1)=0(n2) | n(n–1)2=0(n2) |
10.2.5 Shell Sort
In any sorting algorithm if we move items only one position at a time, its average running time will be, at best, proportional to N2, where N is the number of records. If we want to make substantial improvements over straight insertion, a new technique is required to move records over a wide range instead of short steps. This method was proposed in 1959 by Donald L Shell. It is called Shell sort or diminishing increment sort. The method is based on divide-and-conquer technique invented by Donald Shell.
Consider an array of integers to be sorted using the shell sort. This method divides the original list into sublists by taking every kth element beginning with the first one. The value of k miss called an increment. Suppose we had a 12-item list
4 7 2 9 10 5 7 3 9 5 10 3
which was broken into three sublists using an increment of 4.
List1 4 9 7 5
List2 7 10 3 10
List3 2 5 9 3
Each sublist is then sorted and a smaller increment is selected.
List1 4 5 7 9
List2 3 7 10 10
List3 2 3 5 9
The entire list after one increment has been used.
4 3 2 5 7 3 7 10 5 9 10 9
Next, a new increment of 2 (i.e. k=2) produces two new sublists
List1 4 2 7 7 5 10
List2 3 5 3 10 9 9
These two lists are sorted individually
List1 2 4 5 7 7 10
List2 3 3 5 9 9 10
The list is now given below
2 3 4 3 5 5 7 9 7 9 10 10
Finally, one increment is selected to get the sorted sequence,
2 3 3 4 5 5 7 7 9 9 10 10
Each of the intermediate sorting process involves either a comparatively shorter list or a list which is comparatively well ordered. So insertion sort can be applied to each sorting operation; the list tends to converge quickly to its final destination.
The sequence of increments 4,2,1 is not mandatory; any other sequence can be used so long as the last increment equals 1. For example, the above list can be sorted with increments 5,3, and 1 instead of 4, 2, and 1. It is described as follows:
The original item list is given below:
4 7 2 9 10 5 7 3 9 5 10 3
k=5
List1 4 10 9
List2 7 5 5
List3 2 7 10
List4 9 3 3
Each Sublist is sorted as follows:
List1 4 9 10
List2 5 5 7
List3 2 7 10
List4 3 3 9
The entire list after one increment is shown below:
4 5 2 3 9 5 7 3 10 7 10 9
A new increment, that is, 3 is now selected.
List1 4 2 9 7 10 10
List2 5 3 5 3 7 9
These two lists are sorted individually.
List1 2 4 7 9 10 10
List2 3 3 5 5 7 9
The new list is obtained as follows:
2 3 4 3 7 5 9 5 10 7 10 9
Finally, 1 is selected as increment to get the following sorted list:
2 3 3 4 5 5 7 7 9 9 10 10
The algorithm for shell sort is given below.
Algorithm 10.4: Shell sort
Input: An unsorted array A of size N, A [1],…, A [N]
Output: Sort the array in ascending order
Step 1: I=N/2
Step 2: while (I > 0) do
Step 3: J= I
Step 4: while (J < N) do
Step 5: J= J+1
Step 6: K= J+ 1
Step 7: while (K > 0) do
Step 8: if (A [K] > A [K+I]) then do
Step 9: S= A[K]
Step 10: A[K] = A[K+I]
Step 11: A [K+I] = S
Step 12: K= K-I
else
Step 13: K = 0
end
end
end
Step 14:I = I/2
end
Step 15: Stop
Example 10.4
/* Shell sort program */
# include <stdio.h>
# define n 13
int X[n]={9, 12,45,7,53,12,78,90,10,65,3,19,47};
main( )
{
int i, J, K, TEMP , GAP;
printf(“
Unsorted Data
”);
for(i=0; i<n;i++)
printf(“%4d”, X[I]);
printf(“
”);
gap=1;
do {
gap=3*gap+1;
} while(gap<=n);
gap = gap/3;
for(;gap>0; gap=gap/2)
{
printf(“
Span Size = %4d
”, gap);
for(i=gap; i<n; i++)
for(j = i-1; j>0; j=j - gap)
if(j+gap < n &&(x[j]>x(X[J] + gap]))
{
temp = x[j];
x[j] = x[j+gap];
x[j+gap]=temp;
}
for(K=0; K<n; K++)
printf(“% 4d”, X[K];
}
printf (“
Sorted data
”);
for(i=0; i<n; i++)
printf(“%4d”, X[i]);
}
Unsorted Data
9 12 45 7 53 12 78 90 10 65 3 19 47
Span Size= 13
9 12 45 7 53 12 78 90 10 65 3 19 47
Span size = 6
9 12 45 7 53 12 47 90 45 65 53 19 78
Span Size=3
7 3 10 9 12 12 47 53 19 65 90 45 78
Span Size= 1
3 7 9 10 12 12 19 45 47 53 65 78 90
Sorted Data
3 7 9 10 12 12 19 45 47 53 65 78 90
Complexity of Shell sort The main reason why straight insertion is relatively slow is that the items are inserted sequentially. Thus the average running time is O(n2.) Shell proposed an efficient variant in which the insertion process is done in several passes of successive refinements.
For a given input size n, the passes are determined by an ‘increment sequence’ ht, h (t-1)…h1, where h = 1. In the early passes (when the increment are typically large), elements can be displaced far from their previous position with only a few comparisons. The later passes “fine tune” the placements of elements. The last pass, when h1=1, consists of a single straight insertion sort of of entire array. The resulting expected running time is 0 (n5/3). The average running time will be at least proportional to n2.
The shell sort is also called the diminishing increment sort because the increment sequence continually decreases. The method is most efficient if the successive values of h are kept relatively prime to each other. Kunth has mathematically estimated that, with relatively prime values of h, the shell sort will execute in an average time proportional to 0(n(Log 2 N)2).
10.2.6 Quick Sort
The next sort we consider is the partition-exchange sort or quick sort. The method consists of a series of steps, each of which takes a list of elements to be sorted as input. The output from each step is a rearrangement of the elements so that one element is in its sorted position and two sublists remain to be sorted. If the elements to be sorted are
X [1], X [2],…, X [n]
then quick sort could rearrange the elements to produce the following order shown in Fig. 10.4.
Fig. 10.4 (a) Each of these elements is smaller than X [j]. (b) Element in its sorted position. (c) Each of these elements is larger than X [j]
Each step of quick sort positions a given list into three disjoint sublists. One of these sublists is a single element that is in its sorted position. The sublist in the left of the sorted element contains elements that are less than the sorted element whereas the sublist in the right of the sorted element has elements that are higher than the sorted element. This sorting problem is said to have been partitioned into further sublists and so on.
Let us illustrate the quick sort with an example. If the initial array is given as
26 57 48 37 12 92 86 33
and suppose we want to place the first element 26 in its proper position, the resulting array is
12 26 57 48 37 92 86 33
Note that the element 12 is less than or equal to 25 and each element above 26 is higher than or equal to 26.
Since 26 is in its final position the original array has been decomposed into the problem of sorting two subarrays
(12) and (57, 48, 37, 92, 86, 33)
The entire array is viewed as
12 26 (57, 48, 37, 92, 86, 33)
where parentheses enclose the subarrays that are yet to be sorted. Repeating the process on the subarray on the right of 26 yields
12 26 (48, 37, 33) 57 (92, 86)
and further repetitions yield
12 26 (37, 33) 48 57 (92,86)
12 26 (33) 37 48 57 (92, 86)
12 26 33 37 48 57 (92, 86)
12 26 33 37 48 57 (86) 92
12 26 33 37 48 57 86 92
Note that the final array is now sorted. The algorithm for quick sort is presented below.
Algorithm 10.5: Quick sort
Input: An array A of size n containing n distinct numbers, A [1]…A[n].
Output: Rearranging the elements in array A into ascending order.
Step 1: Right = n
Step 2: for left = 1 to n do
Step 3: Call function qs (A, left, right)
end
Step 4: Stop
Function: qs (A, Left, right)
Step 1: if (left < right) then do
Step 2: j=left
Step 3: K= right + 1
Step 4: while (j <= K) do
Step 5: while (A [j] < A [left]) do
Step 6: j= j + 1
end
Step 7: while (A[K]>A[left] do
Step 8: K= K–1
end
Step 9: if(j < k) then do
Step 10: s=A [j]
Step 11: A [j] = A[K]
Step 12: A [K] = s
end
end
Step 13: s=A [left]
Step 14: A [left] = A[K]
Step 15: A [K] = s
Step 16: qs (A, left, K–l) / * Recursive call * /
Step 17: qs (A, K+1, right) / * Recursive call * /
Step 18: Return
The program for quick sort is given below.
Example 10.5
int X[]={5,2,4,7,1,4,3,8,9,4,6,7,10,12,2,15};
/* Quick sort program */
main( )
{
int 1, r, i, j;
1 = 0;
r=15;
printf(“
Unsorted data
”);
for(i=0; i<16; i++)
printf(“% 3d”, X[i]);
printf(“
”);
for(i=0; i<16; i++)
quick(X, 1, r);
printf(“
Sorted data
”);
for(i=0; i<16; i++)
printf(“%3d”, X[i]
printf(“
”);
}
quick(x, 1, r)
int x[], 1, r;
{
int i, j, pivot, t, k;
if(r>1)
{
pivot = X[1];
i = 1 +1;
j=r;
do
{
while(X[i]< = pivot && i<r); i++;
while(X[j]> pivot && j>1); j--;
if(i<j)
{
t=X[i];
X [i] = X [j];
X [j] = t;
}
printf(“
pivot = % d
”, X[i]);
for(k=0; k<16; k++)
printf(“% 3d”, X[k];
} while(i<j);
t=X [ i ]
X [ i ] = X [ j ] ;
X [ j ] = t ;
}
if(j>i+1) quick(X, 1, j-1);
if(j>r-1 quick(X, j+1, r);
return;
}
Unsorted Data
5 2 4 7 1 4 3 8 9 4 6 7 10 12 2 15
pivot=5
5 2 4 2 1 4 3 8 9 4 6 7 10 12 7 15
pivot=5
5 2 4 2 1 4 3 4 9 8 6 7 10 12 7 15
pivot=5
5 2 4 2 1 4 3 4 9 8 6 7 10 12 7 15
pivot=4
4 2 4 2 1 4 3 5 9 8 6 7 10 22 7 15
pivot=3
3 2 1 2 4 4 4 5 9 8 6 7 10 12 7 15
pivot=2
2 2 1 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=1
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=2
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=2
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=3
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=4
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=4
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=4
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=4
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=5
1 2 2 3 4 4 4 5 9 8 6 7 10 12 7 15
pivot=9
1 2 2 3 4 4 4 5 9 8 6 7 7 12 10 15
pivot=9
1 2 2 3 4 4 4 5 9 8 6 7 7 12 10 15
pivot=7
1 2 2 3 4 4 4 5 7 7 6 8 9 12 10 15
pivot=7
1 2 2 3 4 4 4 5 7 7 6 8 9 12 10 15
pivot=6
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=6
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=7
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=7
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=8
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=9
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=12
1 2 2 3 4 4 4 5 6 7 7 8 9 12 10 15
pivot=12
1 2 2 3 4 4 4 5 6 7 7 8 9 10 12 15
Sorted Data
1 2 2 3 4 4 4 5 6 7 7 8 9 10 12 15
Complexity of quick sort Both the expected and the minimum number comparisons required by quick sort are O(n log2n). The worst-case behaviour of this algorithm is of the order O(n2). However, if we are lucky enough then each time an item is correctly positioned, the sublist to its left will be of the same size as that to its right. This would make the sorting of the sublists each of size n/2. The time required to position an item in a list of size n is O(n).
Quick sort is an extremely good general-purpose routine. A big drawback of the method is its worst-case performance. It requires O(n2) time to sort a list that is already sorted or nearly sorted. A good way to guard against guaranteed bad behaviour is to choose the partioning elements to be random element in the current sublist (say, the first, middle, and the last elements). This also has the effect of reducing the average number of comparisons.
If the smaller of the two sublists is always processed first after each partition, then the required stack contains at the most log n entries. We can simulate the stack with only a constant amount of space at a slight increase in computing time.
10.2.7 Merge Sort
One of the most common external sorts is the merge sort. When the data to be sorted do not fit in memory, then an external sort is employed. External sort methods bring only portion of the data into the computer's memory during comparison and swap operations.
Merging is the process of combining two or more sorted sublists into a third sorted list. For example, merge sort accepts two sorted sublists x and y of n1 and n2 elements, respectively, and merges them into a third list z containing n3 elements. In other words, merge sort begins by comparing pairs of elements one from each sublist. The smallest element is appended to a sorted list and is replaced by the next element from its sublist. This process continues until there are no more elements in one of the sublists. The remaining elements in the other sublist are then appended to the sorted list, and the sort is complete. For example, we can merge the two sublists (503, 703, 765) and (087,512,677) to obtain (087,503,512, 677, 703, 765). A straightforward way to perform this is to compare the two smallest items, and output the smallest. This process continues until only one sorted list remains. The method is illustrated in Fig. 10.5.
Fig. 10.5 Successive passes for merge sort
Note that some care is necessary when one of the two sublists becomes exhausted.
Algorithm 10.6: Merge sort (Recursive version)
Input: Merge sort requires two arrays r and t. r-array holds data to be sorted and array t is used for merging operation.
Output: Array r holds the sorted list in ascending order.
/* Recursive function */ Merge sort(n) /* Array r of size n */ begin L = 1 If (n > = 3) then repeat Merge (L, n, r, t) L = 2 * L Merge(L, n, t, r) L = 2 * L until L > = (n div 2) if(L < n) then begin Merge(L, n, r, t,) for K = 1 to n do r [K] = t [K] end end /* Merge function */ Merge(L, n, r, t) begin k1 = 1 k2 = L+1 q=1 repeat end1= k1+1 if(end1> = n) then end1= n+1 else begin end2=k2+1 if(end3>n) then end2= n + 1 repeat if(r [K1]< =r[K2] then begin t[q] = r[K1] q= q + 1 k1 = k1+1 end else begin t[q] = r [k2] q=q + 1 k2= k2+1 end until (k1=end1)or(k2=end2) end if(k1 < end1) then repeat t[q] = r[k1] q= q+1 k1= k1+1 until k1 = end1 else repeat t[q] = r[k2] q= q + 1 k2= k2 + 1 until k2= end2 k1 = k2 k2 = k2+1 until (k1 > = n) end
The non-recursive merge-sort program and recursive merge-sort program are given as follows.
Sorting a list of elements by the method of merge sort
Example 10.6
# include< stdio.h >
void merging( );
void main( )
{
int n1, n2, n, z, a[10], b[10], c[10], i;
clrscr( );
printf (“Enter number of elements in the first sorted array: ===>”)
scanf(“% d”, &n1);
printf(“/n Enter the elements of the first sorted array:
”);
for(i = 0; i < n1; i++)
{
scanf(“% d”, &z) ’
a[i] = Z;
}
printf (“/n Enter number of the elements in the second sorted
array:=>”):
scanf(“%d”, &n2);
printf(“
Enter the elements of the second sorted array:
”):
for( i =0 ; i<n2 ; i++ )
{ scanf(“%d”, &z);
b [ i ] = z ;
}
clrscr( );
printf(“
The elements of the first sorted array:
”);
for( i = 0 ; i< n1 ; i++ ) printf (“%d”, a [ i ] ;
printf (“
The elements of the second sorted array :
”);
for( i = 0 ; i < n2 ; i++ ) printf (“%d”, b [ i ] ;
n= n1 + n2 ;
merging( a , b , c , n1, n2, n ) ;
}
void merging(int x[], int y[], int z[], int m1, int m2, int m3)
{
static int xlower = 0, ylower=0, zlower= 0 ;
int xupper = m1, yupper= m2, zupper = m3, 1;
if(x [xlower] < y [ylower])
{
z[ zlower ] = x[xlower] ;
x lower++ ;
}
else
{
z[zlower ] = y[ ylower ] ;
ylower++ ;
}
zlower++ ;
if ( ( xlower < xupper ) && (ylower < yupper ))
merging( x, y, z, m1, m2, m3 ) ;
else
{
while (xlower < xupper) Z[zlower++] = x[xlower++ ] :
while(Ylower <yupper) Z[zlower++] = y[ylower ++] :
printf(“
”);
printf(“Elements of the sorted list after combining”);
printf(“First and second array
”);
for(1=0; 1 < zupper ; 1++ )
printf(“% d”, z[ 1 ];
}
}
Enter number of elements in the first sorted array: = = = > 6
Enter the elements of the first sorted array:
12 16 22 34 45 50
Enter number of elements in the second sorted array: = = = > 5
Enter the elements of the second sorted array:
34 39 42 51 59
The elements of the first sorted array:
12 16 22 34 45 50
The elements of the second sorted array:
34 39 42 51 59
Elements of the sorted list after combining first and second array:
12 16 22 34 34 39 42 45 50 51 59
Example 10.7
/*******************************************************/
/ * MERGING OF TWO SORTED FILES (Using recursion)*/
/*******************************************************/
# include < stdio.h >
# include < conio .h >
# include < stdlib .h >
main( )
{
void merge(int x[], int y[], int x1, int x2, int c1, int c2, int i);
int i, n1, n2;
int at[100], b[100];
clrscr( );
printf(“Enter the total number of elements in list array
”);
scanf(“%d”, &n1 ) ;
printf(“
Enter the element of list file in ascending order
”);
for(i=0; i<n1; i++);
{
printf(“a [% d] = ” , i + 1 ) ;
scanf(“%d”, &a [ i ] ;
}
printf(“
”);
printf(“Enter the total number of elements in 2nd array
”);
scanf( “ %d ” , &n2 ) ;
printf(“
Enter the elements of 2nd file in ascending order
”);
for( i = 0 ; i < n2 ; i++)
{
printf(“b [ % d ] = ” , i + 1);
scanf(“% d ”, & b [i] ;
}
printf(“
The list in ascending order
”);
printf (“<———————————————————————————>
”);
merge( a, b, n1, n2, 0, 0, 0 );
getch( );
}
void merge(int x[], int y[], int x1, int x2, int c2, int i)
{
if ( C1 + C2 = = x1 + x2 )
return;
else
{
if ( x[c1] < y[c2] && c1 < x1 ) ( ( (c2 == x2) )
{
printf(“c [ % d ] = % d n”, i + 1, x[ c1 ] ;
merge( x, y, x1, x2, c1, c2, i + 1 ) ;
}
else
{
if ( ( ( x [c1] > y [c2] && c2 < x2 ) (
( c1 = = x1 ) )
{
printf(“c [ % d ] > y [ % d n ” , i +
1 , y [ c2 ] ;
merge( x, y, x1, x2, c1 , c2+ 1 , i + 1,
Y [ c2 ]) ;
}
}
}
}
Enter the total number of elements in list array
5
Enter the elements of list file in ascending order
a[1] =2
a[2] =4
a[3] =8
a[4] =11
a[5] =12
Enter the total number of elements in 2nd array
3
Enter the elements of 2nd file in ascending order
b[1] =1
b[2] =3
b[3] = 6
The list in ascending order
<——————————————————————————>
c [1] = 1
c [2] = 2
c [3] = 3
c [4] = 4
c [5] = 6
c [6] = 8
c [7] = 11
c [8] = 12
Complexity of merge sort The algorithm merge sort makes a pass over the entire array each time it is called. This occurs approximately log2n times in sorting a list of length n. The procedure merge moves all n of the elements during each pass. So it requires n log2n moves, no matter how the data are initially ordered. It will perform better for a linked list than for an array. The number of comparisons during a pass depends on the order of the data. If the sublists of length one are being merged, then there will be n/2 comparisons. If sublists of length greater than n/2 are being merged, then as many as (n–1) comparisons may be required. The merge sort requires approximately n log2n moves and some where between (n/2) log2n and n log2n comparisons. It has a very consistent performance since the effort required to use it does not affect much the initial order of the data. It has a drawback to implement it using arrays, because it requires twice as much memory as any of the other algorithms.
10.2.8 Heap Sort
The heap-sort algorithm was invented by J W J Williams in the year 1964. Like merge sort, but unlike insertion sort, heap sorts, running time is O(n log2n). Heap sort sorts in place—only a constant number of array elements are sorted outside the input array at any time. The heap data structure is an array object that can be viewed as a complete binary tree. Fig. 10.6(a) and 10.6(b) show a heap as a binary tree and an array.
Fig. 10.6 A heap view as a binary tree (a) and an array (b)
In the above figure the number within the circle at each node in the tree is the value stored at that node. The number prefix to a node is the corresponding index in the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.
A heap is a binary tree which must satisfy the following two conditions:
(a) The data value that is sorted in any node is less than or equal to the value in any of that node's children. The value stored in the root of a heap is always the smallest value in the loop. This condition is called the ordering property of heaps.
(b) A heap must be a complete binary tree. This property is known as the structuring property of heaps.
Suppose that A [1], A [2],…, A[n] is a sequence of elements. This sequence is a heap if it satisfies the following two conditions
A[i] < A[2i]…(i)
A[i] < A[2i+1]…(ii)
for all applicable values of i.
The two conditions will be referred to as the heap conditions. Fig. 10.7 shows three arrangements of a sequence of elements from a heap. Each element is an integer and each sequence contains a set of integers.
Fig. 10.7 Three distinct heaps from same set of integers
The data sets of array A in Fig. 10.7(a) are sorted and then form a heap. So the sorted data always forms a heap as shown in Fig. 10.7(b) and Fig. 10.7(c). Many other arrangements of the same data also form a heap. Fig. 10.8 shows binary trees constructed from the heaps.
The heap-sort proceeds in two phases. First, put the data into the heap and, second, data are extracted from the heap in sorted order. A heap sort is similar to the selection sort because both algorithms select and then swap into sorted order successively larger elements. A heap sort uses a more efficient data structure than selection sort but a selection sort will be faster than heap sort in case of a smaller set of elements.
Initially in a heap-sort structure the smallest element is on top. Thus, if the elements forming the heap are sorted on the array elements A [1], A [2],…, A[n], then the elements with smallest key will be stored as A [1]. Thus it is required to find element with the second smallest key.
Fig. 10.8 Binary trees constructed from the heaps
So we will proceed in the following way.
The first pass exchanges A [1] and A [n] and then sifts down A [1] in the sequence A [1],…, A [n – 1] so that A [1],…, A[n – 1] forms a heap. The result is that A [n] is a sorted list of length one and the second smallest element is A [1], The second step exchanges A [1] with A [n – 1] and then sifts down A [1] in the sequence A [1],…, A [n – 2], creating a heap with n – 2 elements. Now, A [n – 1] and A [n] from a sorted list of length two, and A [1] is the third smallest element. The ith step exchanges A [1] with A [n – (i – 1)] and sifts A [1] in the sequence A [1],…, A[n – 1] creating a heap with n – i elements. The sequence A [n – (i – 1)],…, A [n] is sorted, and A[1] is the ith smallest. We now present the heap-sort algorithm.
Algorithm 10.7: Heap-sort
Input: An input array A consisting n elements.
Output: The resulting sorted array A.
Step 1: j= [n/2] + 1/1 * [.] integer part*/
Step 2: while (j > 1) do
Step 3: j = j – 1
Step 4: call function siftdown (j, n)
end
Step 5: K= n
Step 6: while (K > 1) do
Step 7: T = A [1]
Step 8: A [1] = A [K]
Step 9: A [K] = T
Step 10: call function siftdown (1, K)
End
Step 11: stop
Function: siftdown (X, Y)
Step 1: i = X
Step 2: J= 2 * i
Step 3: P = A [i]
Step 4: while (J < = Y) do
Step 5: if (J < y) and if (A [J] < { A [j + 1) then do
Step 6: J = J + 1
end
Step 7: if (P > = A [j] then do step 11
end
Step 8: A [i] = A [J]
Step 9: i = J
Step 10: J = 2 * i
end
Step 11: A [i] = P
end
We now present the C source code for the heap-sort algorithm.
Example 10.8
# include <stdio.h>
# define SIZE 100
int A[SIZE];
main ( )
{
int no, i;
int 1, r, X;
printf(“
Enter number of elements:”);
scanf( % d”, &no);
printf(“
Enter the elements to be sorted:”);
for( i = 0 ; i < no; i++ )
scanf( “ % d “ ,&A[i] );
printf(“
The elements in the array A before sorted
”);
for( i = 0 ; i < n; i++)
printf(“ % d ” , A[i] );
printf( “
” );
1 = ( no/2 )+ 1;
r = no;
while( 1 > 1 )
{
(1--;
siftdown(1, r);
}
while ( r > 1 )
{
X=A[1];
A[1]=A[r];
A[1]=X;
r--;
siftdown( 1, r );
}
printf (“
The sorted list is as follows :
”);
for( i = 0; i <=n ; i++ )
printf(“% d ”( A [ i ];
printf(“
”);
}
/* Function siftdown */
siftdown ( 1, r )
int 1, r;
{
int i, j , X ;
i = 1 ;
J=2 *i ;
X = A [ i ] ;
while ( j < = r )
{
if( A [ j ] < A [ j + 1 ] )
j ++ ;
if( X > = A[ j ] break ;
A[ i ] = A[ j ] ;
i = j;
j = i * 2;
}
A [ i ] = X ;
return ;
}
Complexity of heap sort In any sorting method we have a sequence of n integer values, that is, A1, A2,…, An, and it is required to sort them either in ascending or descending order. Heap sort proceeds in two phases— create heap phase and maintaining heap property phase. The heap-sort procedure takes time O (n log2 n) since the call to CREATEHEAP takes time 0 (n) and each of the n-1 calls to maintain the heap property. The overall time complexity of heap-sort is therefore O (n log2 n) in both the average case and the worst case.
10.3 SORTING ON MULTIPLE KEYS
There is practically no data processing activity that does not require the data to be in some order. Computer sorting techniques are important in many applications. So far we have discussed various sorting methods such as insertion sort, bubble sort, quick sort, shell sort, heap sort, and merge sort. Sorting algorithms are broadly classified into two categories—internal sorting and external sorting. When the data to be sorted does not fit in memory, then an external sort is employed. One of the most common external sorting method is the Merge sort. The idea behind merge sort can also be used in case of merging two files.
Sorting is also done upon some key data items. The use of key complicates the sorting process. Sorting is done either in the ascending order or descending order of the key. So far we have assumed that the key field is an integer. It is not always true. For example, consider the case of a payroll problem where the necessary informations are employee number, employee name, employee address, department number, basic pay, allowances, deductions, and so on. If the sorting in ascending order is done on employee name, then the employee whose name is greater than (in collating sequence) that of another employee will appear later in the sorted list. It is also possible to sort on multiple keys. If we want to sort the said informations according to department number and within each department according to the employee number, then two keys are involved, that is, department number and employee number. The first one is called primary key and the second is called secondary key. In this case the department number is the primary key and the employee number is the secondary key. Suppose we want to sort first department number in ascending sequence and then within each department number in the descending sequence of basic pay, that is, all employee informations having the same value for department number are to be arranged from the highest to the lowest values of basic pay.
So far, we have illustrated a wide range of sort routines. All of them sort array of integer in ascending order. However, programmers are frequently faced with the need to sort strings. If the strings are themselves elements of an array, we can proceed in a manner similar to the sort routines described in this chapter. The difference is in how we make the comparison between array elements and in how array elements are interchanged.
In C language, comparing string is done with the help of library function strcmp. This function compares two strings element by element until a difference is found. If the two strings are the same, it returns 0, else it returns a positive number or a negative number depending on whether the first string is lexicographically greater than the second string or less than the second string. While comparing strings is done, it is needed to copy the strings. The following program illustrates how the quick-sort program can be modified to sort strings.
Example 10.9
# include < stdio.h>
/* Sorting an array of strings */
# define n 10
main( )
{
Char *Names[N]
Int i, left, right;
Left= 0; right = N - 1 ;
/* Read an array of names */
for(i = 0; i < N ; i ++)
scanf(“ %s
” , *Names[i];
printf( “
Unsorted names are given below :
”);
for(i = 0 ; i<n ; i + + )
printf( “ % s ” , Names[I];.
/* Call quick sort routines */
Quick_sort (Names, left, right );
/* Printing of sorted names */
printf( ‘ /n/n Sorted names are given below
” ) ;
for( i = 0 ; i<n ; i++)
printf(“
% s ” , Names[i] ;
return 0;
}
/* Quick sort function */
Quick_sort ( x, left, right )
Char *x[] ;
Int left, right ;
{
int i, j ;
char pivot[ 10 ] , t[ 10 ] ;
if ( right > left )
{
strcpy( pivot, x{left] ) ;
i = left + 1 ;
j = right ;
do {
while(strcemp (x [ i ] , pivot )<=0)&& i < right )
i + +;
while(strcmp (x [ j ] , pivot ) >=0 &&j> left)
j-- ;
if(i < j )
{
strcpy( t, x [ i ] ) ;
strcpy( x [ i ], x [ j ] ;
strcpy(x [ j ] , t ) ;
}
} while( i < j );
strcpy( t, x [ left ] );
strcpy( x [ left ], x [ j ];
strcpy( x [ J ] , t );
}
if (j>left + 1) Quick_sort ( x, left, J - 1) ;
if (j>right-1) Quick_sort ( x, j + 1 , right);
return;
}
We now present two more programs for sorting employee records. The first program sorts the employee records on employee names. The second program sorts the names as primary key and employee identification as the secondary key.
Example 10.10
# include<stdio.h>
# include<conio.h>
# include<string.h>
void main( )
{
struct employee
{
int id;
char *name ;
float salary ;
};
struct employee e[100] , arr;
int i , k, j , len;
float n ;
char * rname;
clrscr( );
printf( “
Enter the number of employees ; ” );
scanf( “ % f ” , & n : i++ );
{
printf( “
Enter the id number, name, salary: ” );
scanf(“%d %s %f”, &e[i]. id, rname, &e[i];salary );
len= strlen( rname );
len= len * sizeof( rname );
e[ i ]. name = (char * ) malloc ( len );
strcpy( e [ i ] . name, rname ):
}
/* Starts the sorting process */
for ( i = 1 ; i <= n; i++)
{
for( j= 1; j<=( n-1 ); j+ + )
{
k = Strcmp( e [ j ].name, e [ j + 1 ].name ) ;
If ( k > 0 )
{
arr = e[ j + 1 ] ;
e[ j + 1] = e[j];
e [ j ]= arr ;
}
/* If the two strings are equal ! ! */
if ( k == 0 )
{
if( e[ j ] . i d > e[ j + 1 ].i d )
{
arr= e[ j + 1] ;
e [ j + 1 ] = e [ j ] ;
e[ j ] = arr ;
}
}
}
}
/* Prints the sorted output */
printf( “
SORTED OUTPUT : - ” ) :
printf( “
nID NO : NAME SALARY ” ) ;
printf( “
” ) ;
for( i = 1 ; i < = n ; i++)
printf(“
%d %sRs. %2f”, e[i].id, e[i].name, e[i].salary);
}
Enter the number of employees : 6
Enter the id number, name, salary: 1 parama 3456. 99
Enter the id number, name, salary: 2 parama 8976. 78
Enter the id number, name, salary: 3 depali 5676. 77
Enter the id number, name, salary: 4 mahuya 2341. 98
Enter the id number, name, salary: 5 depali 5678. 98
Enter the id number, name, salary: 6 parama 7896. 65
Sorted Output:
| ID NO | NAME | SALARY |
| 3 | depali | Rs. 5676. 77 |
| 5 | depali | Rs. 5678. 98 |
| 4 | mahuya | Rs. 2341. 98 |
| 1 | parama | Rs. 3456. 99 |
| 2 | parama | Rs. 8976. 78 |
| 6 | parama | Rs. 7896. 65 |
Example 10.11
/* A PROGRAM TO SORT A EMPLOYEE RECORD ON EMPLOYEE NAMES*/
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
main( )
{
Struct employee {
int eno;
char ename[30];
float salary;
int egrade;
};
struct employee E[40];
int i, n, no, j, c, gr, grl;
float sal, sall;
char ch, str[30];
clrscr( );
printf( “
Enter how many employees ” );
scanf(“
%d”, &n );
for ( i=0;i<n, i++ )
{
printf (“
Enter emp-no. ” );
scanf( “
%d”, &no);
E[i].eno= no;
printf (“
Enter emp-name” );
scanf(“
% s”, & E [i].ename);
printf(“
Enter employee salary”);
scanf(“
% f ” , &sal);
E[ i ].esalary = sal;
printf ( “
Enter the grade ” );
scanf( “
% d”, &gr );
E [i].egrade = gr ;
}
for( i=0;i<n-1; i++ )
{
for( j = 0; j<n-1; j++ )
{
k= strcmp(E[j].ename, E[j +1 ].ename);
if (k>0) {/* The swap function resides here */
/* l.Swap for name */
c=0;
ch= E[j].ename[c];
while(ch ! = ‘ ’)
{
str[c]= ch ;
c++ ;
ch=E[j].ename[c];
}
str[c]=‘ ’;
c=0;
ch=E[j + 1].iname[c];
while (ch! = ‘ ’ )
{
E [ j].ename[ c ];
c++;
ch = E[j + 1].ename[c];
}
E[j].ename[c] = ‘ ’;
c=0;
ch=str[c];
While ( ch ! = ‘ ’)
{
E[j +1].ename[c]=ch;
c++;
ch= str[c];
}
E[j + 1]. ename [c] = ‘ ’;
/* Swap for employee no */
no=E[j].eno;
E[j].eno=E [j + 1].eno;
E[j + 1].eno= no;
/* Swap for employee salary */
sall = E[j].esalary;
E[j].salary = E [j + 1].esalary;
E[j+1].esalary = sall;
/* Swap for employee grade */
grl=E [j].egrade;
E [j].egrade=E[j +1].egrade;
E [j + 1].egrade= grl;
}
}
}
printf( “
The sorted employee list is: ” );
for( i=0; i<n, i++)
{
printf(“
%d %s %f %d”, E[i].eno, E[i].ename,
E[i].esalary, E[i].egrade);
}
}
| The sorted employee list is: | ||
| 2110 A. Sharma | 5000.000000 | 2 |
| 3950 J. Dutta | 9700. 000000 | 1 |
| 5911 P. Roy | 3500.000000 | 3 |
| 1010 R. Kumar | 8500.000000 | 1 |
| 7171 T. Dey | 6000.000000 | 2 |
E
XERCISES
| 1. | Write a program to sort the following sequence of eight integers
57, 27,22,95, 79, 45, 96 using insertion sort. In each case, keep track of the number of exchanges and comparison required. |
| 2. | What starting conditions are necessary to produce the worst-case behavior of bubble sort? |
| 3. | Both insertion and bubble sort are particularly deficient with respect to its ability to move elements long distances. Shell sort attempts to move element through long distances. It is fairly simple matter to modify the insertion sort algorithm so that is becomes a shellsort algorithm. Write an algorithm to implement this. |
| 4. | Mean sort uses mean value of those elements being partitioned. Implement mean sort for an array containing the following integers:
482,231, 928, 204,105, 428, 379, 47 |
| 5. | A sorting algorithm is stable if it preserves the order of elements with equal keys. Which of these algorithms—quick sort, heap sort, or merge sort are stable? |
| 6. | The algorithm for heap sort places elements in ascending or descending order. What changes of a C-Program are needed so that the result will be in ascending order if it originally sorts in descending order or vice-versa? |
| 7. | A drawback to merge sort for arrays is its requirement for twice as much memory as any of the other algorithms. Merge sort moves all elements during each pass. So it requires nlog2n moves no matter how the data are initially ordered. It will therefore perform better with a linked list data structure than with an array. Implement merge sort algorithm using linked structure. |
| 8. | It is noted that (3/2) nlog2n is a conservative bound for the number of exchanges and comparisons required for heap sort algorithm. Rim tests on random sequences of integers to determine the number of exchanges and comparisons actually required. Plot the experimental results along with the value (3/2) nlog2n for merge sort. |
| 9. | What are similarities and differences between selection sort and heap sort? |