2.1 Linear search Binary search

UNIT- 2

Searching and Sorting Techniques

2.1 Linear search, Binary search

Searching

Searching is the process of finding some particular element in the list. If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

There are two popular search methods that are widely used in order to search some item into the list. However, choice of the algorithm depends upon the arrangement of the list.

Linear Search

Binary Search

Linear Search

Linear search is the simplest search algorithm and often called sequential search. In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match found then location of the item is returned otherwise the algorithm return NULL.

Linear search is mostly used to search an unordered list in which the items are not sorted. The algorithm of linear search is given as follows.

Algorithm

LINEAR_SEARCH(A, N, VAL)

Step 1: [INITIALIZE] SET POS = -1

Step 2: [INITIALIZE] SET I = 1

Step 3: Repeat Step 4 while I<=N

Step 4: IF A[I] = VAL
SET POS = I
PRINT POS
Go to Step 6
[END OF IF]
SET I = I + 1
[END OF LOOP]

Step 5: IF POS = -1
PRINT " VALUE IS NOT PRESENTIN THE ARRAY "
[END OF IF]

Step 6: EXIT

Complexity of algorithm

Complexity	Best Case	Average Case	Worst Case
Time	O(1)	O(n)	O(n)
Space			O(1)

C Program

#include<stdio.h>

void main ()

{

int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};

int item, i,flag;

printf("\nEnter Item which is to be searched\n");

scanf("%d",&item);

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

{

if(a[i] == item)

{

flag = i+1;

break;

}

else

flag = 0;

}

if(flag != 0)

{

printf("\nItem found at location %d\n",flag);

}

else

{

printf("\nItem not found\n");

}

Output:

Enter Item which is to be searched

Item not found

Enter Item which is to be searched

Item found at location 2

Java Program

import java.util.Scanner;

public class Leniear_Search {

public static void main(String[] args) {

int[] arr = {10, 23, 15, 8, 4, 3, 25, 30, 34, 2, 19};

int item,flag=0;

Scanner sc = new Scanner(System.in);

System.out.println("Enter Item ?");

item = sc.nextInt();

for(int i = 0; i<10; i++)

{

if(arr[i]==item)

{

flag = i+1;

break;

}

else

flag = 0;

}

if(flag != 0)

{

System.out.println("Item found at location" + flag);

}

else

System.out.println("Item not found");

}

Output:

Enter Item ?

Item found at location 2

Enter Item ?

Item not found

C# Program

using System;

public class LinearSearch

{

public static void Main()

{

int item, flag = 0;

int[] a= {10, 23, 5, 90, 89, 34, 12, 34, 1, 78};

Console.WriteLine("Enter the item value");

item = Convert.ToInt32(Console.ReadLine());

for(int i=0;i<10;i++)

{

if(item == a[i])

{

flag = i+1;

break;

}

else

flag = 0;

}

if(flag != 0 )

{

Console.WriteLine("Item Found at Location " + flag);

}

else

Console.WriteLine("Item Not Found");

}

Output:

Enter the item value

Item Found at Location 10

Enter the item value

Item not found

Python Program

arr = [10,2,3,4,23,5,21,45,90,100];

item = int(input("Enter the item which you want to search "));

for i in range (0,len(arr)):

if arr[i] == item:

flag = i+1;

break;

else:

flag = 0;

if flag != 0:

print("Item found at location %d" % (flag));

else :

print("Item not found");

Output:

Enter the item which you want to search 2

Item found at location 2

Enter the item which you want to search 101

Item not found

Binary Search

Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an element into some list by using binary search technique, we must ensure that the list is sorted.

Binary search follows divide and conquer approach in which, the list is divided into two halves and the item is compared with the middle element of the list. If the match is found then, the location of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.

Binary search algorithm is given below.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

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

Step 2: Repeat Steps 3 and 4 while BEG <=END

Step 3: SET MID = (BEG + END)/2

Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]

Step 5: IF POS = -1
PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
[END OF IF]

Step 6: EXIT

Complexity

SN	Performance	Complexity
1	Worst case	O(log n)
2	Best case	O(1)
3	Average Case	O(log n)
4	Worst case space complexity	O(1)

Example

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.

In 1ststep :

BEG = 0

END = 8ron

MID = 4

a[mid] = a[4] = 13 < 23, therefore

in Second step:

Beg = mid +1 = 5

End = 8

mid = 13/2 = 6

a[mid] = a[6] = 20 < 23, therefore;

in third step:

beg = mid + 1 = 7

End = 8

mid = 15/2 = 7

a[mid] = a[7]

a[7] = 23 = item;

therefore, set location = mid;

The location of the item will be 7.

Binary Search

Binary Search Program using Recursion

C program

#include<stdio.h>

int binarySearch(int[], int, int, int);

void main ()

{

int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};

int item, location=-1;

printf("Enter the item which you want to search ");

scanf("%d",&item);

location = binarySearch(arr, 0, 9, item);

if(location != -1)

{

printf("Item found at location %d",location);

}

else

{

printf("Item not found");

}

int binarySearch(int a[], int beg, int end, int item)

{

int mid;

if(end >= beg)

{

mid = (beg + end)/2;

if(a[mid] == item)

{

return mid+1;

}

else if(a[mid] < item)

{

return binarySearch(a,mid+1,end,item);

}

else

{

return binarySearch(a,beg,mid-1,item);

}

return -1;

}

Output:

Enter the item which you want to search

Item found at location 2

Java

import java.util.*;

public class BinarySearch {

public static void main(String[] args) {

int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};

int item, location = -1;

System.out.println("Enter the item which you want to search");

Scanner sc = new Scanner(System.in);

item = sc.nextInt();

location = binarySearch(arr,0,9,item);

if(location != -1)

System.out.println("the location of the item is "+location);

else

System.out.println("Item not found");

}

public static int binarySearch(int[] a, int beg, int end, int item)

{

int mid;

if(end >= beg)

{

mid = (beg + end)/2;

if(a[mid] == item)

{

return mid+1;

}

else if(a[mid] < item)

{

return binarySearch(a,mid+1,end,item);

}

else

{

return binarySearch(a,beg,mid-1,item);

}

return -1;

}

Output:

Enter the item which you want to search

the location of the item is 5

using System;

public class LinearSearch

{

public static void Main()

{

int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};

int location=-1;

Console.WriteLine("Enter the item which you want to search ");

int item = Convert.ToInt32(Console.ReadLine());

location = binarySearch(arr, 0, 9, item);

if(location != -1)

{

Console.WriteLine("Item found at location "+ location);

}

else

{

Console.WriteLine("Item not found");

}

public static int binarySearch(int[] a, int beg, int end, int item)

{

int mid;

if(end >= beg)

{

mid = (beg + end)/2;

if(a[mid] == item)

{

return mid+1;

}

else if(a[mid] < item)

{

return binarySearch(a,mid+1,end,item);

}

else

{

return binarySearch(a,beg,mid-1,item);

}

return -1;

}

Output:

Enter the item which you want to search

Item found at location 3

Python

def binarySearch(arr,beg,end,item):

if end >= beg:

mid = int((beg+end)/2)

if arr[mid] == item :

return mid+1

elif arr[mid] < item :

return binarySearch(arr,mid+1,end,item)

else:

return binarySearch(arr,beg,mid-1,item)

return -1

arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];

item = int(input("Enter the item which you want to search ?"))

location = -1;

location = binarySearch(arr,0,9,item);

if location != -1:

print("Item found at location %d" %(location))

else:

print("Item not found")

Output:

Enter the item which you want to search ?

Item found at location 9

Enter the item which you want to search ?

101

Item not found

Binary Search function using Iteration

int binarySearch(int a[], int beg, int end, int item)

{

int mid;

while(end >= beg)

{

mid = (beg + end)/2;

if(a[mid] == item)

{

return mid+1;

}

else if(a[mid] < item)

{

beg = mid + 1;

}

else

{

end = mid - 1;

}

return -1;

}

2.2 Hashing – Definition, hash functions, Collision

Hashing

In data structures,

Hashing is a well-known technique to search any particular element among several elements.

It minimizes the number of comparisons while performing the search.

Advantage-

Unlike other searching techniques,

Hashing is extremely efficient.

The time taken by it to perform the search does not depend upon the total number of elements.

It completes the search with constant time complexity O(1).

Hashing Mechanism-

In hashing,

An array data structure called as Hash table is used to store the data items.

Based on the hash key value, data items are inserted into the hash table.

Hash Key Value-

Hash key value is a special value that serves as an index for a data item.

It indicates where the data item should be be stored in the hash table.

Hash key value is generated using a hash function.

Hash Function-

Hash function is a function that maps any big number or string to a small integer value.

Hash function takes the data item as an input and returns a small integer value as an output.

The small integer value is called as a hash value.

Hash value of the data item is then used as an index for storing it into the hash table.

Types of Hash Functions-

There are various types of hash functions available such as-

Mid Square Hash Function

Division Hash Function

Folding Hash Function etc

It depends on the user which hash function he wants to use.

Properties of Hash Function-

The properties of a good hash function are-

It is efficiently computable.

It minimizes the number of collisions.

It distributes the keys uniformly over the table.

Collision in Hashing-

In hashing,

Hash function is used to compute the hash value for a key.

Hash value is then used as an index to store the key in the hash table.

Hash function may return the same hash value for two or more keys.

When the hash value of a key maps to an already occupied bucket of the hash table,

it is called as a Collision.

Collision Resolution Techniques-

Collision Resolution Techniques are the techniques used for resolving or handling the collision.

Collision resolution techniques are classified as-

Separate Chaining

Open Addressing

Separate Chaining-

To handle the collision,

This technique creates a linked list to the slot for which collision occurs.

The new key is then inserted in the linked list.

These linked lists to the slots appear like chains.

That is why this technique is called as separate chaining.

Time Complexity-

For Searching-

In worst case, all the keys might map to the same bucket of the hash table.

In such a case, all the keys will be present in a single linked list.

Sequential search will have to be performed on the linked list to perform the search.

So, time taken for searching in worst case is O(n).

For Deletion-

In worst case, the key might have to be searched first and then deleted.

In worst case, time taken for searching is O(n).

So, time taken for deletion in worst case is O(n).

Load Factor (α)-

Load factor (α) is defined as-

If Load factor (α) = constant, then time complexity of Insert, Search, Delete = Θ(1)

PRACTICE PROBLEM BASED ON SEPARATE CHAINING-

Problem-

Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-

50, 700, 76, 85, 92, 73 and 101

Use separate chaining technique for collision resolution.

Solution-

The given sequence of keys will be inserted in the hash table as-

Step-01:

Draw an empty hash table.

For the given hash function, the possible range of hash values is [0, 6].

So, draw an empty hash table consisting of 7 buckets as-

Step-02:

Insert the given keys in the hash table one by one.

The first key to be inserted in the hash table = 50.

Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.

So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:

The next key to be inserted in the hash table = 700.

Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.

So, key 700 will be inserted in bucket-0 of the hash table as-

Step-04:

The next key to be inserted in the hash table = 76.

Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.

So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:

The next key to be inserted in the hash table = 85.

Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.

Since bucket-1 is already occupied, so collision occurs.

Separate chaining handles the collision by creating a linked list to bucket-1.

So, key 85 will be inserted in bucket-1 of the hash table as-

Step-06:

The next key to be inserted in the hash table = 92.

Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.

Since bucket-1 is already occupied, so collision occurs.

Separate chaining handles the collision by creating a linked list to bucket-1.

So, key 92 will be inserted in bucket-1 of the hash table as-

Step-07:

The next key to be inserted in the hash table = 73.

Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.

So, key 73 will be inserted in bucket-3 of the hash table as-

Step-08:

The next key to be inserted in the hash table = 101.

Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.

Since bucket-3 is already occupied, so collision occurs.

Separate chaining handles the collision by creating a linked list to bucket-3.

So, key 101 will be inserted in bucket-3 of the hash table as-

2.3 Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort, Radix sort

Bubble Sort

In Bubble sort, each element of the array is compared with its adjacent element. The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting. Consider an array A of n elements whose elements are to be sorted by using Bubble sort. The algorithm processes like following.

In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2], A[2] is compared with A[3] and so on. At the end of pass 1, the largest element of the list is placed at the highest index of the list.

In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of Pass 2 the second largest element of the list is placed at the second highest index of the list.

In pass n-1, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of this pass. The smallest element of the list is placed at the first index of the list.

Algorithm:

Step 1: Repeat Step 2 For i = 0 to N-1

Step 2: Repeat For J = i + 1 to N - I

Step 3: IF A[J] > A[i]
SWAP A[J] and A[i]
[END OF INNER LOOP]
[END OF OUTER LOOP

Step 4: EXIT

Complexity

Scenario	Complexity
Space	O(1)
Worst case running time	O(n2)
Average case running time	O(n)
Best case running time	O(n2)

C Program

#include<stdio.h>

void main ()

{

int i, j,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

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

{

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

{

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

{

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

printf("Printing Sorted Element List ...\n");

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

{

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

}

Output:

Printing Sorted Element List . . .

101

C++ Program

#include<iostream>

using namespace std;

int main ()

{

int i, j,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

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

{

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

{

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

{

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

cout <<"Printing Sorted Element List ...\n";

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

{

cout <<a[i]<<"\n";

}

return 0;

}

Output:

Printing Sorted Element List ...

101

Java Program

public class BubbleSort {

public static void main(String[] args) {

int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

for(int i=0;i<10;i++)

{

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

{

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

{

int temp = a[i];

a[i]=a[j];

a[j] = temp;

}

System.out.println("Printing Sorted List ...");

for(int i=0;i<10;i++)

{

System.out.println(a[i]);

}

Output:

Printing Sorted List . . .

101

C# Program

using System;

public class Program

{

public static void Main()

{

int i, j,temp;

int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

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

{

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

{

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

{

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

Console.WriteLine("Printing Sorted Element List ...\n");

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

{

Console.WriteLine(a[i]);

}

Output:

Printing Sorted Element List . . .

101

Python Program

a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]

for i in range(0,len(a)):

for j in range(i+1,len(a)):

if a[j]<a[i]:

temp = a[j]

a[j]=a[i]

a[i]=temp

print("Printing Sorted Element List...")

for i in a:

print(i)

Output:

Printing Sorted Element List . . .

101

Rust Program

fn main()

{

let mut temp;

let mut a: [i32; 10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];

for i in 0..10

{

for j in (i+1)..10

{

if a[j] < a[i]

{

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

println!("Printing Sorted Element List ...\n");

for i in &a

{

println!("{} ",i);

}

Output:

Printing Sorted Element List . . .

101

JavaScript Program

<html>

<head>

<title>

Bubble Sort

</title>

</head>

<body>

var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];

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

{

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

{

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

{

temp = a[i];

a[i]=a[j];

a[j] = temp;

}

txt = "<br>";

document.writeln("Printing Sorted Element List ..."+txt);

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

{

document.writeln(a[i]);

document.writeln(txt);

}

</script>

</body>

</html>

Output:

Printing Sorted Element List ...

101

PHP Program

<html>

<head>

<title>Bubble Sort</title>

</head>

<body>

<?php

$a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);

for($i=0;$i<10;$i++)

{

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

{

if($a[$i]<$a[$j])

{

$temp = $a[$i];

$a[$i]=$a[$j];

$a[$j] = $temp;

}

echo "Printing Sorted Element List ...\n";

for($i=0;$i<10;$i++)

{

echo $a[$i];

echo "\n";

}

</body>

</html>

Output:

Printing Sorted Element List ...

101

Selection Sort

In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted to its appropriate position into the array.

First, find the smallest element of the array and place it on the first position. Then, find the second smallest element of the array and place it on the second position. The process continues until we get the sorted array.

The array with n elements is sorted by using n-1 pass of selection sort algorithm.

In 1st pass, smallest element of the array is to be found along with its index pos. then, swap A[0] and A[pos]. Thus A[0] is sorted, we now have n -1 elements which are to be sorted.

In 2nd pas, position pos of the smallest element present in the sub-array A[n-1] is found. Then, swap, A[1] and A[pos]. Thus A[0] and A[1] are sorted, we now left with n-2 unsorted elements.

In n-1th pass, position pos of the smaller element between A[n-1] and A[n-2] is to be found. Then, swap, A[pos] and A[n-1].

Therefore, by following the above explained process, the elements A[0], A[1], A[2],...., A[n-1] are sorted.

Example

Consider the following array with 6 elements. Sort the elements of the array by using selection sort.

A = {10, 2, 3, 90, 43, 56}.

Pass	Pos	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
1	1	2	10	3	90	43	56
2	2	2	3	10	90	43	56
3	2	2	3	10	90	43	56
4	4	2	3	10	43	90	56
5	5	2	3	10	43	56	90

Sorted A = {2, 3, 10, 43, 56, 90}

Complexity

Complexity	Best Case	Average Case	Worst Case
Time	Ω(n)	θ(n2)	o(n2)
Space			o(1)

Algorithm

SELECTION SORT(ARR, N)

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

Step 2: CALL SMALLEST(ARR, K, N, POS)

Step 3: SWAP A[K] with ARR[POS]
[END OF LOOP]

Step 4: EXIT

SMALLEST (ARR, K, N, POS)

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

Step 2: [INITIALIZE] SET POS = K

Step 3: Repeat for J = K+1 to N -1
IF SMALL > ARR[J]
SET SMALL = ARR[J]
SET POS = J
[END OF IF]
[END OF LOOP]

Step 4: RETURN POS

C Program

#include<stdio.h>

int smallest(int[],int,int);

void main ()

{

int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

int i,j,k,pos,temp;

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

{

pos = smallest(a,10,i);

temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

printf("\nprinting sorted elements...\n");

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

{

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

}

int smallest(int a[], int n, int i)

{

int small,pos,j;

small = a[i];

pos = i;

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

{

if(a[j]<small)

{

small = a[j];

pos=j;

}

return pos;

}

Output:

printing sorted elements...

101

C++ Program

#include<iostream>

using namespace std;

int smallest(int[],int,int);

int main ()

{

int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

int i,j,k,pos,temp;

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

{

pos = smallest(a,10,i);

temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

cout<<"\n printing sorted elements...\n";

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

{

cout<<a[i]<<"\n";

}

return 0;

}

int smallest(int a[], int n, int i)

{

int small,pos,j;

small = a[i];

pos = i;

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

{

if(a[j]<small)

{

small = a[j];

pos=j;

}

return pos;

}

Output:

printing sorted elements...

101

Java Program

public class SelectionSort {

public static void main(String[] args) {

int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

int i,j,k,pos,temp;

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

{

pos = smallest(a,10,i);

temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

System.out.println("\nprinting sorted elements...\n");

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

{

System.out.println(a[i]);

}

public static int smallest(int a[], int n, int i)

{

int small,pos,j;

small = a[i];

pos = i;

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

{

if(a[j]<small)

{

small = a[j];

pos=j;

}

return pos;

}

Output:

printing sorted elements...

101

C# Program

using System;

public class Program

{

public void Main() {

int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

int i,pos,temp;

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

{

pos = smallest(a,10,i);

temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

Console.WriteLine("\nprinting sorted elements...\n");

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

{

Console.WriteLine(a[i]);

}

public static int smallest(int[] a, int n, int i)

{

int small,pos,j;

small = a[i];

pos = i;

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

{

if(a[j]<small)

{

small = a[j];

pos=j;

}

return pos;

}

Output:

printing sorted elements...

101

Python Program

def smallest(a,i):

small = a[i]

pos=i

for j in range(i+1,10):

if a[j] < small:

small = a[j]

pos = j

return pos

a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]

for i in range(0,10):

pos = smallest(a,i)

temp = a[i]

a[i]=a[pos]

a[pos]=temp

print("printing sorted elements...")

for i in a:

print(i)

Output:

printing sorted elements...

101

Rust Program

fn main ()

{

let mut a: [i32;10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];

for i in 0..10

{

let mut small = a[i];

let mut pos = i;

for j in (i+1)..10

{

if a[j]<small

{

small = a[j];

pos=j;

}

let mut temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

println!("\nprinting sorted elements...\n");

for i in &a

{

println!("{}",i);

}

Output:

printing sorted elements...

101

JavaScript Program

<html>

<head>

<title>

Selection Sort

</title>

</head>

<body>

function smallest(a, n, i)

{

var small = a[i];

var pos = i;

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

{

if(a[j]<small)

{

small = a[j];

pos=j;

}

return pos;

}

var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];

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

{

pos = smallest(a,10,i);

temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

document.writeln("printing sorted elements ...\n"+"<br>");

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

{

document.writeln(a[i]+"<br>");

}

</script>

</body>

</html>

Output:

printing sorted elements ...

101

PHP Program

<html>

<head>

<title>Selection sort</title>

</head>

<body>

<?php

function smallest($a, $n, $i)

{

$small = $a[$i];

$pos = $i;

for($j=$i+1;$j<10;$j++)

{

if($a[$j]<$small)

{

$small = $a[$j];

$pos=$j;

}

return $pos;

}

$a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);

for($i=0;$i<10;$i++)

{

$pos = smallest($a,10,$i);

$temp = $a[$i];

$a[$i]=$a[$pos];

$a[$pos] = $temp;

}

echo "printing sorted elements ...\n";

for($i=0;$i<10;$i++)

{

echo $a[$i];

echo "\n";

}

</body>

</html>

Output:

printing sorted elements ...

101

Insertion Sort

Insertion sort is the simple sorting algorithm which is commonly used in the daily lives while ordering a deck of cards. In this algorithm, we insert each element onto its proper place in the sorted array. This is less efficient than the other sort algorithms like quick sort, merge sort, etc.

Technique

Consider an array A whose elements are to be sorted. Initially, A[0] is the only element on the sorted set. In pass 1, A[1] is placed at its proper index in the array.

In pass 2, A[2] is placed at its proper index in the array. Likewise, in pass n-1, A[n-1] is placed at its proper index into the array.

To insert an element A[k] to its proper index, we must compare it with all other elements i.e. A[k-1], A[k-2], and so on until we find an element A[j] such that, A[j]<=A[k].

All the elements from A[k-1] to A[j] need to be shifted and A[k] will be moved to A[j+1].

Complexity

Complexity	Best Case	Average Case	Worst Case
Time	Ω(n)	θ(n2)	o(n2)
Space			o(1)

Algorithm

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

Step 2: SET TEMP = ARR[K]

Step 3: SET J = K - 1

Step 4: Repeat while TEMP <=ARR[J]
SET ARR[J + 1] = ARR[J]
SET J = J - 1
[END OF INNER LOOP]

Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]

Step 6: EXIT

C Program

#include<stdio.h>

void main ()

{

int i,j, k,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

printf("\nprinting sorted elements...\n");

for(k=1; k<10; k++)

{

temp = a[k];

j= k-1;

while(j>=0 && temp <= a[j])

{

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

j = j-1;

}

a[j+1] = temp;

}

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

{

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

}

Output:

Printing Sorted Elements . . .

101

C++ Program

#include<iostream>

using namespace std;

int main ()

{

int i,j, k,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

cout<<"\nprinting sorted elements...\n";

for(k=1; k<10; k++)

{

temp = a[k];

j= k-1;

while(j>=0 && temp <= a[j])

{

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

j = j-1;

}

a[j+1] = temp;

}

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

{

cout <<a[i]<<"\n";

}

Output:

printing sorted elements...

101

Java Program

public class InsertionSort {

public static void main(String[] args) {

int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

for(int k=1; k<10; k++)

{

int temp = a[k];

int j= k-1;

while(j>=0 && temp <= a[j])

{

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

j = j-1;

}

a[j+1] = temp;

}

System.out.println("printing sorted elements ...");

for(int i=0;i<10;i++)

{

System.out.println(a[i]);

}

Output:

Printing sorted elements . . .

101

C# Program

using System;

public class Program

{

public static void Main()

{

int i,j, k,temp;

int[] a = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

Console. WriteLine("\nprinting sorted elements...\n");

for(k=1; k<10; k++)

{

temp = a[k];

j= k-1;

while(j>=0 && temp <= a[j])

{

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

j = j-1;

}

a[j+1] = temp;

}

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

{

Console.WriteLine(a[i]);

}

Output:

printing sorted elements . . .

101

Python Program

a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]

for k in range(1,10):

temp = a[k]

j = k-1

while j>=0 and temp <=a[j]:

a[j+1]=a[j]

j = j-1

a[j+1] = temp

print("printing sorted elements...")

for i in a:

print(i)

Output:

printing sorted elements . . .

101

Swift Program

import Foundation

import Glibc

var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];

print("\nprinting sorted elements...\n");

for k in 1...9

{

let temp = a[k];

var j = k-1;

while j>=0 && temp <= a[j]

{

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

j = j-1;

}

a[j+1] = temp;

}

for i in a

{

print(i);

}

Output:

printing sorted elements...

101

JavaScript Program

<html>

<head>

<title>

Insertion Sort

</title>

</head>

<body>

var txt = "<br>";

var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];

document.writeln("printing sorted elements ... "+txt);

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

{

var temp = a[k]

j=k-1;

while (j>=0 && temp <= a[j])

{

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

jj = j-1;

}

a[j+1] = temp;

}

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

{

document.writeln(a[i]);

document.writeln(txt);

}

</script>

</body>

</html>

Output:

printing sorted elements ...

101

PHP Program

<html>

<head>

<title>Insertion Sort</title>

</head>

<body>

<?php

$a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);

echo("printing sorted elements ... \n");

for($k=0;$k<10;$k++)

{

$temp = $a[$k];

$j=$k-1;

while ($j>=0 && $temp <= $a[$j])

{

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

$j = $j-1;

}

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

}

for($i=0;$i<10;$i++)

{

echo $a[$i];

echo "\n";

}

</body>

</html>

Output:

printing sorted elements ...

101

Merge sort

Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps.

If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A into two sub-array of equal number of elements.

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

Combine the sub-arrays to form a single final sorted array maintaining the ordering of the array.

The main idea behind merge sort is that, the short list takes less time to be sorted.

Complexity

Complexity	Best case	Average Case	Worst Case
Time Complexity	O(n log n)	O(n log n)	O(n log n)
Space Complexity			O(n)

Example :

Consider the following array of 7 elements. Sort the array by using merge sort.

A = {10, 5, 2, 23, 45, 21, 7}

Merge sort

Algorithm

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

Step 2: Repeat while (I <= MID) AND (J<=END)
IF ARR[I] < ARR[J]
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[END OF IF]
SET INDEX = INDEX + 1
[END OF LOOP]
Step 3: [Copy the remaining
elements of right sub-array, if
any]
IF I > MID
Repeat while J <= END
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[END OF LOOP]
[Copy the remaining elements of
left sub-array, if any]
ELSE
Repeat while I <= MID
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[END OF LOOP]
[END OF IF]

Step 4: [Copy the contents of TEMP back to ARR] SET K = 0

Step 5: Repeat while K < INDEX
SET ARR[K] = TEMP[K]
SET K = K + 1
[END OF LOOP]

Step 6: Exit

MERGE_SORT(ARR, BEG, END)

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

Step 2: END

C Program

#include<stdio.h>

void mergeSort(int[],int,int);

void merge(int[],int,int,int);

void main ()

{

int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

int i;

mergeSort(a,0,9);

printf("printing the sorted elements");

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

{

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

}

void mergeSort(int a[], int beg, int end)

{

int mid;

if(beg<end)

{

mid = (beg+end)/2;

mergeSort(a,beg,mid);

mergeSort(a,mid+1,end);

merge(a,beg,mid,end);

}

void merge(int a[], int beg, int mid, int end)

{

int i=beg,j=mid+1,k,index = beg;

int temp[10];

while(i<=mid && j<=end)

{

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

{

temp[index] = a[i];

i = i+1;

}

else

{

temp[index] = a[j];

j = j+1;

}

index++;

}

if(i>mid)

{

while(j<=end)

{

temp[index] = a[j];

index++;

j++;

}

else

{

while(i<=mid)

{

temp[index] = a[i];

index++;

i++;

}

k = beg;

while(k<index)

{

a[k]=temp[k];

k++;

}

Output:

printing the sorted elements

101

Java Program

public class MyMergeSort

{

void merge(int arr[], int beg, int mid, int end)

{

int l = mid - beg + 1;

int r = end - mid;

intLeftArray[] = new int [l];

intRightArray[] = new int [r];

for (int i=0; i<l; ++i)

LeftArray[i] = arr[beg + i];

for (int j=0; j<r; ++j)

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

int i = 0, j = 0;

int k = beg;

while (i<l&&j<r)

{

if (LeftArray[i] <= RightArray[j])

{

arr[k] = LeftArray[i];

i++;

}

else

{

arr[k] = RightArray[j];

j++;

}

k++;

}

while (i<l)

{

arr[k] = LeftArray[i];

i++;

k++;

}

while (j<r)

{

arr[k] = RightArray[j];

j++;

k++;

}

void sort(int arr[], int beg, int end)

{

if (beg<end)

{

int mid = (beg+end)/2;

sort(arr, beg, mid);

sort(arr , mid+1, end);

merge(arr, beg, mid, end);

}

public static void main(String args[])

{

intarr[] = {90,23,101,45,65,23,67,89,34,23};

MyMergeSort ob = new MyMergeSort();

ob.sort(arr, 0, arr.length-1);

System.out.println("\nSorted array");

for(int i =0; i<arr.length;i++)

{

System.out.println(arr[i]+"");

}

Output:

Sorted array

101

C# Program

using System;

public class MyMergeSort

{

void merge(int[] arr, int beg, int mid, int end)

{

int l = mid - beg + 1;

int r = end - mid;

int i,j;

int[] LeftArray = new int [l];

int[] RightArray = new int [r];

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

LeftArray[i] = arr[beg + i];

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

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

i = 0; j = 0;

int k = beg;

while (i < l && j < r)

{

if (LeftArray[i] <= RightArray[j])

{

arr[k] = LeftArray[i];

i++;

}

else

{

arr[k] = RightArray[j];

j++;

}

k++;

}

while (i < l)

{

arr[k] = LeftArray[i];

i++;

k++;

}

while (j < r)

{

arr[k] = RightArray[j];

j++;

k++;

}

void sort(int[] arr, int beg, int end)

{

if (beg < end)

{

int mid = (beg+end)/2;

sort(arr, beg, mid);

sort(arr , mid+1, end);

merge(arr, beg, mid, end);

}

public static void Main()

{

int[] arr = {90,23,101,45,65,23,67,89,34,23};

MyMergeSort ob = new MyMergeSort();

ob.sort(arr, 0, 9);

Console.WriteLine("\nSorted array");

for(int i =0; i<10;i++)

{

Console.WriteLine(arr[i]+"");

}

Output:

Sorted array

101

Quick Sort

Quick sort is the widely used sorting algorithm that makes n log n comparisons in average case for sorting of an array of n elements. This algorithm follows divide and conquer approach. The algorithm processes the array in the following way.

Set the first index of the array to left and loc variable. Set the last index of the array to right variable. i.e. left = 0, loc = 0, en d = n - 1, where n is the length of the array.

Start from the right of the array and scan the complete array from right to beginning comparing each element of the array with the element pointed by loc.

Ensure that, a[loc] is less than a[right].

If this is the case, then continue with the comparison until right becomes equal to the loc.

If a[loc] > a[right], then swap the two values. And go to step 3.

Set, loc = right

start from element pointed by left and compare each element in its way with the element pointed by the variable loc. Ensure that a[loc] > a[left]

if this is the case, then continue with the comparison until loc becomes equal to left.
[loc] <a[right], then swap the two values and go to step 2.
Set, loc = left.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(n) for 3 way partition or O(n log n) simple partition	O(n log n)	O(n2)
Space Complexity			O(log n)

Algorithm

PARTITION (ARR, BEG, END, LOC)

Step 1: [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =

Step 2: Repeat Steps 3 to 6 while FLAG =

Step 3: Repeat while ARR[LOC] <=ARR[RIGHT]
AND LOC != RIGHT
SET RIGHT = RIGHT - 1
[END OF LOOP]

Step 4: IF LOC = RIGHT
SET FLAG = 1
ELSE IF ARR[LOC] > ARR[RIGHT]
SWAP ARR[LOC] with ARR[RIGHT]
SET LOC = RIGHT
[END OF IF]

Step 5: IF FLAG = 0
Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFT
SET LEFT = LEFT + 1
[END OF LOOP]

Step 6:IF LOC = LEFT
SET FLAG = 1
ELSE IF ARR[LOC] < ARR[LEFT]
SWAP ARR[LOC] with ARR[LEFT]
SET LOC = LEFT
[END OF IF]
[END OF IF]

Step 7: [END OF LOOP]

Step 8: END

QUICK_SORT (ARR, BEG, END)

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

Step 2: END

C Program

#include <stdio.h>

int partition(int a[], int beg, int end);

void quickSort(int a[], int beg, int end);

void main()

{

int i;

int arr[10]={90,23,101,45,65,23,67,89,34,23};

quickSort(arr, 0, 9);

printf("\n The sorted array is: \n");

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

printf(" %d\t", arr[i]);

}

int partition(int a[], int beg, int end)

{

int left, right, temp, loc, flag;

loc = left = beg;

right = end;

flag = 0;

while(flag != 1)

{

while((a[loc] <= a[right]) && (loc!=right))

right--;

if(loc==right)

flag =1;

else if(a[loc]>a[right])

{

temp = a[loc];

a[loc] = a[right];

a[right] = temp;

loc = right;

}

if(flag!=1)

{

while((a[loc] >= a[left]) && (loc!=left))

left++;

if(loc==left)

flag =1;

else if(a[loc] <a[left])

{

temp = a[loc];

a[loc] = a[left];

a[left] = temp;

loc = left;

}

return loc;

}

void quickSort(int a[], int beg, int end)

{

int loc;

if(beg<end)

{

loc = partition(a, beg, end);

quickSort(a, beg, loc-1);

quickSort(a, loc+1, end);

}

Output:

The sorted array is:

101

Java Program

public class QuickSort {

public static void main(String[] args) {

int i;

int[] arr={90,23,101,45,65,23,67,89,34,23};

quickSort(arr, 0, 9);

System.out.println("\n The sorted array is: \n");

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

System.out.println(arr[i]);

}

public static int partition(int a[], int beg, int end)

{

int left, right, temp, loc, flag;

loc = left = beg;

right = end;

flag = 0;

while(flag != 1)

{

while((a[loc] <= a[right]) && (loc!=right))

right--;

if(loc==right)

flag =1;

elseif(a[loc]>a[right])

{

temp = a[loc];

a[loc] = a[right];

a[right] = temp;

loc = right;

}

if(flag!=1)

{

while((a[loc] >= a[left]) && (loc!=left))

left++;

if(loc==left)

flag =1;

elseif(a[loc] <a[left])

{

temp = a[loc];

a[loc] = a[left];

a[left] = temp;

loc = left;

}

returnloc;

}

static void quickSort(int a[], int beg, int end)

{

int loc;

if(beg<end)

{

loc = partition(a, beg, end);

quickSort(a, beg, loc-1);

quickSort(a, loc+1, end);

}

Output:

The sorted array is:

101

C# Program

using System;

public class QueueSort{

public static void Main() {

int i;

int[] arr={90,23,101,45,65,23,67,89,34,23};

quickSort(arr, 0, 9);

Console.WriteLine("\n The sorted array is: \n");

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

Console.WriteLine(arr[i]);

}

public static int partition(int[] a, int beg, int end)

{

int left, right, temp, loc, flag;

loc = left = beg;

right = end;

flag = 0;

while(flag != 1)

{

while((a[loc] <= a[right]) && (loc!=right))

right--;

if(loc==right)

flag =1;

else if(a[loc]>a[right])

{

temp = a[loc];

a[loc] = a[right];

a[right] = temp;

loc = right;

}

if(flag!=1)

{

while((a[loc] >= a[left]) && (loc!=left))

left++;

if(loc==left)

flag =1;

else if(a[loc] <a[left])

{

temp = a[loc];

a[loc] = a[left];

a[left] = temp;

loc = left;

}

return loc;

}

static void quickSort(int[] a, int beg, int end)

{

int loc;

if(beg<end)

{

loc = partition(a, beg, end);

quickSort(a, beg, loc-1);

quickSort(a, loc+1, end);

}

Output:

The sorted array is:

101

Radix Sort

Radix sort processes the elements the same way in which the names of the students are sorted according to their alphabetical order. There are 26 radix in that case due to the fact that, there are 26 alphabets in English. In the first pass, the names are grouped according to the ascending order of the first letter of names.

In the second pass, the names are grouped according to the ascending order of the second letter. The same process continues until we find the sorted list of names. The bucket are used to store the names produced in each pass. The number of passes depends upon the length of the name with the maximum letter.

In the case of integers, radix sort sorts the numbers according to their digits. The comparisons are made among the digits of the number from LSB to MSB. The number of passes depend upon the length of the number with the most number of digits.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	Ω(n+k)	θ(nk)	O(nk)
Space Complexity			O(n+k)

Example

Consider the array of length 6 given below. Sort the array by using Radix sort.

A = {10, 2, 901, 803, 1024}

Pass 1: (Sort the list according to the digits at 0's place)

10, 901, 2, 803, 1024.

Pass 2: (Sort the list according to the digits at 10's place)

02, 10, 901, 803, 1024

Pass 3: (Sort the list according to the digits at 100's place)

02, 10, 1024, 803, 901.

Pass 4: (Sort the list according to the digits at 1000's place)

02, 10, 803, 901, 1024

Therefore, the list generated in the step 4 is the sorted list, arranged from radix sort.

Algorithm

Step 1:Find the largest number in ARR as LARGE

Step 2: [INITIALIZE] SET NOP = Number of digits
in LARGE

Step 3: SET PASS =0

Step 4: Repeat Step 5 while PASS <= NOP-1

Step 5: SET I = 0 and INITIALIZE buckets

Step 6:Repeat Steps 7 to 9 while I<n-1< li=""></n-1<>

Step 7: SET DIGIT = digit at PASSth place in A[I]

Step 8: Add A[I] to the bucket numbered DIGIT

Step 9: INCREMENT bucket count for bucket
numbered DIGIT
[END OF LOOP]

Step 10: Collect the numbers in the bucket
[END OF LOOP]

Step 11: END

C Program

#include <stdio.h>

int largest(int a[]);

void radix_sort(int a[]);

void main()

{

int i;

int a[10]={90,23,101,45,65,23,67,89,34,23};

radix_sort(a);

printf("\n The sorted array is: \n");

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

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

}

int largest(int a[])

{

int larger=a[0], i;

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

{

if(a[i]>larger)

larger = a[i];

}

return larger;

}

void radix_sort(int a[])

{

int bucket[10][10], bucket_count[10];

int i, j, k, remainder, NOP=0, divisor=1, larger, pass;

larger = largest(a);

while(larger>0)

{

NOP++;

larger/=10;

}

for(pass=0;pass<NOP;pass++) // Initialize the buckets

{

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

bucket_count[i]=0;

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

{

// sort the numbers according to the digit at passth place

remainder = (a[i]/divisor)%10;

bucket[remainder][bucket_count[remainder]] = a[i];

bucket_count[remainder] += 1;

}

// collect the numbers after PASS pass

i=0;

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

{

for(j=0;j<bucket_count[k];j++)

{

a[i] = bucket[k][j];

i++;

}

divisor *= 10;

}

Output:

The sorted array is:

101

Java Program

public class Radix_Sort {

public static void main(String[] args) {

int i;

Scanner sc = new Scanner(System.in);

int[] a = {90,23,101,45,65,23,67,89,34,23};

radix_sort(a);

System.out.println("\n The sorted array is: \n");

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

System.out.println(a[i]);

}

static int largest(inta[])

{

int larger=a[0], i;

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

{

if(a[i]>larger)

larger = a[i];

}

returnlarger;

}

static void radix_sort(inta[])

{

int bucket[][]=newint[10][10];

int bucket_count[]=newint[10];

int i, j, k, remainder, NOP=0, divisor=1, larger, pass;

larger = largest(a);

while(larger>0)

{

NOP++;

larger/=10;

}

for(pass=0;pass<NOP;pass++) // Initialize the buckets

{

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

bucket_count[i]=0;

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

{

// sort the numbers according to the digit at passth place

remainder = (a[i]/divisor)%10;

bucket[remainder][bucket_count[remainder]] = a[i];

bucket_count[remainder] += 1;

}

// collect the numbers after PASS pass

i=0;

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

{

for(j=0;j<bucket_count[k];j++)

{

a[i] = bucket[k][j];

i++;

}

divisor *= 10;

}

Output:

The sorted array is:

101

C# Program

using System;

public class Radix_Sort {

public static void Main()

{

int i;

int[] a = {90,23,101,45,65,23,67,89,34,23};

radix_sort(a);

Console.WriteLine("\n The sorted array is: \n");

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

Console.WriteLine(a[i]);

}

static int largest(int[] a)

{

int larger=a[0], i;

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

{

if(a[i]>larger)

larger = a[i];

}

return larger;

}

static void radix_sort(int[] a)

{

int[,] bucket=new int[10,10];

int[] bucket_count=new int[10];

int i, j, k, remainder, NOP=0, divisor=1, larger, pass;

larger = largest(a);

while(larger>0)

{

NOP++;

larger/=10;

}

for(pass=0;pass<NOP;pass++) // Initialize the buckets

{

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

bucket_count[i]=0;

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

{

// sort the numbers according to the digit at passth place

remainder = (a[i]/divisor)%10;

bucket[remainder,bucket_count[remainder]] = a[i];

bucket_count[remainder] += 1;

}

// collect the numbers after PASS pass

i=0;

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

{

for(j=0;j<bucket_count[k];j++)

{

a[i] = bucket[k,j];

i++;

}

divisor *= 10;

}

Output:

The sorted array is:

101

2.4 Complexity and analysis

Algorithm Analysis

Analysis of efficiency of an algorithm can be performed at two different stages, before implementation and after implementation, as

A priori analysis −This is defined as theoretical analysis of an algorithm. Efficiency of algorithm is measured by assuming that all other factors e.g. speed of processor, are constant and have no effect on implementation.

A posterior analysis −This is defined as empirical analysis of an algorithm. The chosen algorithm is implemented using programming language. Next the chosen algorithm is executed on target computer machine. In this analysis, actual statistics like running time and space needed are collected.

Algorithm analysis is dealt with the execution or running time of various operations involved. Running time of an operation can be defined as number of computer instructions executed per operation.

Algorithm Complexity

Suppose X is treated as an algorithm and N is treated as the size of input data, the time and space implemented by the Algorithm X are the two main factors which determine the efficiency of X.

Time Factor −The time is calculated or measured by counting the number of key operations such as comparisons in sorting algorithm.

Space Factor −The space is calculated or measured by counting the maximum memory space required by the algorithm.

The complexity of an algorithm f(N) provides the running time and / or storage space needed by the algorithm with respect of N as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space needed the algorithm in its life cycle.

Space needed by an algorithm is equal to the sum of the following two components

A fixed part that is a space required to store certain data and variables (i.e. simple variables and constants, program size etc.), that are not dependent of the size of the problem.

A variable part is a space required by variables, whose size is totally dependent on the size of the problem. For example, recursion stack space, dynamic memory allocation etc.

Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the fixed part and S(I) is treated as the variable part of the algorithm which depends on instance characteristic I. Following is a simple example that tries to explain the concept

Algorithm

SUM(P, Q)

Step 1 - START

Step 2 - R ← P + Q + 10

Step 3 - Stop

Here we have three variables P, Q and R and one constant. Hence S(p) = 1+3. Now space is dependent on data types of given constant types and variables and it will be multiplied accordingly.

Time Complexity

Time Complexity of an algorithm is the representation of the amount of time required by the algorithm to execute to completion. Time requirements can be denoted or defined as a numerical function t(N), where t(N) can be measured as the number of steps, provided each step takes constant time.

For example, in case of addition of two n-bit integers, N steps are taken. Consequently, the total computational time is t(N) = c*n, where c is the time consumed for addition of two bits. Here, we observe that t(N) grows linearly as input size increases.

TEXT BOOKS:

Schaum’s Outlines Data Structures – Seymour Lipschutz (MGH)

REFERENCE BOOKS:

Data Structure using C- A. M. Tanenbaum, Y. Langsam, M. J. Augenstein(PHI)

Data Structures- A Pseudo code Approach with C – Richard F. Gilberg and Behrouz A. Forouzon 2 ndEdition

Sign Up

Index

Notes

Highlighted

Underlined

Browse by Topics

Notes

Highlighted

Underlined