SORTING TECHNIQUES COMPLEXITY OF SORTING ALGORITHMS by Md Farrukh Asif

 

SORTING TECHNIQUES

COMPLEXITY OF SORTING ALGORITHMS

 

The complexity of the sorting algorithm measures the running time of n items to be sorted. The operations in the sorting algorithm, where A1, A2 ….. A contains the items to be sorted and B is an auxiliary location, which can be generalized as:

 

(a) Comparisons- which tests whether Ai < Aj or test whether
             Ai < B

(b) Interchange- which switches the contents of Ai and Aj or
             of Ai and B

(c) Assignments- which set B = A and then set Aj = B or Aj = Ai

 

Normally, the complexity functions measure only the number of comparisons, since the number of other operations is at most a constant factor of the number of comparisons. 

BUBBLE SORT 

In bubble sort, each element is compared with its adjacent element. If the first element is larger than the second one, then the positions of the elements are interchanged, otherwise it is not changed. Then next element is compared with its adjacent element and the same process is repeated for all the elements in the array until we get a sorted array.

 

Let A be a linear array of n numbers. Sorting of A means rearranging the elements of A so that they are in order. Here we are dealing with ascending order. i.e., A[1] < A[2] < A[3] < ...... A[n].

 

Suppose the list of numbers A[1], A[2], ………… A[n] is an element of array A. The bubble sort algorithm works as follows:

 

Step 1: Compare A[1] and A[2] and arrange them in the (or desired) ascending order, so that A[1] < A[2].that is if A[1] is greater than A[2] then interchange the position of data by swap = A[1]; A[1] = A[2]; A[2] = swap. Then compare A[2] and A[3] and arrange them so that A[2] < A[3]. Continue the process until we compare A[N – 1] with A[N].

 

 

Note: Step1 contains n – 1 comparisons i.e., the largest element is “bubbled up” to the nth position or “sinks” to the nth position. When step 1 is completed A[N] will contain the largest element.

 

Step 2: Repeat step 1 with one less comparisons that is, now stop comparison at A [n – 1] and possibly rearrange A[N – 2] and A[N – 1] and so on.

 

Note: in the first pass, step 2 involves n–2 comparisons and the second largest element will occupy A[n-1]. And in the second pass, step 2 involves n – 3 comparisons and the 3rd largest element will occupy A[n – 2] and so on.

 

Step n – 1: compare A[1]with A[2] and arrange them so that A[1] < A[2]

 

After n – 1 steps, the array will be a sorted array in increasing (or ascending) order.

 

The following figures will depict the various steps (or PASS) involved in the sorting of an array of 5 elements. The elements of an array A to be sorted are: 42, 33, 23, 74, 44

 

FIRST PASS
33 swapped	33	33	33
42	23 swapped	23	23
23	42	42 no swapping	42
74	74	74	44 swapped
44	44	44	74

23 swapped	23	23
33	33 no swapping	33
42	42	42 no swapping
44	44	44
74	74	74
23 no swapping	23
33	33 no swapping
42	42
44	44
74	74

 

23 no swapping

 

33

 

42

 

44

 

74

 

Thus the sorted array is 23, 33, 42, 44, 74.

 

ALGORITHM

 

Let A be a linear array of n numbers. Swap is a temporary variable for swapping (or interchange) the position of the numbers.

 

1. Input n numbers of an array A

 

2. Initialise i = 0 and repeat through step 4 if (i < n)

 

3. Initialize j = 0 and repeat through step 4 if (j < n – i – 1)

 

4. If (A[j] > A[j + 1])

 

(a) Swap = A[j]

 

(b) A[j] = A[j + 1]

 

(c) A[j + 1] = Swap

 

5. Display the sorted numbers of array A

 

6. Exit.

 

========== Program Begins Here ======

//PROGRAM TO IMPLEMENT BUBBLE SORT USING ARRAYS //STATIC MEMORY ALLOCATION //CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

#define MAX 20

void main()

{

int arr[MAX],i,j,k,temp,n,xchanges;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

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

{

printf (“E\nnter element %d : ”,i+1);

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

}

printf (“\nUnsorted list is :\n”);

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

printf (“%d ”, arr[i]);

printf (“\n”);

/* Bubble sort*/

for (i = 0; i < n–1 ; i++)

{

xchanges=0;

for (j = 0; j <n–1–i; j++)

{

if (arr[j] > arr[j+1])

{

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

xchanges++;

}/*End of if*/

}/*End of inner for loop*/

if (xchanges==0) /*If list is sorted*/

break;

printf(“\nAfter Pass %d elements are :  ”,i+1);

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

printf(“%d ”, arr[k]);

printf(“\n”);

}/*End of outer for loop*/

printf(“\nSorted list is :\n”);

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

printf(“%d ”, arr[i]);

getch();

}/*End of main()*/

  

============== PROGRAM Begins Here =======

//PROGRAM TO IMPLEMENT BUBBLE SORT

//USING DYNAMIC MEMORY ALLOCATION

//CODED AND COMPILED IN TURBO C

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

//this function will bubble sort the input

void bubblesort(int *a,int n)

{

int i,j,k,temp;

for(i=1;i < n;i++)

for(j=0;j < n–1;j++)

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

{

temp=a[j];

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

a[j+1]=temp;

}

}

void main()

{

int *a,n,*l,*temp;

clrscr();

printf (“\nEnter the number of elements :”);

scanf (“%d”,&n);

//allocating the array of memory dynamically

a=((int*)malloc(n*sizeof (int)));

temp=a;//storing the memnory address

l=a+n;

printf (“\nEnter the elements\n”);

while(a < l)

{

scanf (“%d”,a);

a++;

}

bubblesort(temp,n);

printf (“\nSorted array is : ”);

a=temp;

while(a < l)

{

printf (“  %d”,*a);

a++;

}

getch();

}

 TIME COMPLEXITY 

The time complexity for bubble sort is calculated in terms of the number of compari-sons f(n) (or of number of loops); here two loops (outer loop and inner loop) iterates (or repeated) the comparisons. The number of times the outer loop iterates is determined by the number of elements in the list which is asked to sort (say it is n). The inner loop is iterated one less than the number of elements in the list (i.e., n-1 times) and is reiterated upon every iteration of the outer loop

f (n) = (n – 1) + (n – 2) + .+ 2+1

          

 = n(n – 1) = O(n2).

 

BEST CASE 

In this case you are asked to sort a sorted array by bubble sort algorithm. The inner loop will iterate with the ‘if’ condition evaluating time, that is the swap procedure is never called. In best case outer loop will terminate after one iteration, i.e., it involves performing one pass, which requires n–1 comparisons

 

f  (n) = O(n)

 

WORST CASE 

In this case the array will be an inverted list (i.e., 5, 4, 3, 2, 1, 0). Here to move first element to the end of the array, n–1 times the swapping procedure is to be called. Every other element in the list will also move one location towards the start or end of the loop on every iteration. Thus n times the outer loop will iterate and n (n-1) times the inner loop will iterate to sort an inverted array

 

f(n) = (n(n – 1))/2 = O(n2)

 

AVERAGE CASE 

The average case is more difficult to analyze than the other cases. In this case, the input data(s) are randomly placed in the list. The exact time complexity can be calculated only if we know the number of iterations, comparisons, and swapping. In general, the complexity of average case is:

 

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

 

 SELECTION SORT

 

The selection sort algorithm finds the smallest element of the array and interchanges it with the element in the first position of the array. Then it finds the second smallest element from the remaining elements in the array and places it in the second position of the array and so on.

             Let A be a linear array of ‘n’ numbers, A [1], A [2], A [3],...... A [n].

 

Step 1: Find the smallest element in the array of n numbers A[1], A[2], ...... A[n]. Let LOC is the location of the smallest number in the array. Then interchange A[LOC] and A[1] by swap = A[LOC]; A[LOC] = A[1]; A[1] = Swap.

 

Step 2: Find the second smallest number in the sub list of n – 1 elements A [2] A [3]  A [n – 1] (first element is already sorted). Now we concentrate on the rest of the elements in the array. Again A [LOC] is the smallest element in the remaining array and LOC the corresponding location then interchange A [LOC] and A [2].Now A [1] and A [2] is sorted, since A [1] less than or equal to A [2].

 

Step 3: Repeat the process by reducing one element each from the array

 

Step n – 1: Find the n – 1 smallest number in the sub array of 2 elements (i.e., A(n– 1), A (n)). Consider A [LOC] is the smallest element and LOC is its corresponding position. Then interchange A [LOC] and
A(n – 1).
Now the array A [1], A [2], A [3], A [4],………..A [n] will be a sorted array.

 

The following figure is generated during the iterations of the algorithm to sort 5 numbers 42, 33, 23, 74, 44 :

ALGORITHM

 

Let A be a linear array of n numbers A [1], A [2], A [3], ……… A [k], A [k+1], …….. A [n]. Swap

 

be a temporary variable for swapping (or interchanging) the position of the numbers. Min is the variable to store smallest number and Loc is the location of the smallest element.

 

1. Input n numbers of an array A

 

2. Initialize i = 0 and repeat through step5 if (i < n – 1) (a) min = a[i]

 

(b) loc = i

 

3. Initialize j = i + 1 and repeat through step 4 if (j < n – 1)

 

4. if (a[j] < min)

 

(a) min = a[j]

 

(b) loc = j

 

5. if (loc ! = i)

 

(a) swap = a[i]

 

(b) a[i] = a[loc]

 

(c) a[loc] = swap

 

6. display “the sorted numbers of array A”

 

7. Exit

 

 

========= PROGRAM Begins Here =========

//PROGRAM TO IMPLEMENT SELECTION SORT

//USING STATIC MEMORY ALLOCATION, THAT IS //USING ARRAYS

//CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

#define MAX 20

void main()

{

int arr[MAX], i,j,k,n,temp,smallest;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”, & n);

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

{

printf (“\nEnter element %d : ”,i+1);

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

}

printf (“\nUnsorted list is : \n”);

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

printf (“%d ”, arr[i]);

printf (“\n”);

/*Selection sort*/

for (i = 0; i < n – 1 ; i++)

{

/*Find the smallest element*/

smallest = i;

for(k = i + 1; k < n ; k++)

{

if (arr[smallest] > arr[k])

smallest = k ;

}

if ( i != smallest )

{

temp = arr [i];

arr[i] = arr[smallest];

arr[smallest] = temp ;

}

printf (“\nAfter Pass %d elements are :  ”,i+1);

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

printf (“%d ”, arr[ j]);

printf (“\n”);

}/*End of for*/

printf (“\nSorted list is : \n”);

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

printf (“%d ”, arr[i]);

getch();

}/*End of main()*/

  

======== PROGRAM ========

//PROGRAM TO IMPLEMENT SELECTION SORT

//USING DYNAMIC MEMORY ALLOCATION

//CODED AND COMPILED USING TURBO C

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

//this function will sort the input elements using selection sort

void selectionsort(int *a,int n)

{

int i,j,temp;

for(i=0;i< n–1;i++)

for(j=i+1;j < n;j++)

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

{

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

void main()

{

int *a,n,*l,*temp;

clrscr();

printf (“\nEnter the number of elements\n”);

scanf (“%d”,&n);

//dynamically allocate the memory array block

a=((int*)malloc(n*sizeof (int)));

temp=a;

l=a+n;

printf (“\nEnter the elements\n”);

while(a < l)

{

scanf (“%d”,a);

a++;

}

//calling the selection sort fucntion

selectionsort(temp,n);

printf (“\nSorted array :  ”);

a=temp;

while(a < l)

{

printf (“ %d”,*a);

a++;

}

getch();

}

 

 

TIME COMPLEXITY

 

Time complexity of a selection sort is calculated in terms of the number of compari-sons f (n). In the first pass it makes n – 1 comparisons; the second pass makes n – 2

 

comparisons and so on. The outer for loop iterates for (n - 1) times. But the inner loop iterates for n*(n – 1) times to complete the sorting.

 

f (n) = (n – 1) + (n – 2) + ......

+2+1

 

= (n(n – 1))/2

 

= O(n₂)

 

Readers can go through the algorithm and analyse it for different types of input to find their (efficiency) Time complexity for best, worst and average case. That is in best case how the algorithm is performed for sorted arrays as input.

 

In worst case we can analyse how the algorithm is performed for reverse sorted array as input. Average case is where we input general (mixed sorted) input to the algo-rithm. Following table will summarise the efficiency of algorithm in different case :

Best case	Worst case	Average case
n – 1 = O(n)	n(n − 1) = O(n2)	n(n − 1)= O(n)
	2	2

 

 

INSERTION SORT 

The insertion sort algorithm sorts a set of values by inserting values into an existing sorted file. Compare the second element with the first, if the first element is greater than the second, place it before the first one. Otherwise, the place is just after the first one. Compare the third value with second. If the third value is greater than the second value then place it just after the second. Otherwise, place the second value to the third place. And compare third value with the first value. If the third value is greater than the first value place the third value to second place, otherwise place the first value to second place. And place the third value to first place and so on.

 

Let A be a linear array of n numbers A [1], A [2], A [3], ...... A[n]. The algorithm scan the array A from A [1] to A [n], by inserting each element A[k], into the proper position of the previously sorted sub list. A [1], A [2], A [3], ...... A [k – 1]

 

 Step 1: As the single element A [1] by itself is sorted array.

  

Step 2: A [2] is inserted either before or after A [1] by comparing it so that A[1], A[2] is sorted array.

 

Step 3: A [3] is inserted into the proper place in A [1], A [2], that is A [3] will be compared with A [1] and A [2] and placed before A [1], between A [1] and A [2], or after A [2] so that A [1], A [2], A [3] is a sorted array.

 

Step 4: A [4] is inserted in to a proper place in A [1], A [2], A [3] by comparing it; so that A [1], A [2], A [3], A [4] is a sorted array.

  

Step 5: Repeat the process by inserting the element in the proper    
             place in array.

  

Step n : A [n] is inserted into its proper place in an array A [1], A [2],
              A [3], ...... A [n –1] so that A [1], A [2], A [3], ...... ,A [n] is a
              sorted array.

 

 

To illustrate the insertion sort methods, consider the following array with five elements 42, 33, 23, 74, 44 :

 

ALGORITHM

 

Let A be a linear array of n numbers A [1], A [2], A [3], ...... ,A [n]......Swap is a temporary variable to interchange the two values. Pos is the control variable to hold the position of each pass.

             1. Input an array A of n numbers

2. Initialize i = 1 and repeat through steps 4 by incrementing i by one.

(a) If (i < = n – 1)

 

(b) Swap A[I],

(c) Pos = i – 1

 

             3. Repeat the step 3 if (Swap < A[Pos] and (Pos >= 0))

 

(a) A [Pos+1] = A [Pos]

 

(b) Pos = Pos-1

4. A [Pos +1] = Swap

 

5. Exit

  

=== PROGRAM Begins Here ===

//PROGRAM TO IMPLEMENT          //INSERTION SORT USING ARRAYS

//CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

#define MAX 20

void main()

{

int arr[MAX],i,j,k,n;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

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

{

printf (“\nEnter element %d : ”,i+1);

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

}

printf (“\nUnsorted list is :\n”);

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

printf (“%d ”, arr[i]);

printf (“\n”);

/*Insertion sort*/

for(j=1;j < n;j++)

{

k=arr[j]; /*k is to be inserted at proper place*/

for(i=j–1;i>=0 && k<arr[i];i--)

arr[i+1]=arr[i];

arr[i+1]=k;

printf (“\nPass %d, Element inserted in proper place: %d\n”,j,k); for (i = 0; i < n; i++)

printf (“%d ”, arr[i]);

printf (“\n”);

}

printf (“\nSorted list is :\n”);

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

printf (“%d ”, arr[i]);

getch();

}/*End of main()*/

 

TIME COMPLEXITY 

In the insertion sort algorithm (n – 1) times the loop will execute for comparisons and interchanging the numbers. The inner while loop iterates a maximum of ((n – 1) × (n – 1))/2 times to computing the sorting.

  WORST CASE 

The worst case occurs when the array A is in reverse order and the inner while loop must use the maximum number (n – 1) of comparisons. Hence

 

f(n) = (n – 1) + ....... +2 +1

 

= (n (n – 1))/2

 

= O(n²).

 

AVERAGE CASE 

In the average case, there will be approximately (n – 1)/2 comparisons in the inner while loop. Hence the average case

 

f (n) = (n – 1)/2 + ......2/2 +1/2

 

= n (n – 1)/4

 

= O(n²).

 

BEST CASE 

The best case occurs when the array A is in sorted order and the outer for loop will iterate for (n – 1) times. And the inner while loop will not execute because the given array is a sorted array

 

i.e.,                 f (n) = O(n).

 

 

SHELL SORT 

Shell Sort is introduced to improve the efficiency of simple insertion sort. Shell Sort is also called diminishing increment sort. In this method, sub-arrays, containing the kth element of the original array, are sorted.

 

Let A be a linear array of n numbers A [1], A [2], A [3], ...... A [n].

 

Step 1: The array is divided into k sub-arrays consisting of every kth element. Say k = 5, then five sub-array, each containing one fifth of the elements of the original array.

 

 

Sub array 1 →	A[0]	A[5]	A[10]
Sub array 2 →	A[1]	A[6]	A[11]
Sub array 3 →	A[2]	A[7]	A[12]
Sub array 4 →	A[3]	A[8]	A[13]
Sub array 5 →	A[4]	A[9]	A[14]

 

 

 Note :

The ith element of the jth sub array is located as A [(i–1) × k+j–1]

 

Step 2: After the first k subarray is sorted (usually by insertion sort) , a new smaller value of k is chosen and the array is again partitioned into a new set of subarrays.

 

Step 3: And the process is repeated with an even smaller value of k, so that A [1], A [2], A [3], ....... A [n] is sorted.

 

To illustrate the shell sort, consider the following array with 7 elements 42, 33, 23, 74, 44, 67, 49 and the sequence K = 4, 2, 1 is chosen.

 

23,

33,

42,

44,

49,

67,

74

 

ALGORITHM 

Let A be a linear array of n elements, A [1], A [2], A [3], ...... A[n] and Incr be an array

 

of a sequence of span to be incremented in each pass. X is the number of elements in the array Incr. Span is to store the span of the array from the array Incr.

 

1. Input n numbers of an array A

 

2. Initialise i = 0 and repeat through step 6 if (i < x)

 

3. Span = Incr[i]

 

4. Initialise j = span and repeat through step 6 if ( j < n) (a) Temp = A [ j ]

5. Initialise k = j-span and repeat through step 5 if (k > = 0) and (temp < A [k ]) (a) A [k + span] = A [k]

6. A [k + span] = temp

 

7. Exit

    

=== PROGRAM Begins Here ===

//PROGRAM TO IMPLEMENT

//SHELL SORT USING ARRAYS

//CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

#define MAX 20

void main()

{

int arr[MAX], i,j,k,n,incr;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

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

{

printf (“\nEnter element %d : ”,i+1);

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

}

printf (“\nUnsorted list is :\n”);

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

printf (“%d ”, arr[i]);

printf (“\nEnter maximum increment (odd value) : ”);

scanf (“%d”,&incr);

/*Shell sort algorithm is applied*/

while(incr>=1)

{

for (j=incr;j<n;j++)

{

k=arr[ j];

for(i = j–incr; i > = 0 && k < arr[i]; i = i–incr)

arr[i+incr]=arr[i];

arr[i+incr]=k;

}

printf (“\nIncrement=%d \n”,incr);

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

printf(“%d ”, arr[i]);

printf (“\n”);

incr=incr–2; /*Decrease the increment*/

}/*End of while*/

printf (“\nSorted list is :\n”);

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

printf (“%d ”, arr[i]);

getch();

}/*End of main()*/

 TIME COMPLEXITY 

The detailed efficiency analysis of the shell sort is mathematically involved and beyond the scope of this book. The time complexity depends on the number of elements in the array increment (i.e., number of spans) and on their actual values. One requirement is that the elements of increments should be relatively prime (i.e., no common divisor other than 1). This guarantees that after successive iteration of the sub arrays, the entire array is almost sorted when the span = 1 (i.e., in the last iteration). If an appropriate sequence of increments is classified, then the order of the shell sort is

 

f (n) = O(n (log n)²)

 

Continued…..