10 Sorting – Introduction to Data Structures in C

Chapter 10

Sorting

Chapter Outline

10.1 INTRODUCTION

In our daily life, we keep the information in particular order. This helps in accessing any part of it easily. Likewise, in database programs, large data is maintained in the form of records. It would be very difficult if data or records were unsorted. It is very boring to find a particular record if data or records are randomly stored. The process of sorting is essential for database applications.

Sorting is a process in which records are arranged in ascending or descending order. A group of fields is called record. For example, consider the following structure:

struct employee

{

char *name;

int age;

float height;

} s;

We are familiar with the above declarations and definitions. The object s contains three fields as described in the structure. The database is a collection of such fields. Each record contains the above fields, and it may vary depending upon the structure defined. The sorting can be done or any one or a combination of one or more fields. Suppose, we sort the records based on name. Then, the field name will be the key field. A record is quickly searched in a sorted database. Thus, sorting is a very useful concept of data structure.

10.2 SORTING

As already defined in the previous section sorting is a process in which records are arranged in ascending or descending order. In real life we come across several examples of sorted information. For example, in telephone directory the names of the subscribers and their phone numbers are written in alphabetial order. The records of the list of these telephone holders are to be sorted by their names. By using this directory, we can access the telephone number and address of the subscriber very easily.

Bankers or businesspersons sort the currency denomination notes received from customers in the appropriate form. Currency denominations of Rs 1000, 500, 100, 50, 20, 10, 5, and 1 are separated first and then separate bundles are prepared.

While we play the cards, initially the cards appear random but we keep them in ascending or descending order. In most of the offices the officials keep the files in a specific order for tracing them easily in future. Even at our homes, many times we keep the utensils in particular order such as increasing or decreasing height size. This helps us in accessing a particular item without difficulty. The sort method has great impact on data structures in our dally life.

For example, consider the five numbers 5, 9, 7, 4, 1.

The above numbers can be sorted in ascending or descending order.

The representation of these numbers in

Ascending order (0 to n): 1 4 5 7 9

Descending order (n to 0): 9 7 5 4 1

Similarly, alphabets can also be sorted.

Consider the alphabets B, A, D, C, E. These can be sorted in ascending or descending order.

Ascending order (A to Z): A B C D E

Descending order (Z to A): E D C B A.

10.3 INSERTION SORT

In insertion sort the element is inserted at appropriate place. For example, consider an array of n elements. In this type, swapping of elements is done without taking any temporary variable. The greater numbers are shifted towards the end of the array and smaller are shifted to beginning. Here, a real life example of playing cards can be cited. We keep the cards in increasing order. The card having least value is placed at the extreme left and the largest one at the other side. In between them the other cards are managed in ascending order.

Consider an example of playing cards. The playing cards having values 4, 6, 2, 1, 8 can be sorted according to the method described above, as

Fig. 10.1 illustrates the insertion sort.

Figure 10.1 Insertion sort

The process of insertion sort can be explained with following steps:

  • Get the random integer list. In the above example the list contains elements 4, 6, 2, 1, 8.
  • In the first pass the initial key is defined as 6 and compared with 4. As 6 is larger than 4 hence the position of 6 remains as it is.
  • In the second pass element 2 is compared with the initial key 6 and 4 and 2 are placed appropriately. That is, its position is now at first.
  • In the pass three the elements 1 is compared with the earlier three elements and placed appropriately. Its position is shown in Fig. 10.1.
  • In the pass 4 the last element 8 is compared with the initial key and it is found greater hence it is placed on the right side of 6.

The final sorted list appears as 1, 2, 4, 6, 8.

Thus, in the insertion sort we are actually finding the proper place for the element to insert with respect to the key.

Here, a program is provided on insertion sort.

Example 10.1

Write a program to sort array elements using insertion sort.

Solution

#include <stdio.h>

#include <conio.h>

main()

{

int nums[20],p=0,q=1,r,num;

clrscr();

printf("Enter number of elements : ");

scanf("%d",&num);

printf ("\n Enter %d elements : ",num);

while (p<num)

scanf("%d", &nums[p++]);

while(q<num)

{

   r=nums[q];

   for(p=q−1;p>=0 && r<nums[p];p−−)

   nums[p+1]=nums[p];

   nums[p+1]=r;

      printf(" Element %d inserted in appropriate place ",r);

   p=0;

   while (p<num)

   printf("%d ", nums[p++]);

   printf("\n");

   q++;

}

printf("Sorted elements are : ");

for (p = 0; p < num; p++)

printf("%d ", nums[p]);

}

>OUTPUT

Enter number of elements: 5

Enter 5 elements: 4 6 2 1 8

Element 6 inserted in appropriate place 4 6 2 1 8

Element 2 inserted in appropriate place 2 4 6 1 8

Element 1 inserted in appropriate place 1 2 4 6 8

Element 8 inserted in appropriate place 1 2 4 6 8

Sorted elements are: 1 2 4 6 8

Explanation In this program, the nested while loops are used. The variable q is initialized with 1 and p with 0. The variable r inside the while loop is used to take elements from array and the same element is compared with remaining elements. The ‘for’ loop inside the while loop executes if p>=zero and r (recently assigned value of array element) less than other elements, the insertion is carried out.

Example 10.2

Write a program to sort given list of elements by using insertion sort. Use pointer.

Solution

#include <stdio.h>

#include <conio.h>

main()

{

int ls[5],limit,*pt,p=0,q=0,tem;

pt=&ls[0];

clrscr();

printf("How many numbers would you like to sort?-");

scanf("%d",&limit);

printf("Enter %d elements:-",limit);

while(q<limit)

scanf("%d",&ls[q++]);

for(q=1;q<limit;q++)

{

tem=*(pt+q);

for(p=q−1;p>=0 && tem<*(pt+p);p−−)

*(pt+p+1)=*(pt+p);

*(pt+p+1)=tem;

}

printf("Sorted elements are:- ");

for (p = 0; p <limit; p++)

printf("%d ", ls[p]);

}

OUTPUT

How many numbers would you like to sort?-4

Enter 4 elements:-12 3 1 2

Sorted elements are:- 1 2 3 12

Explanation In this program, the limit for the array is made available with variable limit. The variable *pt is used for storing the starting address of the array element. With address location list is sorted by using the insertion sort method.

Time Complexity of Insertion Sort in Worst Case Consider an example to sort the 5 elements 9, 8, 7, 6 and 5. The comparisons are shown in the different passes in Fig. 10.2.

Figure 10.2 Insertion sort in worst case

The number of comparisons in worst case can be calculated by referring to Fig. 10.2. The comparisons in the different passes are made as follows:

  1. In pass =1 only one comparison is made between the elements 9 and 8.
  2. Pass =2 contains the two comparisons the element 7 is compared with 9 and 8.
  3. Three comparisons are made in the pass=3. The element 6 is compared with 7, 8 and 9.
  4. Four comparisons are made in the pass=4. The element 5 is compared with 6, 7, 8 and 9.

The total comparisons in the sorting method in worst case = 1+2+3+4=10.

Thus, theoretically f(n) = n(n−1)/2 =5(5−1)/2=10.

Practical values of comparisons are equal to the theoretical value.

10.4 SELECTION SORT

The selection sort is nearly the same as exchange sort. Assume, we have a list containing n elements. By applying selection sort, the first element is compared with all remaining (n−1) elements. The smallest element is placed at the first location. Again, the second element is compared with remaining (n−2) elements. If the item found is lesser than the compared elements in the remaining (n−2) list then the swap operation is done. In this type, entire array is checked for the smallest element and then swapped.

Fig. 10.3 illustrates the process of sorting elements by selection sort. In each pass, one element is sorted and kept at the left. Initially, the elements are temporarily sorted and after next pass, they are permanently sorted and kept at the left. Permanently sorted elements are covered with squares and temporarily with circles. Element inside the circle “O” is chosen for comparing with the other elements marked in a circle and sorted temporarily. Sorted elements inside the square “□” are shown.

Consider the elements 2, 6, 4, 8, and 5 for sorting under selection sort method.

  1. In pass 1, select element 2 and check it with the remaining elements 6, 4, 8, and 5. There is no smaller value than 2, hence the element 2 is placed at the first position.
  2. Now, select element 6 for comparing with remaining (n−2) elements, i.e. 4, 8, and 5. The smaller element is 4 than 6. Hence, we swap 4 and 6 and 4 is placed after 2.
  3. Again, we select the next element 6 and compare it with the other two elements 8 and 5 and swapping is done between 6 and 5.
  4. In the next pass element 8 is compared with the remaining one element 6. In this case, 8 is swapped with 6.
  5. In the last pass the 8 is placed at last because it is the highest number in the list.

Time Complexity The performance of sorting algorithm depends upon the number of iterations and time to compare them. The first element is compared with the remaining n−1 elements in pass 1. Then, n−2 elements are taken in pass 2. This process is repeated until the last element is encountered. The mathematical expression for these iterations will be equal to (n−1)+(n−2)+ … +(n− (n−1)). Thus, the expression become n*(n−1)/2.

Thus, the number of comparisons is proportional to (n2). The time complexity of selection sort is O (n2).

Comparison with Other Methods 1. This method requires more number of comparisons than quick sort, tree sort. 2. It is easier to implement than other methods such as quick sort, tree sort. 3. The performance of the selection sort is quicker than bubble sort.

Figure 10.3 Selection sort

Example 10.3

Write a program to sort elements of an array using selection sort.

Solution

#include <stdio.h>

# include <conio.h>

main()

{

int nums[15], p=0,q,r,num,t,small;

clrscr();

printf("How many elements to sort ? : ");

scanf("%d",&num);

printf("Enter %d elements : ":,num);

while (p<num)

scanf("%d", &nums[p++]);

for(p=0; p<num−1;p++)

{

      small = p;

      for(r=p+1; r<num;r++)

      if(nums[small] > nums[r])

      small = r ;

      if( p != small )

      {

       t = nums [p];

       nums[p] = nums[small];

       nums[small] = t ;

   }

   printf("\nAfter %d pass elements are : ",p+1);

   q=0;

   while (q< num)

   printf(" %d ", nums[q++]);

}

printf("\nSorted elements are: ");

p=0;

while( p < num)

printf("%d ", nums[p++]);

}

OUTPUT

How many elements to sort? : 5

Enter 5 elements: 8 6 4 2 5

After 1 pass elements are: 2 6 4 8 5

After 2 pass elements are : 2 4 6 8 5

After 3 pass elements are : 2 4 5 8 6

After 4 elements are : 2 4 5 6 8

Sorted elements are: 2 4 5 6 8

Explanation This program of selection sort uses nested loops. Using nested loops array elements are compared with one another. The value of loop variable p is assigned to variable small. The inner loop executes from (p+1) to num, in which the number present at array position nums [small] if greater than nums[r], the location indicated by r is assigned to small. The next if () block carries swapping of elements. Thus, all array elements are compared and necessary swapping is done.

10.5 BUBBLE SORT

Bubble sort is a commonly used sorting algorithm. In this type, two successive elements are compared and swapping is done if the first element is greater than the second one. The elements are sorted in ascending order. It is easy to understand but it is time consuming.

Bubble sort is an example of exchange sort. In this method repetitively comparison is performed between the two successive elements and if essential swapping of elements is done. Thus, step-by-step entire array elements are checked. It is different from the selection sort. Instead of searching the minimum element and then applying swapping, two records are swapped instantly upon noticing that they are not in order.

The Fig. 10.4 illustrates the exchange sort.

Let us consider the elements 9, 5, 1, 4, and 3 for sorting under bubble sort.

  1. In pass 1, first element 9 is compared with its next element 5. The next element is smaller than the 9. Hence, it is swapped. Now, the list is 5,9,1,4,3 again the 9 is compared with its next element 1 the next element is smaller than the 9 hence swapping is done. The same procedure is done with the 4 and 3 and at last we get the list as 5,1,4,3,9.
  2. In pass 2, the elements of pass 1 are compared. The first element 5 is compared with its next element 1.5 and 1 are swapped because 1 is smaller than 5. Now, the list becomes 1,5,4,3,9. Next, 5 is compared with element 4. Again, 5 and 4 are swapped. This process is repeated until all successive elements are compared and if the succeeding number is smaller than the present number then the numbers are swapped. The final list at the end of this pass is 1,4,3,5,9.
  3. In pass 3, the first element 1 is compared with the next element 4. The element 4 is having the higher value than the first element 1, hence they remain at their original positions. Next, 4 is compared with the subsequent element 3 and swapped due to smaller value of 3 than 4.
  4. At last, the sorted list obtained is 1,3,4,5,9.

Figure 10.4 Bubble sort

Example 10.4

Write a program to sort a given array by using the bubble sort.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

int a[5],i,j,temp;

clrscr();

printf("Enter the elements of an array : ");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

    for(i=0;i<5;i++)

    {

    for(j=i;j<4;j++)

    {

        if(a[i]>a[j+1])

        {

         temp=a[i];

         a[i]=a[j+1];

         a[j+1]=temp;

        }

      }

}

printf("Sorted elements in ascending order : ");

for(i=0;i<5;i++)

printf(" %d ",a[i]);

}

OUTPUT

Enter the elements of an array: 9 5 1 4 3

Sorted elements in ascending order: 1 3 4 5 9

Explanation In this program an array of five elements is declared. The variable j and i are loop variables. The variable i is used in the outer loop and j is used in the inner loop. The 'if' statement checks the number, it compares every current element denoted by ith location with (j+1)th element. If the number ith is greater, it is assigned to temp. The smaller number is assigned to ith location and temp (holds larger number) assigned to (j+1)th location. Thus, by exchange elements are sorted.

Time Complexity The performance of bubble sort in worst case is n (n−1)/2. This is because in the first pass n−1 comparisons or exchanges are made; in the second pass n−2 comparisons are made. This is carried out until the last exchange is made. The mathematical representation for these exchanges will be equal to (n−1)+(n−2)+ … +(n− (n−1)). Thus, the expression becomes n*(n−1)/2.

Thus, the number of comparisons is proportional to (n2). The time complexity of bubble sort is 0 (n2).

10.6 QUICK SORT

It is also known as partition exchange sort. It was invented by CAR Hoare. It is based on partition. Hence, the method falls under divide and conquer technique. The main list of elements is divided into two sub-lists. For example, a list of X elements are to be sorted. The quick sort marks an element in a list called as pivot or key. Consider the first element J as a pivot. Shift all the elements whose value is less than J towards the left and elements whose value is greater than J to the right of J. Now, the key element divides the main list into two parts. It is not necessary that selected key element must be in the middle. Any element from the list can act as key element. However, for best performance preference is given to middle elements. Time consumption of the quick sort depends on the location of the key in the list.

Consider the following example in which five elements 8,9,7,6,4 are to be sorted using quick sort. The Fig. 10.5 illustrates it.

Consider pass 1 under which the following iterations are made. Similar operations are done in pass 2, pass 3, etc.

In iteration 1 the first element 8 is marked as pivot one. It is compared with the last element whose value is 4. Here, 4 is smaller than 8 hence the numbers are swapped. Iteration 2 shows the swapping operation.

In the iteration 3 and 4, the position of 8 is fixed. In iteration 2, 8 and 9 are compared and swapping is done after iteration 2.

In iteration 3, 8 and 6 are compared and necessary swapping is done. After this, it is impossible to swap. Hence, the position of 8 is fixed. Because of fixing the position of 8 the main list is divided into two parts. Towards the left of 8 elements smaller than 8 are placed and towards the right greater than 8 are placed.

Towards the right of 8 only one element is present hence there is no need of further swapping. This may be considered under pass 2.

However, towards the left of 8 there are three elements and these elements are to be swapped as per the procedure described above. This may be considered under pass 3.

Figure 10.5 Quick sort

Example 10.5

Write a program to sort the array elements using quick sort.

Solution

#include<stdio.h>

#include <conio.h>

main()

{

int nums[15],numj=0;

int q_sort(int *,int,int);

int show(int *,int,int);

clrscr();

printf("Enter the number of elements : ");

scanf("%d",&num);

printf ("\n Enter %d elements : ",num);

while (j<num)

    scanf("%d",&nums[j++]);

    q_sort(nums,0,num−1);

printf("Sorted list is :\n");

show(nums,0,num−1);

}

q_sort(int items[],int lower,int upper)

{

int key,temp,l,r,key_placed=0;

int show(int *,int,int);

l=lower;

r=upper;

key=lower;

if(lower>=upper) return 0;

while(key_placed==0)

{

    while( items[key]<=items[r] & key!=r)

    r−−;

    if( key==r ) key_placed=1;

    if( items[key] > items[r] )

    {

        temp=items[key];

        items[key]=items[r];

        items[r]=temp;

        key=r;

    }

    while( items[key]>=items[l] && l!=key ) l++;

    if(key==l) key_placed=1;

    if( items[key] < items[l] )

    {

       temp=items[key];

       items[key]=items[l];

       items[l]=temp;

       key=l;

    }

}

printf(" * Key Placed is %d -> ",items[key]);

show(items,lower,upper);

printf("\n");

q_sort(items,lower,key−1);

q_sort(items,key+1,upper);

return 0;

}

show(int items[],int lower,int upper)

{

 while(lower<=upper)

 printf("%d ",items[lower++]);

 return 0;

}

OUTPUT

Enter the number of elements: 5

Enter 5 elements: 8 9 7 6 4

* Key Placed is 8 -> 4 6 7 8 9

* Key Placed is 4 -> 4 6 7

* Key Placed is 6 -> 6 7

Sorted list is : 4 6 7 8 9

Explanation In this program the functions q_sort () and show () are defined. In q_sort () elements are passed by value and address. The base address of an array nums is passed to function q_sort (). The variable num holds total number of elements. The q_sort () function is invoked recursively. In the first execution of q_sort (), value 0 is taken as lower key and (n1) is taken as upper key. If value of lower is greater than upper, the q_sort () function terminates. The value of upper variable is assigned to r. The value of r is decremented continuously until it reaches to key value. When the value of variables key and r are same the key is placed to one and the while loop is terminated. The ‘if ()’ statement carries swapping if element positioned at value key is greater than element positioned at value r. The same procedure is carried out when key is placed at one and swapping is carried out.

Time Complexity The efficiency of quick sort depends upon the selection of pivot. The pivot can bifurcate the list into compartments. Sometimes, the compartments are having the same sizes or dissimilar sizes. Assume a case in which pivot is in the middle. Thus, the total elements towards left of it and right are equal. We can express the size of list with the power of 2. The mathematical representation for the size is n=2s. The value of s can be calculated as log2 n.

After the first pass is completed there will be two compartments having equal number of elements, i.e. n/2 elements are on the left side as well as right side. In the subsequent passes, four portions are made and each compartment contains n/4 elements. In this way, we will be proceeding further until the list is sorted. The number of comparisons in different passes will be as follows:

Pass 1 will have n comparisons. Pass 2 will have 2*(n/2) comparisons. In the subsequent passes will have 4*(n/4), 8*(n/8) comparisons and so on. The total comparisons involved in this case would be 0 (n)+0 (n)+0 (n)+ … +s. The value of expression will be 0 (n log n). Thus, time complexity of quick sort is 0 (n log n).

Comparison with Other Methods

  1. This is the fastest sorting method among all.
  2. It is somewhat complex, so little difficult to implement than other sorting algorithms.

Figure 10.6 Inorder tree sort

10.7 TREE SORT

In binary tree, we know that the elements are inserted according to the value greater or less in between node and the root in traversing. If the value is less than traversing node, insertion is done at left side. If the value is greater than traversing node, it is inserted at right side. The elements of such tree can be sorted. This sorting involves creation of binary tree and then in order traversing is done. Few examples are illustrated based on the tree such as inorder tree and heap sort.

Consider the list containing elements 1, 3, 4, 2, 9 for sorting. Fig. 10.6 illustrates the inorder sort.

  1. At first, element 1 is inserted in the tree as root node and element 3 is inserted at right to the root because the inserted node is larger than the root. Fig. 10.5 (a) explains it.
  2. The element 4 is inserted at the right of the node 3 because it is larger than it. Insertion of element 4 is shown in Fig. 10.5(b).
  3. As per Fig. 10.5 (c) element 2 is inserted at the left of the node 3 due to lesser value.
  4. At last, the element 9 is inserted at right of the node 4. This is shown in Fig. 10.5 (d).
  5. The final binary tree is shown in Fig. 10.5 (e). Using the inorder traversing the sorted list is obtained.

Example 10.6

Write a C program to insert nodes into a binary tree and to traverse in inorder.

Solution

#include <stdio.h>

# include <malloc.h>

# include <conio.h>

# include <process.h>

struct nodes

{

 int data;

 struct nodes *ls;

 struct nodes *rs;

}*tree;

main()

{

int number;

int insert (int);

int inorder(struct nodes *);

int search(int ele,struct nodes **p,struct nodes **l);

tree=0;

clrscr();

printf("Enter the numbers and 0 to exit :-");

while(1)

{

scanf("%d",&number);

if (number==0)

      break;

insert(number);

}

printf("Inorder of the tree is as:-");

inorder(tree);

}

insert(int ele)

{

struct nodes *t,*father,*m_loc;

search(ele,&father,&m_loc);

if(m_loc!=0)

{

 printf("Item already present");

 return 0;

}

t=(struct nodes *)malloc(sizeof(struct nodes));

t->data=ele;

t->ls=0;

t->rs=0;

if(father==0)

tree=t;

else

if(ele<father->data)

  father->ls=t;

else

  father->rs=t;

return 0;

}

inorder(struct nodes *pr)

{

if(tree==0)

{

printf("Tree is empty");

return 0;

}

if(pr!=0)

{

      inorder(pr->ls);

      printf("%d ",pr->data);

      inorder(pr->rs);

}

return 0;

}

search(int ele,struct nodes **p,struct nodes **l)

{

struct nodes *pr,*p_s;

if(tree==0)

{

      *l=0;

      *p=0;

      return 0;

  }

if(ele==tree->data)

{

      *l=tree;

      *p=0;

      return 0;

  }

if(ele<tree->data)

  pr=tree->ls;

else

  pr=tree->rs;

p_s=tree;

while(pr!=0)

{

  if(ele==pr->data)

  {

      *l=pr;

      *p=p_s;

      return 0;

    }

  p_s=pr;

  if(ele<pr->data)

    pr=pr->ls;

else

    pr=pr->rs;

}

*l=0;

*p=p_s;

return 0;

}

OUTPUT

Enter the numbers and 0 to exit :-12 3 53 5 0

Inorder of the tree is as:-3 5 12 53

Explanation In this program, insert() and inorder() are user defined functions. The insert() function is invoked to insert the value in the binary tree. When entered number is zero, the insertion operation is terminated. The inorder() is used for traversing the binary tree. This function is used for getting the sorted list.

10.8 MERGING LIST

Merging is a process in which two lists are merged to form a new list. The new list is the sorted list. Before merging, individual lists are sorted and then merging is done. The procedure is very straightforward.

Consider a list of 9 elements. They are as follows:

21,12,34,3,7,11,9,23,4.

 

Pass 1: In merge sort, first the list is divided into pairs containing two elements each. These can be shown as follows. If numbers are even then exact pairs are done. In this case nine numbers are assumed for selection. So, 5 pairs are possible. They are as follows:

After division of the list into pairs sort the elements of each pair.

Pass 2: Merge the pairs after sorting in the first pass. The elements appear as follows:

Sort the elements of the above merged pairs. On sorting, the elements will be as follows:

Pass 3: Again, merge two groups as follows:

Sort the elements of the merge groups.

Pass 4: Merge the element 4 with the remaining element.

At last pass all elements get sorted.

A program on merge sort is provided for understanding.

Example 10.7

Write a program to create two-array list of integers. Sort and store elements of both of them in the third list.

Solution

#include <stdio.h>

# include <conio.h>

# include <math.h>

main ()

{

int m,n,p,sum=0;

int listA[5],listB[5],listC[10]={0};

clrscr();

printf ("\n Enter elements for first list : ");

for (m=0;m<5;m++)

{

      scanf ("%d",&listA[m]);

      if (listA[m]==0) m−−;

      sum=sum+abs(listA[m]);

}

      printf ("\n Enter elements for second list : ");

for (n=0;n<5;n++)

{

      scanf ("%d",&listB[n]);

      if (listA[n]==0) n−− ;

      sum=sum+abs(listB[n]);

}

p=n=m=0;

m=m-sum;

while (m<sum)

{

  for (n=0;n<5;n++)

   {

      if (m==listA[n] || m==listB[n])

      listC[p++]=m;

      if (m==listA[n] && m==listB[n])

      listC[p++]=m;

   }

   m++;

}

puts (" Merged sorted list : ");

for (n=0;n<10;++n)

 printf (" %d ",listC[n]);

}

OUTPUT

Enter elements for first list : 1 5 4 −3 2

Enter elements for second list : 9 5 1 2 10

Merged sorted list :

−3 1 1 2 2 4 5 5 9 10

Explanation In this program three arrays listA [], listB [] and listC [] are declared. Using for loop elements in listA [] and listB [] are declared. The sum of all ten elements entered in both the lists are taken in variable sum. The while and nested for loop checks corresponding elements of both the list.

  • If one of the corresponding elements is same, that element is stored in the list[] array.
  • If both the corresponding elements are same, they are stored in successive locations in the listC [].

The value of m is initially zero. The sum obtained is again subtracted from m. This is because if negative numbers are entered, they are to be considered in the sorting. For example, the value of sum=20. In real execution, the sum may be different depending on integers entered.

Value of m would be m = −20 ( as pre m = m−20 when m = 0)

Thus, in the while loop value of m varies from −20 to 20. In this range, all the entered elements are covered. The value of m changes from −20 to 20, i.e. −20,−19 upto +20 in ascending order. Thus, the same order is applied while saving element in arrayC[].

Time Complexity f(n) represents the number of comparisons needed to sort an array consisting of n elements. In worst case in every pass n comparisons would be needed for sorting the elements. The algorithms require at most log 2 n passes.

Please note that this algorithm has the same order as that of heap sort. Also, for average case it is similar to quick sort.

10.9 HEAP SORT

In heap sort, we use the binary tree in which the nodes are arranged in specific prearranged order. The rule prescribes that each node should have bigger value than its child node. The following steps are to be followed in heap sort:

  1. Arrange the nodes in the binary tree form.
  2. Node should be arranged as per the specific rules.
  3. If the inserted node is bigger than its parent node then replace the node.
  4. If the inserted node is lesser than its parent node then do not change the position.
  5. Do not allow entering nodes on right side until the child nodes of the left are fulfilled.
  6. Do not allow entering nodes on left side until the child nodes of the right are fulfilled.
  7. The procedure from step 3 to step 6 is repeated for each entry of the node.

Consider the numbers 56, 23, 10, 99, 6, 19, 45, 45, 23 for sorting using heap. Sorting process is illustrated in Fig. 10.7.

  1. At first, we pickup the first element 56 from the list. Make it as the root node.
  2. Next, take the second element 23 from the list. Insert this to the left of the root node 56. Refer the Fig. 10.7 (2).
  3. Then, take the third element 10 from the list for insertion. Insert it to the right of the root node.
  4. Take the fourth element 99. Insert it to the left side node 23. The inserted element is greater than the parent element, hence swap the 99 with 23. But the parent node 56 is smaller than the child node 99 hence 99 and 56 are swapped. After swapping 99 becomes the root node. This is shown in Fig. 10.7 (4) and (5).
  5. Consider the next element 6 to insert in the tree. Insert it at left side. There exists left node, hence insert it to the right of the 56. Refer Fig. 10.7 (6).
  6. Element 19 is inserted to the right side of the 99 because the left side gets full. Insert the element 19 to the right node 10. However, the parent element is lesser than the child, hence swaps the 19 with 10.
  7. Now, element 45 is to be inserted at the right side of 19. However, the parent element is having the value lesser than the child element hence swap the 45 with 19. Refer the Fig. 10.7 (9) and (10).
  8. Now, the right side is fully filled hence add the next element 45 to the left. The element 45 is inserted at the last node of the left, i.e. 23. However, the parent element is having the value lesser than the child element hence swap 45 with 23. Refer the Fig. 10.7 (11) and (12).
  9. Insert the last element 23 to the left side node, i.e. 45. The left of the 45 is already filled hence insert the element 23 at the right of the 45. Refer the Fig. 10.7 (13).
  10. At last, we get a sorted heap tree, as shown in Fig. 10.7 (13).

Figure 10.7 Heap sort

Time Complexity We know that the depth of the complete binary tree is (log2n). In worst case, the number of comparisons in each step would be equal to the depth of the tree. The number of comparisons for the above observation would be O (n log2n). Thus, the number of comparisons in this method would be O (n log2 n).

10.10 RADIX SORT

The radix sort is a technique, which is based on the position of digits. The number is represented with different positions. The number has units, tens, hundreds positions onwards. Based on its position the sorting is done. For example, consider the number 456, which is selected for sorting. In this number 6 is at units position and 5 is at tens and 4 is at the hundreds position. 3 passes would be needed for the sorting of this number with this procedure. In the first pass, we place all numbers at the unit place. In the second pass all numbers are placed in the list with consents to the tens position digit value. Also, in the third pass the numbers are placed with consent to the value of the hundreds position digit.

For example:

23,46,12,34,45,49,58,38,10,21.

In the first pass, the numbers are placed as per the value of the unit position digit. First, take number 23, which is present at the first in the list. Insert 23 in the packet labelled 3. Second number 46 is inserted in packet 6. 12 is inserted in the packet 2. The number 34 is inserted in the packet 4. 45 in the packet 5, 46 in the packet 6, 58 in the packet 8, 38 is also in the packet 8, 10 is in the packet 0 and 21 is in the packet 1. The numbers are inserted in the packets as per the sequence of that number in the original list.

 

Table 10.1 Sorting the numbers on unit place digit

In first pass sort the elements as per the value of the unit place digit. The operation is shown in the above Table 10.1. After the first pass we get the following list as:

10,21,12,23,34,45,46,58,38,49.

Perform the second pass operation on the list, which is sorted list after the first pass. As per the values of the digit of the tens position, the place of the elements is fixed. At first, take the first element 10 of the list, which is obtained after the first pass. Insert 10 into the packet 1; insert 21 in the 2(second) packet. This procedure is repeated until the end of the list. In the second pass, the numbers are as:

 

Table 10.2 Sorting the numbers on ten’s place digit

Table 10.2 shows the second pass for sorting the numbers. The sorted list after the second pass is as:

10,12,21,23,34,38,45,46,49,58.

By appropriately placing numbers, the sorted list of the items or elements is obtained. In this example of radix sort, two passes are required for complete sorting. The number of passes depends upon the length of the greatest number in the list. If the list contains the numbers greater than the 99, then the number of passes must be greater than 3 or equal to 3.

Example 10.8

Write a program to sort the given single digit numbers by using the radix sort.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

static int bk[10][5],k1,k2,k3,k4,k5,k6,k7,k8,k9,k0,p;

int ij,no_p,list[5],slist[5];

clrscr();

printf("Enter the one digit elements:-");

for(i=0;i<5;i++)

scanf("%d",&list[i]);

for(i=0;i<5;i++)

{

no_p=list[i]%10;

switch(no_p)

{

case 0: bk[0][k0++]=list[i]; break;

case 1: bk[1][k1++]=list[i]; break;

case 2: bk[2][k2++]=list[i]; break;

case 3: bk[3][k3++]=list[i]; break;

case 4: bk[4][k4++]=list[i]; break;

case 5: bk[5][k5++]=list[i]; break;

case 6: bk[6][k6++]=list[i]; break;

case 7: bk[7][k7++]=list[i]; break;

case 8: bk[8][k8++]=list[i]; break;

case 9: bk[9][k9++]=list[i]; break;

}

}

printf("The elements in table are:-");

printf("\n--------------------");

printf("\n\t\t\tElements");

for(j=0;j<10;j++)

{

printf("\nElements in bucket %d:-"j);

for(i=0;i<5;i++)

if(bk[j][i]>0)

{

printf("%3d",bk[j][i]);

slist[p++]=bk[j][i];

}

}

printf("\n--------------------");

printf("\nThe sorted numbers:-");

for(i=0;i<5;i++)

printf("%2d",slist[i]);

}

OUTPUT

Enter the one digit elements:- 1 6 8 3 6

The elements in table are:-

-----------------------------

 

Elements

Elements in bucket 0:-

 

Elements in bucket 1:-

    1

Elements in bucket 2:-

 

Elements in bucket 3:-

    3

Elements in bucket 4:-

 

Elements in bucket 5:-

 

Elements in bucket 6:-

    6    6

Elements in bucket 7:-

 

Elements in bucket 8:-

    8

Elements in bucket 9:-

 

-----------------------------

The sorted numbers:- 1 3 6 6 8

Explanation In this program the list[] is initialized to store the inputted numbers from the keyboard. The static int bk[][] is used to store the numbers in the buckets 0 to 9. The k0 to k9 are the variables, which are used to limit the buckets. The no_p variable stores the elements in buckets by the switch() control statement. At last, the sorted list is stored into the slist[].

Example 10.9

Write a program to sort the given two digit numbers by using the radix sort. Use function.

Solution

#include<stdio.h>

#include<conio.h>

int l[5],flag=0;

main()

{

int i,j;

void place();

clrscr();

printf("Enter five elements with two digits:-");

for(i=0;i<5;i++)

scanf("%d",&l[i]);

printf("\nThe first sorted table is");

place();

printf("\nFirst sorted list :-");

for(i=0;i<5;i++)

printf("%3d",l[i]);

  flag=2;

  getch();

  printf("\n\nThe final sorted table is");

  place();

  printf("\nFinal sorted list :-");

  for(i=0;i<5;i++)

  printf("%3d",l[i]);

  getch();

}

void place()

{

 int k1,k2,k3,k4,k5,k6,k7,k8,k9,k0;

 int a,p,q,r;

 int n,b[10][5]={0};

 k0=k1=k2=k3=k4=k5=k6=k7=k8=k9=a=0;

while(a<5)

  {

    if(flag==2)

      n=l[a]/10;

    else

      n=l[a]%10;

  switch(n)

    {

        case 0: b[0][k0++]=l[a]; break;

        case 1: b[1][k1++]=l[a]; break;

        case 2: b[2][k2++]=l[a]; break;

        case 3: b[3][k3++]=l[a]; break;

        case 4: b[4][k4++]=l[a]; break;

        case 5: b[5][k5++]=l[a]; break;

        case 6: b[6][k6++]=l[a]; break;

        case 7: b[7][k7++]=l[a]; break;

        case 8: b[8][k8++]=l[a]; break;

        case 9: b[9][k9++]=l[a]; break;

    }a++;

  }

r=0;

for(p=0;p<10;p++)

  {

    if(b[p][0]!=0)

    printf("\nBucket %d contain:-",p);

    for(q=0;q<5;q++)

     if(b[p][q]>0)

     {

      printf("%3d",b[p][q]);

      l[r++]=b[p][q];

    }

  }

}

OUTPUT

Enter five elements with two digits:-99 12 11 48 10

The first sorted table is

Bucket 0 contain:- 10

Bucket 1 contain:- 11

Bucket 2 contain:- 12

Bucket 8 contain:- 48

Bucket 9 contain:- 99

First sorted list :- 10 11 12 48 99

The final sorted table is

Bucket 1 contain:- 10 11 12

Bucket 4 contain:- 48

Bucket 9 contain:- 99

Final sorted list :- 10 11 12 48 99

Explanation In this program function place() is used to sort the list. The variable n is used to store either the reminder or quotient. The modulus operator is used for finding the unit place and the divide operation for tens place. Then, these elements are stored in buckets by the switch () control statement. After the first call of the place () the first sorted list is stored into the l[] and after second call the final sorted list is placed into l[].

Time Complexity Number of comparisons require for radix sort algorithm in the worst case f(n)=O(n2) and in best case f(n)= O( n log 2 n).

10.11 PARTITION EXCHANGE SORT

The partition exchange sort is the sorting technique in which list of elements is divided into the two subparts. Using the pivot from the list makes the sublist of the list. The left part is called left sublist and the right part is called right sublist. On the sublist quick or the tree sort is performed and the two-sorted parts are prepared and combined.

For example, consider the following list:

24, 30, 27, 32, 11, 21, 19.

Assume the pivot key selected is 24 and the smaller numbers than pivot are shifted on its left side and remaining greater elements to the right of it. The element 24 divides the list in two parts. The Fig. 10.8 shows the partition exchange sort.

Figure 10.8 Partition exchange sort

After the swapping the elements towards left of the pivot:

11, 21, 19, 24, 30, 27, 32.

After removing 24 the two sublists become:

11, 21, 19 and 30, 27, 32.

The left and right parts after sorting:

11, 19, 21

27, 30, 32

After combining the two parts including the pivot key the sorted list becomes:

11, 19, 21, 24, 27, 30, 32.

Following program is presented on the same concept.

Example 10.10

Write a program to sort the elements by using the partition exchange sort.

Solution

#include<stdio.h>

#include<conio.h>

int q_sort(int items[],int lower,int upper);

main()

{

 int arr[7],ltree[7],rtree[7];

 int i=0,j,pivot,lcount=0,rcount=0;

 clrscr();

 printf("\nEnter the 7 elements:");

 for(i=0;i<7;i++)

 scanf("%d",&arr[i]);

 printf("Enter pivot element:-");

 scanf("%d",&pivot);

 for(j=0;j<7;j++)

 {

if(arr[j]<=pivot)

{

++lcount;

ltree[lcount]=arr[j];

}

if(arr[j]>pivot)

{

++rcount;

rtree[rcount]=arr[j];

}

}

q_sort(ltree,0,lcount);

for(j=0;j<lcount;j++)

printf("%d ",ltree[j]);

q_sort(rtree,0,rcount);

for(i=0;i<rcount;i++)

printf("%d ",rtree[i]);

}

int q_sort(int items[],int lower,int upper)

{

int key,temp,l,r,key_placed=0;

l=lower;r=upper;key=lower;

if(lower>=upper)

  return 0;

while(key_placed==0)

{

  while( items[key]<=items[r] && key!=r)

  r−−;

  if( key==r )

  key_placed=1;

  if( items[key] > items[r] )

  {

      temp=items[key];

      items[key]=items[r];

      items[r]=temp;

      key=r;

  }

  while( items[key]>=items[l] && l!=key )

    l++;

    if(key==l)

    key_placed=1;

    if( items[key] < items[l] )

    {

      temp=items[key];

      items[key]=items[l];

      items[l]=temp;

      key=l;

    }

  }

q_sort(items,lower,key−1);

q_sort(items,key+1,upper);

return 0;

}

OUTPUT

Enter the 7 elements:- 24 30 27 32 11 21 19

Enter pivot element:- 24

11 19 21 24 27 30 32

Explanation In this program seven elements are inputted for sorting into the arr[]. After selecting the pivot key the elements whose values are lower than pivot key are placed into the ltree[] otherwise rtree[]. Then the q_sort() is resurvey called for sorting the left as well as right side elements of that pivot key. In the function q_sort() the values of the lower and upper bound are checked. If the value of the lower bound is greater than or equal to the upper bound than the function is terminated else the remaining elements are to be sorted. After performing these operations the sorted list is obtained for the ltree[] as well as rtree[].

Summary

This chapter deals with sorting and its implementations.

  1. Sorting is a process in which records are arranged in ascending or descending order.
  2. This chapter presents information on various sorting methods ; each of them is illustrated with suitable example.
  3. Insertion sort: In insertion sort the element is inserted at appropriate place. Here, a real life example of playing cards can be quoted. The cards are kept in increasing order. The card having least value is placed at the extreme left and the largest one at the other side. In between them the other cards are inserted in ascending order.
  4. Selection sort: The selection sort is almost same as exchange sort. By applying selection sort, the first element is compared with remaining (n−1) elements. The smallest element is placed at the first location. Again, the second element is compared with remaining (n−2) elements. If the item found is lesser than the compared elements in the remaining n−2 list then the swap operation is done. In this type, entire array is checked for the smallest element and then swapped.
  5. Bubble sort: Bubble sort is frequently used sorting algorithm. In this method, two successive elements are compared and exchanging is done if the first element is greater than the second one. The elements are sorted in ascending order.
  6. Quick sort: It is also recognized as partition exchange sort. This method also falls under divide and conquer technique. The main list of elements is divided into two sub-lists. Any one element from the list is marked as pivot key in the quick sort. Now, the pivot key divides the main list into two parts. It is not necessary that selected key element must be at middle. Any element from the list can act as key element. However, for best performance preference is given to middle elements. Time consumption of the quick sort depends on the location of the key in the list.
  7. Tree sort: Inorder and heap sort methods are elaborated under tree sorting. Inorder tree sorting method involves arranging the elements as per rules. In this method, firstly the left element of tree is chosen, then node and right node. The rule for heap sort prescribes that each parent node should have bigger value.
  8. Heap sort: In heap sort, binary tree is used in which the nodes are arranged in specific prearranged order. The rule prescribes that each node should have bigger value than its child node. The heap sort process can be followed from the figure and example given in this chapter.
  9. Radix sort: The radix sort is based on the position of digits. Based on the positions of digits sorting is done.
  10. Partition exchange sort: The partition exchange sort divides the elements into the two subparts. A pivot is selected among the elements. The elements whose values are smaller than the pivot are shifted towards left of it. The right part has elements whose values are greater than the pivot.
Exercises
  1. Answer the following questions:
    1. What is sorting? How is sorting essential for data base applications?
    2. Explain different types of sorting methods.
    3. Distinguish between selection and exchange sort.
    4. Explain the heap sort method.
    5. How does the merge sort work?
    6. How does radix sort work?
    7. Explain the method of partition exchange sort.
    8. Explain the insertion sort with its time complexity.
    9. Compare the performance of selection and insertion sort.
    10. How does the quick sort work? Explain with a suitable example.
    11. Describe the working of tree sort.
  2. Write following programs:
    1. Apply selection sort on given ten numbers and sort them in ascending order.
    2. Sort ten names of the students using merge sort.
    3. Apply the quick sort to the given ten names and sort them in alphabetic order.
    4. Write a program for sorting the given list by descending orders, using selection sort.
    5. Apply tree-sorting method (inorder) on given ten numbers and arrange them in ascending order.
    6. Write a program by using heap sort for sorting given numbers.
    7. Apply partition sort on twelve numbers.
    8. Write a program for sorting two digit numbers using radix sort.
    9. Write a function for bubble sort.
    10. Use selection sort method for sorting five numbers using pointers.
    11. Write a program to sort 15 elements using bubble sort. Assume any suitable elements.
    12. Write a program to sort the elements 2,32,45,67,89,4,3,8,10 in descending order using insertion sort.
    13. Write a program to sort a given list of elements using tree sort.
    14. Write a program to sort one digit number by using the radix sort method. Use pointer.
    15. Write a program to sort the following numbers in ascending order using selection sort. 12,34,5,78,4,56,10,23,1,45,65.
  3. Select the appropriate option for each of the following questions:
    1. The process of arranging records in ordered manner is called
      1. sorting
      2. searching
      3. indexing
      4. none of the above.
    2. In insertion sort, the shifting of numbers are:
      1. shift greater numbers at end and smaller at beginning of the array
      2. shift greater number at the middle and smaller at right
      3. shift smaller at the center and greater at beginning
      4. none of the above.
    3. In this type of sort list is divided in two sub-lists:
      1. quick sort
      2. exchange sort
      3. merge sort
      4. none of the above.
    4. The exchange sort is also called
      1. bubble sort
      2. merge sort
      3. shell sort
      4. none of the above.
    5. In the bubble sort the sorting is done with comparing
      1. successive elements
      2. first and last elements
      3. last and middle elements
      4. none of the above.
    6. In tree sort the elements are sorted with
      1. inorder traversing
      2. preorder traversing
      3. post order traversing
      4. none of the above.
    7. Radix sort method is based on
      1. the positions of the digits
      2. the cubes of digits
      3. the squares of digits
      4. none of the above.
    8. For sorting the elements with partition exchange sort which method is used?
      1. bubble sort
      2. quick sort
      3. heap sort
      4. none of the above.
    9. In heap sort the numbers are initially arranged in
      1. ascending order
      2. descending order
      3. binary tree
      4. none of the above.
    10. With merge sort number of list that can be sorted are
      1. one list
      2. more than one lists
      3. none of the above.
  4. What is the output of each of the following programs?
    1. #include<stdio.h>

      #include<conio.h>

      main()

      {

      static int b[10][7],k1,k2,k3,k4,k5,k6,k7,k8,

      k9,k0,p;

      int ij,no,l[7],sl[7];

      clrscr();

      printf("Enter elements <10:-");

      for(i=0;i<7;i++)

      scanf("%d",&l[i]);

      i=0;

      while(i<7)

      {

      no=l[i]%10;

      switch(no)

      {

      case 0: b[0][k0++]=l[i]; break;

      case 1: b[1][k1++]=l[i]; break;

      case 2: b[2][k2++]=l[i]; break;

      case 3: b[3][k3++]=l[i]; break;

      case 4: b[4][k4++]=l[i]; break;

      case 5: b[5][k5++]=l[i]; break;

      case 6: b[6][k6++]=l[i]; break;

      case 7: b[7][k7++]=l[i]; break;

      case 8: b[8][k8++]=l[i]; break;

      case 9: b[9][k9++]=l[i]; break;

      }i++;

      }

      printf("The table is:-");

      for(j=0;j<10;j++)

      {

      printf("\nBucket %d contain:-"j);

      for(i=0;i<5;i++)

      if(b[j][i]>0)

      {

      printf("%3d",b[j][i]);

      sl[p++]=b[j][i];

      }

      }

      printf("\nSorted list:-");

      for(i=0;i<7;i++)

      printf("%2d",sl[i]);

      }

       

    2. #include <stdio.h>

      #include <conio.h>

      main()

      {

      int ns[5],p=0,q=1,temp;

      clrscr();

      printf ("\n Enter 5 elements : ");

      while (p<5)

      scanf("%d", &ns[p++]);

      for(q=1;q<5;q++)

      {

      temp=ns[q];

      for(p=q−1;p>=0 && temp<ns[p];p−−)

      ns[p+1]=ns[p];

      ns[p+1]=temp;

      }

      printf("Sorted elements are : ");

      for (p = 0; p < 5; p++)

      printf("%d ", ns[p]);

      }

       

    3. #include <stdio.h>

      # include <conio.h>

      main()

      {

      int p=0,q,r,num,t,small;

      int arr[5]={ 12,23,1,4,2 };

      clrscr();

      for(p=0; p<4;p++)

      {

      small = p;

      for(r=p+1; r<5;r++)

      if(arr[small] > arr[r])

      small = r ;

      if( p != small )

      {

      t = arr [p];

      arr[p] = arr[small];

      arr[small] = t ;

      }

      }

      printf("\nSorted elements are: ");

      p=0;

      for(p=0;p<5;p++)

      printf("%d ", arr[p]);

      }

       

    4. #include<stdio.h>

      #include<conio.h>

      main()

      {

      int arr1[5]={12,3,122,321,1},i,j,t;

      clrscr();

      for(i=0;i<5;i++)

      for(j=i;j<4;j++)

      if(arr1[i]>arr1[j+1])

      {

      t=arr1[i];

      arr1[i]=arr1[j+1];

      arr1[j+1]=t;

      }

      for(i=0;i<5;i++)

      printf(" %d ",arr1[i]);

      }

       

    5. # include <stdio.h>

      # include <conio.h>

      # include <math.h>

      main ()

      {

      int m,n,p,sum=0,sl[10]={0};

      int l1 [5]={4,2,1,43,3},l2[5]={9,7,6,8,5};

      clrscr();

      for (n=0;n<5;n++)

      {

      sum=sum+l1[n];

      }

      for (n=0;n<5;n++)

      {

      sum=sum+l2[n];

      }

      p=n=m=0;

      m=m-sum;

      while (m<sum)

      {

      for (n=0;n<5;n++)

      {

      if (m==l1[n] || m==l2[n])

      sl[p++]=m;

      if (m==l1[n] && m==l2[n])

      sl[p++]=m;

      }

      m++;

      }

      puts (" Merged sorted list : ");

      for (n=0;n<10;++n)

      printf (" %d ",sl[n]);

      }

       

    6. #include <stdio.h>

      #include <conio.h>

      main()

      {

      int ns[5]={12,34,2,10,1},*pt,p=0,q=1,temp;

      pt=&ns[0];

      clrscr();

      for(q=1;q<5;q++)

      {

      temp=*(pt+q);

      for(p=q−1;p>=0 && temp<*(pt+p);p−−)

      *(pt+p+1)=*(pt+p);

      *(pt+p+1)=temp;

      }

      printf("Sorted elements are : ");

      for (p = 0; p < 5; p++)

      printf("%d ", ns[p]);

      }

       

    7. #include <stdio.h>

      #include <conio.h>

      int ns[5]={123,67,34,2,12};

      main()

      {

      int p;

      void sort();

      clrscr();

      sort();

      printf("Sorted elements:- ");

      for (p = 0; p < 5; p++)

      printf("%d ", ns[p]);

      }

      void sort()

      {

      int q,p,temp;

      for(q=1;q<5;q++)

      {

      temp=ns[q];

      for(p=q−1;p>=0 && temp<ns[p];p−−)

      ns[p+1]=ns[p];

      ns[p+1]=temp;

      }

      }