Sorting Procedure 

 Designed and Managed by
DCube Software Technologies, Nagpur (India) 
Last Revised: 16th Feb 2001 8:05:20

Radix Sort is generally used to sort strings. Since there are 26 alphabets the radix is taken as 26,i.e the names are arranged in 26 classes, where the first class consists of those names that begin with 'A', the second class consists of those names that begin with 'B' and so on. The radix sort is the method used by a card sorter. Decimal numbers, where the radix is 10 are sorted in the same way and hence use only the first 10 pockets of the sorter. The sorter uses a radix reverse-digit sort on numbers.
Suppose a card sorter is a given collection of cards where each card is given a collection of cards where each card contains a 3-digit number punched in columns 1 to 3. The cards are first sorted according to the units digit. On the second pass, the cards are sorted according to the tens digit. On the third and last pass, the cards are sorted according to the hundreds digit.
Suppose 9 cards are punched as follows :

348, 143, 361, 423, 538, 128, 321, 543, 366

Given to a card sorter, the numbers would be sorted in three phases, as :
a) In the first pass, the units digits are sorted into pockets. The cards are collected pocket by pocket, from pocket 9 to pocket  0.   The cards are now reinput to the sorter.

 c) In the third and final pass, the hundreds digits are sorted into pockets.

When the cards are collected after the third pass, the numbers are in the following order :

128, 143, 321, 348, 361, 366, 423, 538, 543

The number C of comparisons needed to sort nine such 3-digit numbers is bounded as follows :
C <= 9 * 3 * 10

The 9 comes from the nine cards, the 3 comes from the three digits in each number, and the 10 comes from radix d = 10 digits.

Complexity of Radix Sort:

Suppose a list A of n items is given. Let d denote the radix ( e.g. d = 10 for decimal digits, d= 26 for letters and d = 2 for bits ), and suppose each item Ai is represnted by means of s of digits :
A_i = d_i1d_i2...dis

The radix sort algorithm will require s passes, the number of digits in each item. Pass K will compare each dik with each of the d digits. Hence the number C(n) of comparisons for the algorithm is bounded as follows :
C(n) <= d * s * n

Although d is independent of n, the number s does depend on n. In the worst case s = n, so C(n) = O(n²). In the best case,
s= log_dn, so C(n) = O(n log n). In other words, radix sort performs well only when the number s of digits in the representation of the A_i's is small. Another drawback of radix sort is that one may need d * n memory locations. This comes from the fact that all the items may be sent to the same pocket during a given pass. This drawback may be minimized by using linked lists rather than arrays to store the items during a given pass. However, one will still require 2 * n memory locations.

# include "math.h"
main( )
{
    int a[] = { 348,143,361,423,538,128,321,543,366};
    int i, j, k, nd = 0, n, t, l, count, c ,ini ;

    /* To find the Greatest number */
    clrscr( ) ;
    t = a[0] ;
    for ( i =1 ; i < 10 ; i++ )
    	if( a[i] > t )
        	t = a[i] ;

    while ( t > 0 )
    {
    	nd++ ;
        t /= 10 ;
    }

    count = 0 ;
    for ( k = 1 ; k <= nd ; k++ )
    {
	for ( i = 0 ; i < 9 ; i++ )
	{
		for ( j = 0 ; j < 9 ; j++ )
		{
 		       if (k == nd )
			c = a[j] / (int)pow ( 10, k-1 ) ;
		       else
	   		c = a[j] / (int)pow ( 10, k-1 ) % 10 ;
		       if ( c == i && j >= count )
		        {
                		ini = j ;

			t = a[j] ;

		                for ( l = ini ; ini > count ; ini-- )
			{
				a[ini] = a[ini-1] ;
				a[count] = t ;
				count++ ;
			}
		        }
		        else if ( c == i )
	                         {
                		ini = j ;
			t = a[j] ;
		                for ( l = ini ; ini < count ; ini++ )
			{
				a[ini] = a[ini+1] ;
				a[count] = t ;
				count++ ;
		                 }

		          }
		}
	        count = 0 ;
	}
           }

           


for ( i = 0 ; i < 9 ; i++ )
    	printf ( " %d", a[i] ) ;
}

Divide the list into n sublists of size 1 and merge adjacent pairs of lists. We then have approximately n/2 sublists of size 2. Repeat this process until there is only one list remaining of size n. Suppose the array A contains 14 elements as follows :
66, 33, 40, 22, 55, 88, 60, 11, 80, 20, 50, 44, 77, 30

Each pass of the merge- sort algorithm will start at the beginning of the array A and merge pairs of sorted subarrays as follows :

    Pass 1.	Merge each pair of elements to obtain the following list of sorted pairs :

    	33,66  	22,40	55,88	11,60	20,80	44,50	30,77

    Pass 2.	Merge each pair of pairs to obtain the following list of sorted quadruplets :

            	22,33,40,66	11,55,60,88	20,44,50,80	30,77

   Pass 3.	Merge each pair of sorted quadruplets to obtain the following two sorted subarrays :

 	11,22,33,40,55,60,66,88	20,30,44,50,77,80

   Pass 4.	Merge the two sorted subarrays to obtain the single sorted array.

    	11,20,22,30,33,40,44,50,55,60,66,77,80,88
    
    

Complexity of merge sort

The algorithm requires at most log n passes. Each pass merges a total of n elements, and by the discussion on the complexity of merging, each pass will require at most n comparisons. Accordingly, for both the worst case and average case,
f(n) <= n log n
This algorithm has the same orger as heap sort and the same average order as quicksort. The main drawback of merge-sort is that it requires an auxiliary array with n elements.
The result of merge sort can summarize as :

Algorithm	Worst Case	Average Case	Extra Memory
Merge Sort	n log n = O(n log n)	n log n = O(n log n)	O(n)

   
       	
# include "math.h"
# define MAX 14
void main( )
{
	int a[] = { 66, 33, 40, 22, 11, 88, 60, 11, 80, 20, 50, 44, 77, 30  } ;
	int i = 0, j = 0, k = 0, l, c, n, no, num = MAX, noe = 1, b[MAX] , inc = 0, ind = 0 ;

	clrscr( ) ;
	n = no = num ;

	if ( n % 2 )
                     c = n+1 ;
	else
	     c = n ;

	while ( n > 0 )
	{
	     k++;
	     n /= 2;
	}

	no = num ;

	for ( i = 1 ; i <= k ; i++ )
	{
		 c/= 2;
		for ( j = 0 ; j < c ; j++ )
		{
			if ( no >= pow(2,i))
		                       merge ( &a[ind *pow(2,i-1)], noe, &a[(ind+1) *pow(2,i-1) ], noe, &b[ind*pow(2,i-1)] ) ;
			else
			{	if ( num % (int)pow(2,i) > noe ) 
					merge ( &a[ind *pow(2,i-1)], noe, &a[(ind+1) *pow(2,i-1) ], 
							num%(int)pow(2,i)-noe, &b[ind*pow(2,i-1)] ) ;
				else
					merge ( &a[ind *pow(2,i-1)], num%(int)pow(2,i), 
							&a[(ind+1) *pow(2,i-1)], 0, &b[ind*pow(2,i-1)] ) ;
			}

			ind += 2 ;
			no -= pow(2,i);
		}
		ind = inc += 2;
		ind=0;

		if ( c%2 )
                                     c++;
		noe *= 2 ;
		no = num ;

		for ( j = 0 ; j < MAX ; j++ )
                                      a[j] = b[j] ;
	}

	printf ( "The Sorted array is as follows : \n" ) ;

	for ( i = 0 ; i < MAX ; i++ )
		printf ( " %d", a[i] ) ;
}

merge ( int *a, int na, int *b, int nb, int *c )
{
	int i = 0, j = 0, k = 0, t ;

	for( k = 0 ; k < na + nb ; k++ )
	{
		if( i < na && j < nb )
		{
			if( a[i] > b[j] )
	                                     c[k] = b[j++] ;
			else
			    c[k] = a[i++] ;
		}
		else 
		{
			if ( i < na )
		 	     c[k] = a[i++] ;
			else
			     c[k] = b[j++] ;
		}
	}
}

This program sorts integers, strings, and dates using qsort( ). qsort( ) is a standard library function declared in stdlib.h header file. This is the quickest sorting procedure available till date. The following are the parameters in order that are passed to qsort( ):

1. The 0th element of the array containing the strings, numbers or dates.
2. The number of elements in the array.
3. Size in bytes of each element in the array.
4. A user-defined comparison routine that compares two items and returns a value based on the comparison
   

   	
   	
   struct date
   {
   	int dd, mm, yy ;
   };
   main( )
   {
   	int a[]= { 46, 43, 12, 57, 76, 65, 84, 94, 93, 23 } ;
   	char *str[] = { "Small", "Sail", "hell", "Hell", "heaven",
   				"Alpha", "Gamma", "Beta", "System", "Software"
   				  } ;
   
   	struct date d[] = {
   						{ 20,11,99 },
   						{ 30, 3,81 },
   						{ 12, 9,98 },
   						{ 16,10,76 },
   						{  6,11,78 },
   						{  3, 6,80 },
   						{ 21, 6,63 },
   						{ 28,11,82 },
   						{  3,10,51 },
   						{ 23,11,58 }
   					};
   
   	int i ;
   	int fcmp_ints ( int *x, int *y ) ;
   	int fcmp_strings ( char **x, char **y ) ;
   	int fcmp_dates ( struct date *d1, struct date *d2 ) ;
   
   	clrscr() ;
   
   	qsort ( ( int * )a, 10, sizeof ( int ), fcmp_ints ) ;
   	printf ( "The Sorted List is : \n" ) ;
   	for ( i = 0 ; i < 10 ; i++ )
   		printf ( " %d", a[i] ) ;
   
   	qsort ( ( char ** )str, 10, sizeof ( str[0] ), fcmp_strings ) ;
   	printf ( "\nThe Sorted List is : \n" ) ;
   	for ( i = 0 ; i < 10 ; i++ )
   		printf ( " %s", str[i] ) ;
   
   	qsort ( ( struct date *) d, 10, sizeof ( struct date ), fcmp_dates ) ;
   	printf ( "\nThe Sorted List is : \n" ) ;
   		
   	for ( i = 0 ; i < 10 ; i++ )
   		printf ( "\n%d/%d/%d", d[i].dd, d[i].mm, d[i].yy ) ;
   }
   
   fcmp_ints ( int *x, int *y )
   {
   	return ( *x - *y ) ;
   }
   
   fcmp_strings ( char **x, char **y )
   {
   	return ( strcmp ( *x, *y ) ) ;
   }
   
   fcmp_dates ( struct date *d1, struct date *d2 )
   {
   	int x, y ;
   
   	x = ( d1->yy - 1980 ) * 512 + d1->mm * 32 + d1->dd ;
   	y = ( d2->yy - 1980 ) * 512 + d2->mm * 32 + d2->dd ;
   
   	return ( x - y ) ;
   }
   
   

      Heap sort uses a tree structure called a heap i.e. if each node N of heap H has the property as :

      The value at N is greater than or equal to the value at each of the children of N.
Suppose an array A with N element is given.  The heapsort algorithm to sort  A consists of the two following phases :

Phase A : 	Build a heap H out of the elements of A.
		It consists of reading an element and inserting the element in the
		proper place of the array A.
		We insert element into the heap H as follows :
		
		1. First adjoin element at the end of H so that H is still a
		    complete tree, but not necessarily a heap.
		2. Then let element rise to its appropriate place in H so that
		    H is finally a heap.

Phase B : 	Repeatedly delete the root element of H.
		Since the root of H always contains the largest node in H, Phase B
		deletes the elements of A in decreasing order.
		This is accomplished as follows :
			
		1. Assign the root R to some variable.
		2. Replace the deleted node R by the last node L of H so that H
		    is still a complete tree, but not necessarily a heap.
		3.  ( Reheap ) Let L sink to its appropriate place in H so that H
		    is finally a heap.
				
Finally the deleted items are sorted.


main( )
{
	int a[10];
	int i, j, n ;

	/* Inserting the elements into a Heap */
	printf ( "Enter the elements : " ) ;
	
	for ( i = 0 ; i < 10 ; i++ )
	{
		scanf ( "%d", &a[i] ) ;
		insert ( a, i + 1 ) ;
	}

	n = 10 ;
	for ( i = 0 ; i < 10 ; i++ )
	{
		del_heap ( a, a[i], --n ) ;
	}
	for ( i = 0 ; i < 10 ; i++ )
	{
		printf ( " %d", a[i] ) ;
	}
}

insert ( int *a, int pos )
{
	int par, t ;

	par = pos/2 ;
	
	while ( par > 0 )
	{
		if ( a[pos-1] > a[par-1] )
		{
			t = a[pos-1] ;
			a[pos-1] = a[par-1] ;
			a[par-1] = t ;
			pos = par ;
			par /= 2 ;
		}
		else
		{
			pos = par ;
			par /= 2 ;
		}
	}
}

del_heap ( int *a, int x, int pos )
{
	int par = 1, left = 2, right = 3, t ;

	/* Deletion and Insertion at the Last pos */
	t = a[0] ;
	a[0] = a[pos] ;
	a[pos] = t ;

	/* Sinking the Zeroeth Node at its right place */
	pos-- ;
	if ( pos > 1 )
	{
		if ( a[left-1] > a[par-1] )
			sink ( a, pos, par, left, right ) ;
		if ( a[right-1] > a[par-1] )
			sink ( a, pos, par, left, right ) ;
	}
}

sink ( int *a, int pos, int par, int left, int right )
{
	int t ;

	if ( a[left-1] > a[par-1] )
	{
		t = a[left-1] ;
		a[left-1] = a[par-1] ;
		a[par-1] = t ;
	}
	if ( a[right-1] > a[par-1] )
	{
		t = a[right-1] ;
		a[right-1] = a[par-1] ;
		a[par-1] = t ;
	}

	par = left ;
	left *= 2 ;
	right = left + 1 ;

	if ( left > pos || right > pos )
		return ;
	else
		sink ( a, pos, par, left, right ) ;
}

Suppose the list of numbers A[1],A[2],...,A[N] is in memory. The bubble
sort algorithm works as follows :

Pass 1.		Compare A[1] and A[2] and arrange them in the desired order, so
			that A[1] > A[2]. Then compare A[2] and A[3] and arrange them so
			that A[2] > A[3]. Then compare A[3] and A[4] and arrange them so
			that A[3] > A[4].  Continue until we compare A[N-1] with A[N] and
			arrange them so that A[N-1] > A[N].

			Observe that Pass 1 involves N-1 comparisions.  During Pass 1 the
			smallest element is bubbled up to nth position or sinks to the
			nth	position.  When Pass 1 is completed, A[N] will contain the
			largest element.
Pass 2.		Repeat Pass 1 with one less comparision; i.e. now we stop after
			we compare and possible rearrange A[N-2] and A[N-1].
Pass 3.		Repeat Pass 1 with two lesser comparision; i.e. now we stop after
			we compare and possible rearrange A[N-3] and A[N-2].
.
.
.
Pass N-1.	Compare A[1] and A[2] and arrange them so that A[1] < A[2].

After n-1 passes, the list will be sorted in increasing order.

Here is the program for you.

main( )
{
	int a[25], i, j, k, m, t ;

	for ( i = 0 ; i <= 24 ; i++ )
		scanf ( "%d", &a[i] ) ;

	m = 23 ;
	for ( i = 0 ; i <= 23 ; i++ )
	{
		for ( j = 0 ; j <= m ; j++ )
		{
			if ( a[j] > a[j+1] )
			{
				t = a[j] ;
				a[j] = a[j+1] ;
				a[j+1] = t ;
			}
		}
		m-- ;
	}

	for ( i = 0 ; i <= 24 ; i++ )
		printf ( "%d ", a[i] ) ;
}