1.

Selection Sort:
def selectionSort(array, size):

for ind in range(size):

min_index = ind

for j in range(ind + 1, size):

# select the minimum element in every iteration

if array[j] < array[min_index]:

min_index = j

# swapping the elements to sort the array

(array[ind], array[min_index]) = (array[min_index], array[ind])

arr = [64,25,12,22,11]

size = len(arr)

selectionSort(arr, size)

print('The array after sorting in Ascending Order by selection sort is:')

print(arr)

2. Travelling salesman problem:

from sys import maxsize

from itertools import permutations

V=4
# implementation of traveling Salesman Problem

def travellingSalesmanProblem(graph, s):

# store all vertex apart from source vertex

vertex = []

for i in range(V):

if i != s:

vertex.append(i)

min_path = maxsize

next_permutation = permutations(vertex)

for i in next_permutation:

# store current Path weight(cost)

current_pathweight = 0

# compute current path weight

k=s

for j in i:

current_pathweight += graph[k][j]

k=j

current_pathweight += graph[k][s]
 # update minimum

min_path = min(min_path, current_pathweight)

return min_path

if __name__ == "__main__":

# matrix representation of graph

graph = [[0, 10, 15, 20], [5, 0, 9, 10],

[6, 13, 0, 12], [8, 8, 9, 0]]

s=0

print(travellingSalesmanProblem(graph, s))

3. Knapsack using dynamic method:

def knapSack(W, wt, val, n):

K = [[0 for x in range(W + 1)] for x in range(n + 1)]

# Build table K[][] in bottom up manner

for i in range(n + 1):

for w in range(W + 1):

if i == 0 or w == 0:

K[i][w] = 0

elif wt[i-1] <= w:

 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])

else:

K[i][w] = K[i-1][w]

return K[n][W]

# Driver program to test above function

val = [12,10,20,15]

wt = [2,1,3,2]

W=5

n = len(val)

print(knapSack(W, wt, val, n))

4. Knapsack using greedy method

class Item:

def __init__(self, profit, weight):

self.profit = profit

self.weight = weight

# Main greedy function to solve problem

def fractionalKnapsack(W, arr):

# Sorting Item on basis of ratio

arr.sort(key=lambda x: (x.profit / x.weight), reverse=True)

# Result(value in Knapsack)
 finalvalue = 0.0

# Looping through all Items

for item in arr:

# If adding Item won't overflow,

# add it completely

if item.weight <= W:

W -= item.weight

finalvalue += item.profit

# If we can't add current Item,

# add fractional part of it

else:

finalvalue += item.profit * W / item.weight

break

# Returning final value

return finalvalue

# Driver Code

if __name__ == "__main__":

W = 50
 arr = [Item(60, 10), Item(100, 20), Item(120, 30)]

# Function call

max_val = fractionalKnapsack(W, arr)

print(max_val)

5. DFS

graph = {

'5' : ['3','7'],

'3' : ['2', '4'],

'7' : ['8'],

'2' : [],

'4' : ['8'],

'8' : []

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node): #function for dfs

if node not in visited:

print (node)

visited.add(node)

for neighbour in graph[node]:

dfs(visited, graph, neighbour)

 # Driver Code

print("Following is the Depth-First Search")

dfs(visited, graph, '5')

6. BFS

from collections import defaultdict

# This class represents a directed graph

# using adjacency list representation

class Graph:

# Constructor

def __init__(self):

# Default dictionary to store graph

self.graph = defaultdict(list)

# Function to add an edge to graph

def addEdge(self, u, v):

self.graph[u].append(v)

# Function to print a BFS of graph

def BFS(self, s):

# Mark all the vertices as not visited

visited = [False] * (max(self.graph) + 1)

# Create a queue for BFS

queue = []

# Mark the source node as

# visited and enqueue it

queue.append(s)

visited[s] = True

while queue:

# Dequeue a vertex from

# queue and print it

s = queue.pop(0)

print(s, end=" ")

# Get all adjacent vertices of the

# dequeued vertex s.

# If an adjacent has not been visited,

# then mark it visited and enqueue it

for i in self.graph[s]:

if visited[i] == False:
 queue.append(i)

visited[i] = True

# Driver code

if __name__ == '__main__':

# Create a graph given in

# the above diagram

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

print("Following is Breadth First Traversal"

" (starting from vertex 2)")

g.BFS(2)

7. To find minimum and maximum value using divide and conquer.

8. import sys
# Divide and conquer solution to find the minimum and maximum number in a list

def findMinAndMax(nums, left, right, min=sys.maxsize, max=-sys.maxsize):

# if the list contains only one element

if left == right: # common comparison

if min > nums[right]: # comparison 1

min = nums[right]

if max < nums[left]: # comparison 2

max = nums[left]

return min, max

# if the list contains only two elements

if right - left == 1: # common comparison

if nums[left] < nums[right]: # comparison 1

if min > nums[left]: # comparison 2

min = nums[left]

if max < nums[right]: # comparison 3

max = nums[right]

else:

if min > nums[right]: # comparison 2

min = nums[right]
 if max < nums[left]: # comparison 3

max = nums[left]

return min, max

# find the middle element

mid = (left + right) // 2

# recur for the left sublist

min, max = findMinAndMax(nums, left, mid, min, max)

# recur for the right sublist

min, max = findMinAndMax(nums, mid + 1, right, min, max)

return min, max

if __name__ == '__main__':

nums = [7, 2, 9, 3, 1, 6, 7, 8, 4]

# initialize the minimum element by INFINITY and the

# maximum element by -INFINITY

(min, max) = findMinAndMax(nums, 0, len(nums) - 1)

print("The minimum element in the list is", min)

print("The maximum element in the list is", max)

7. Divide and conquer strategy Eg: Quick sort algorithm
def partition(array, low, high):

# Choose the rightmost element as pivot

 pivot = array[high]

# Pointer for greater element

i = low - 1

# Traverse through all elements

# compare each element with pivot

for j in range(low, high):

if array[j] <= pivot:

# If element smaller than pivot is found

# swap it with the greater element pointed by i

i=i+1

# Swapping element at i with element at j

(array[i], array[j]) = (array[j], array[i])

# Swap the pivot element with

# the greater element specified by i

(array[i + 1], array[high]) = (array[high], array[i + 1])

# Return the position from where partition is done

return i + 1

# Function to perform quicksort

def quicksort(array, low, high):

if low < high:

 # Find pivot element such that

# element smaller than pivot are on the left

# element greater than pivot are on the right

pi = partition(array, low, high)

# Recursive call on the left of pivot

quicksort(array, low, pi - 1)

# Recursive call on the right of pivot

quicksort(array, pi + 1, high)

# Driver code

if __name__ == '__main__':

array = [10, 7, 8, 9, 1, 5]

N = len(array)

# Function call

quicksort(array, 0, N - 1)

print('Sorted array:')

for x in array:

print(x, end=" ")

Output:

Sorted array:

1 5 7 8 9 10

8. Merger Sort algorithm:

def mergeSort(arr):

if len(arr) > 1:
# Finding the mid of the array

mid = len(arr)//2

# Dividing the array elements

L = arr[:mid]

# Into 2 halves

R = arr[mid:]

# Sorting the first half

mergeSort(L)

# Sorting the second half

mergeSort(R)

i=j=k=0

# Copy data to temp arrays L[] and R[]

while i < len(L) and j < len(R):

if L[i] <= R[j]:

arr[k] = L[i]

i += 1

else:

arr[k] = R[j]

j += 1

k += 1

# Checking if any element was left

 while i < len(L):

arr[k] = L[i]

i += 1

k += 1

while j < len(R):

arr[k] = R[j]

j += 1

k += 1

# Code to print the list

def printList(arr):

for i in range(len(arr)):

print(arr[i], end=" ")

print()

# Driver Code

if __name__ == '__main__':

arr = [12, 11, 13, 5, 6, 7]

print("Given array is")

printList(arr)

mergeSort(arr)

print("\nSorted array is ")

printList(arr)

Output:
 Given array is

12 11 13 5 6 7

Sorted array is

5 6 7 11 12 13

9. Write C program that accepts the vertices and edges for a graph and stores it
as an adjacency matrix.

#include <stdio.h>

// N vertices and M Edges

int N, M;

// Function to create Adjacency Matrix

void createAdjMatrix(int Adj[][N + 1],int arr[][2])

{

// Initialise all value to this

// Adjacency list to zero

for (int i = 0; i < N + 1; i++) {

for (int j = 0; j < N + 1; j++) {

Adj[i][j] = 0;

}

}

// Traverse the array of Edges

for (int i = 0; i < M; i++) {

 // Find X and Y of Edges

int x = arr[i][0];

int y = arr[i][1];

// Update value to 1

Adj[x][y] = 1;

Adj[y][x] = 1;

}

}

// Function to print the created

// Adjacency Matrix

void printAdjMatrix(int Adj[][N + 1])

{

// Traverse the Adj[][]

for (int i = 1; i < N + 1; i++) {

for (int j = 1; j < N + 1; j++) {

// Print the value at Adj[i][j]

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

}

printf("\n");

}

}
// Driver Code

int main()

{

// Number of vertices

N = 5;

// Given Edges

int arr[][2]

= { { 1, 2 }, { 2, 3 },

{ 4, 5 }, { 1, 5 } };

// Number of Edges

M = sizeof(arr) / sizeof(arr[0]);

// For Adjacency Matrix

int Adj[N + 1][N + 1];

// Function call to create

// Adjacency Matrix

createAdjMatrix(Adj, arr);

// Print Adjacency Matrix

printAdjMatrix(Adj);

return 0;

}
Output:

01001
10100
01000
00001
1 0 0 1 0

12. Implement function to print In-Degree, Out-Degree and to display that adjacency
matrix.

def findInOutDegree(adjList, n):

_in = [0] * n

out = [0] * n

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

List = adjList[i]

# Out degree for ith vertex will be the count

# of direct paths from i to other vertices

out[i] = len(List)

for j in range(0, len(List)):

# Every vertex that has

# an incoming edge from i

_in[List[j]] += 1

print("Vertex\tIn\tOut")

for k in range(0, n):

print(str(k) + "\t" + str(_in[k]) +

"\t" + str(out[k]))

if __name__ == "__main__":
# Adjacency list representation of the graph

adjList = []

# Vertices 1 and 2 have an incoming edge

# from vertex 0

adjList.append([1, 2])

# Vertex 3 has an incoming edge from vertex 1

adjList.append([3])

# Vertices 0, 5 and 6 have an

# incoming edge from vertex 2

adjList.append([0, 5, 6])

# Vertices 1 and 4 have an

# incoming edge from vertex 3

adjList.append([1, 4])

# Vertices 2 and 3 have an

# incoming edge from vertex 4

adjList.append([2, 3])

# Vertices 4 and 6 have an

# incoming edge from vertex 5

adjList.append([4, 6])

# Vertex 5 has an incoming edge from vertex 6

adjList.append([5])
 n = len(adjList)

findInOutDegree(adjList, n)

Output:

1 2 1
2 2 3
3 2 2
4 2 2
5 2 2
6 2 1

13. Write program to implement backtracking algorithm for solving problems like N
queens.

global N

N=4

def printSolution(board):

for i in range(N):

for j in range(N):

if board[i][j] == 1:

print("Q",end=" ")

else:

print(".",end=" ")

print()

# A utility function to check if a queen can

# be placed on board[row][col]. Note that this

# function is called when "col" queens are

# already placed in columns from 0 to col -1.

# So we need to check only left side for

# attacking queens

def isSafe(board, row, col):

# Check this row on left side

for i in range(col):

if board[row][i] == 1:

return False

# Check upper diagonal on left side

for i, j in zip(range(row, -1, -1),

range(col, -1, -1)):

if board[i][j] == 1:

return False

# Check lower diagonal on left side

for i, j in zip(range(row, N, 1),

range(col, -1, -1)):

if board[i][j] == 1:

return False

return True

def solveNQUtil(board, col):

# Base case: If all queens are placed

# then return true

if col >= N:
 return True

# Consider this column and try placing

# this queen in all rows one by one

for i in range(N):

if isSafe(board, i, col):

# Place this queen in board[i][col]

board[i][col] = 1

# Recur to place rest of the queens

if solveNQUtil(board, col + 1) == True:

return True

# If placing queen in board[i][col

# doesn't lead to a solution, then

# queen from board[i][col]

board[i][col] = 0

# If the queen can not be placed in any row in

# this column col then return false

return False

# This function solves the N Queen problem using

# Backtracking. It mainly uses solveNQUtil() to

# solve the problem. It returns false if queens

# cannot be placed, otherwise return true and

# placement of queens in the form of 1s.

# note that there may be more than one

# solutions, this function prints one of the

# feasible solutions.

def solveNQ():

board = [[0, 0, 0, 0],

[0, 0, 0, 0],

[0, 0, 0, 0],

[0, 0, 0, 0]]

if solveNQUtil(board, 0) == False:

print("Solution does not exist")

return False

printSolution(board)

return True

# Driver Code

if __name__ == '__main__':

solveNQ()

Output:

..Q.
Q...
...Q
. Q . .

14. Write a program to implement the backtracking algorithm for the sum of subsets
problem.

def isSubsetSum(set, n, sum):

 # Base Cases

if (sum == 0):

return True

if (n == 0 and sum != 0):

return False

# If last element is greater than

# sum, then ignore it

if (set[n - 1] > sum):

return isSubsetSum(set, n - 1, sum);

# else, check if sum can be obtained

# by any of the following

# (a) including the last element

# (b) excluding the last element

return isSubsetSum(set, n - 1, sum) or isSubsetSum(set, n - 1, sum - set[n - 1])

# Driver program to test above function

set = [3, 34, 4, 12, 5, 2]

sum = 9

n = len(set)

if (isSubsetSum(set, n, sum) == True):

print("Found a subset with given sum")

else:

print("No subset with given sum")

Output:

Found a subset with given sum

15. Write program to implement greedy algorithm for job sequencing with deadlines.

def printJobScheduling(arr, t):

# length of array

n = len(arr)

# Sort all jobs according to

# decreasing order of profit

for i in range(n):

for j in range(n - 1 - i):

if arr[j][2] < arr[j + 1][2]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

# To keep track of free time slots

result = [False] * t

# To store result (Sequence of jobs)

job = ['-1'] * t

# Iterate through all given jobs

for i in range(len(arr)):

# Find a free slot for this job

# (Note that we start from the

# last possible slot)

for j in range(min(t - 1, arr[i][1] - 1), -1, -1):

# Free slot found

 if result[j] is False:

result[j] = True

job[j] = arr[i][0]

break

# print the sequence

print(job)

# Driver's Code

if __name__ == '__main__':

arr = [['a', 2, 100], # Job Array

['b', 1, 19],

['c', 2, 27],

['d', 1, 25],

['e', 3, 15]]

print("Following is maximum profit sequence of jobs")

# Function Call

printJobScheduling(arr, 3)

Output:

Following is maximum profit sequence of jobs

['c', 'a', 'e']

16. Write program to implement Dynamic Programming algorithm for the Optimal
Binary Search Tree Problem.
def optCost_memoized(freq, i, j):

# Reuse cost already calculated for the subproblems.

# Since we initialize cost matrix with 0 and fredquency for a tree of one node,
 # it can be used as a stop condition

if cost[i][j]:

return cost[i][j]

# Get sum of freq[i], freq[i+1], ... freq[j]

fsum = Sum(freq, i, j)

# Initialize minimum value

Min = 999999999999

# One by one consider all elements as

# root and recursively find cost of

# the BST, compare the cost with min

# and update min if needed

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

c = (optCost_memoized(freq, i, r - 1) + optCost_memoized(freq, r + 1, j))

c += fsum

if c < Min:

Min = c

# replace cost with new optimal calc

cost[i][j] = c

# Return minimum value

return cost[i][j]

# The main function that calculates minimum

# cost of a Binary Search Tree. It mainly

# uses optCost() to find the optimal cost.

def optimalSearchTree(keys, freq, n):

# Here array keys[] is assumed to be

# sorted in increasing order. If keys[]

# is not sorted, then add code to sort

# keys, and rearrange freq[] accordingly.

return optCost_memoized(freq, 0, n - 1)

# A utility function to get sum of

# array elements freq[i] to freq[j]

def Sum(freq, i, j):

s=0

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

s += freq[k]

return s

if __name__ == '__main__':

keys = [1,2,3,4]

freq = [0.1,0.2,0.4,0.3]

n = len(keys)

# cost[i][j] = Optimal cost of binary search

# tree that can be formed from keys[i] to keys[j].

# cost[0][n-1] will store the resultant cost

cost = [[0 for x in range(n + 1)] for y in range(n + 1)]

# For a single key, cost is equal to

# frequency of the key

 for i in range(n):

cost[i][i] = freq[i]

print("Cost of Optimal BST is", optimalSearchTree(keys, freq, n))

Output:

Cost of Optimal BST is 1.7

17. Write a program that implements Prim’s algorithm to generate minimum cost
spanning Tree.
import sys

class Graph():

def __init__(self, vertices):

self.V = vertices

self.graph = [[0 for column in range(vertices)]

for row in range(vertices)]

# A utility function to print

# the constructed MST stored in parent[]

def printMST(self, parent):

print("Edge \tWeight")

for i in range(1, self.V):

print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

# A utility function to find the vertex with

# minimum distance value, from the set of vertices

# not yet included in shortest path tree

def minKey(self, key, mstSet):

 # Initialize min value

min = sys.maxsize

for v in range(self.V):

if key[v] < min and mstSet[v] == False:

min = key[v]

min_index = v

return min_index

# Function to construct and print MST for a graph

# represented using adjacency matrix representation

def primMST(self):

# Key values used to pick minimum weight edge in cut

key = [sys.maxsize] * self.V

parent = [None] * self.V # Array to store constructed MST

# Make key 0 so that this vertex is picked as first vertex

key[0] = 0

mstSet = [False] * self.V

parent[0] = -1 # First node is always the root of

for cout in range(self.V):

# Pick the minimum distance vertex from

# the set of vertices not yet processed.

# u is always equal to src in first iteration

u = self.minKey(key, mstSet)
 # Put the minimum distance vertex in

# the shortest path tree

mstSet[u] = True

# Update dist value of the adjacent vertices

# of the picked vertex only if the current

# distance is greater than new distance and

# the vertex in not in the shortest path tree

for v in range(self.V):

# graph[u][v] is non zero only for adjacent vertices of m

# mstSet[v] is false for vertices not yet included in MST

# Update the key only if graph[u][v] is smaller than key[v]

if self.graph[u][v] > 0 and mstSet[v] == False \

and key[v] > self.graph[u][v]:

key[v] = self.graph[u][v]

parent[v] = u

self.printMST(parent)

# Driver's code

if __name__ == '__main__':

g = Graph(5)

g.graph = [[0, 2, 0, 6, 0],

[2, 0, 3, 8, 5],

[0, 3, 0, 0, 7],

[6, 8, 0, 0, 9],
 [0, 5, 7, 9, 0]]

g.primMST()

Output:

Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5

18. Write a program that implements Kruskal’s algorithm to generate minimum cost
spanning

class Graph:

def __init__(self, vertices):

self.V = vertices

self.graph = []

# Function to add an edge to graph

def addEdge(self, u, v, w):

self.graph.append([u, v, w])

# A utility function to find set of an element i

# (truly uses path compression technique)

def find(self, parent, i):

if parent[i] != i:

# Reassignment of node's parent

# to root node as

# path compression requires

 parent[i] = self.find(parent, parent[i])

return parent[i]

# A function that does union of two sets of x and y

# (uses union by rank)

def union(self, parent, rank, x, y):

# Attach smaller rank tree under root of

# high rank tree (Union by Rank)

if rank[x] < rank[y]:

parent[x] = y

elif rank[x] > rank[y]:

parent[y] = x

# If ranks are same, then make one as root

# and increment its rank by one

else:

parent[y] = x

rank[x] += 1

# The main function to construct MST

# using Kruskal's algorithm

def KruskalMST(self):

# This will store the resultant MST

result = []

# An index variable, used for sorted edges

i=0
# An index variable, used for result[]

e=0

# Sort all the edges in

# non-decreasing order of their

# weight

self.graph = sorted(self.graph,

key=lambda item: item[2])

parent = []

rank = []

# Create V subsets with single elements

for node in range(self.V):

parent.append(node)

rank.append(0)

# Number of edges to be taken is less than to V-1

while e < self.V - 1:

# Pick the smallest edge and increment

# the index for next iteration

u, v, w = self.graph[i]

i=i+1

x = self.find(parent, u)

y = self.find(parent, v)

# If including this edge doesn't

 # cause cycle, then include it in result

# and increment the index of result

# for next edge

if x != y:

e=e+1

result.append([u, v, w])

self.union(parent, rank, x, y)

# Else discard the edge

minimumCost = 0

print("Edges in the constructed MST")

for u, v, weight in result:

minimumCost += weight

print("%d -- %d == %d" % (u, v, weight))

print("Minimum Spanning Tree", minimumCost)

# Driver code

if __name__ == '__main__':

g = Graph(4)

g.addEdge(0, 1, 10)

g.addEdge(0, 2, 6)

g.addEdge(0, 3, 5)

g.addEdge(1, 3, 15)

g.addEdge(2, 3, 4)

# Function call

g.KruskalMST()
 Output:

Edges in the constructed MST

2 -- 3 == 4

0 -- 3 == 5

0 -- 1 == 10

Minimum Spanning Tree 19

10. Sort a given set of n integer elements using Merge Sort method and compute
its time complexity. Run the program for varied values of n> 5000, and record
the time taken to sort.
import java.util.Random;
import java.util.Scanner;

class QuickSort

{

private int a[];

public QuickSort(int[] a)

{

this.a = a;

}

public int partition ( int a[], int m, int p )

{

int v = a[m];

int i = m;

int j = p;

do

{ while (a[++ i] <v);

while ( a[-- j] > v );

if ( i < j )
interchange ( a, i, j );

} while ( i <= j );

a[m] = a[j]; a[j] = v;

return j;

}

public void qSort ( int p, int q )

{

int j;

if ( p < q )

{

j = partition ( a, p, q + 1 );

qSort ( p, j - 1 );

qSort ( j + 1, q );

}

}

public void interchange ( int a[], int i, int j )

{

int t;

t = a[i];

a[i] = a[j];

a[j] = t;

}

}

public class QuickSortDemo

{

public static void main(String[] args)

{
int n, a[], i;

Scanner input = new Scanner(System.in);

System.out.println("Enter the Size of an Array: ");

n = input.nextInt();

a = new int[n + 1];

Random rn = new Random();

System.out.println("System automatically generates numbers ");

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

{

a[i] = rn.nextInt(n);

}

a[i] = 100000; //Sentinel value

QuickSort qSort = new QuickSort(a);

System.out.println("Before Sort: ");

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

{

System.out.print(a[i] + "\t");

}

int p = 0;

int q = n - 1;

qSort.qSort(p, q);

System.out.println("\n\nAfter Sort: ");

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

{

System.out.print(a[i] + "\t");

}

int step = 2000;

double duration;

/* times for n = 0, 10, ..., 100, 200, ..., 5000 */

System.out.println ( "\n\nN\tRepetitions\tTime\n" );

for ( n = 5000; n < 50000; n += step )

{

a = new int[n + 1];

qSort = new QuickSort(a);

/*get time for size n */

long repetitions = 0;

long start = System.nanoTime();

do

{

repetitions ++;

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

a[i] = rn.nextInt(n);

a[i] = 100000; //Sentinel value

qSort.qSort(0, n - 1);

} while ( System.nanoTime() - start < 1000000000 );

/* repeat until enough time has elapsed */

duration = ( ( double ) ( System.nanoTime() - start ) ) / 1000000000;

duration /= repetitions;

System.out.println ( n + "\t" + repetitions + "\t\t" + duration );

}

}

}

OUTPUT:
Enter the Size of an Array:

5

System automatically generates numbers

Before Sort:

2 4 0 4 2

After Sort:

0 2 2 4 4

25 NAVEEN KUMAR K R AND ABDUL RAZAK M S

N Repetitions Time

5000 2604 3.840779374039939E-4

7000 1826 5.47683173603505E-4

9000 1384 7.22663938583815E-4

11000 1116 8.963977114695341E-4

13000 933 0.0010729254876741692

15000 803 0.0012468262278953922

17000 694 0.0014428503530259367

19000 623 0.0016070116115569826

21000 559 0.0017905278372093024

23000 506 0.001978315013833992

25000 465 0.0021531490322580643

27000 428 0.0023395274672897196

29000 396 0.0025256930378787876

31000 369 0.0027141917425474254

33000 345 0.0028995773043478264

35000 325 0.0030829968984615384

37000 305 0.00328287162295082

39000 289 0.003461591204152249

 41000 274 0.0036523042846715323

43000 243 0.004119721567901235

45000 248 0.004037317338709678

47000 233 0.004306232450643777

49000 227 0.004423571559471365

11. Sort a given set of n integer elements using Quick Sort method and compute
its time complexity. Run the program for varied values of n> 5000 and record
the time taken to sort.

import java.util.Random;

import java.util.Scanner;

class MergeSort

{

private int a[];

public MergeSort(int[] a)

{

this.a = a;

}

void merge ( int low, int mid, int high )

{

int b[] = new int[high + 1];

int h = low;

int i = low;

int j = mid + 1;

int k;

while ( ( h <= mid ) && ( j <= high ) )

{
if ( a[h] <= a[j] ) b[i ++] = a[h ++];

else b[i ++] = a[j ++];

} if (h>mid )

{

for ( k = j; k <= high; ++ k )

b[i ++] = a[k];

}

else

{

for ( k = h; k <= mid; ++ k )

b[i ++] = a[k];

} for (k=low; k<= high; ++ k)

a[k] =b[k];

}

void mergeSort ( int low, int high )

{

int mid;

if ( low < high )

{

mid = ( low + high ) / 2;

mergeSort ( low, mid );

mergeSort ( mid + 1, high );

merge ( low, mid, high );

}

}

}

public class MergeSortDemo

{

public static void main(String[] args)

{

int n, a[], i;

Scanner input = new Scanner(System.in);

System.out.println("Enter the Size of an Array: ");

n = input.nextInt();

a = new int[n + 1];

Random rn = new Random();

System.out.println("System automatically generates numbers ");

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

{

a[i] = rn.nextInt(n);//a[i] = input.nextInt();

}

a[i] = 100000; //Sentinel value

MergeSort mSort = new MergeSort(a);

System.out.println("Before Sort: ");

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

{

System.out.print(a[i] + "\t");

}

int low = 0;

int high = n - 1;

mSort.mergeSort(low, high);

System.out.println("\n\nAfter Sort: ");

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

{
System.out.print(a[i] + "\t");

}

int step = 2000;

double duration;

/* times for n = 0, 10, ..., 100, 200, ..., 5000 */

System.out.println ( "\n\nN\tRepetitions\tTime\n" );

for ( n = 5000; n < 50000; n += step )

{

a = new int[n + 1];

mSort = new MergeSort(a);

/*get time for size n */

long repetitions = 0;

long start = System.nanoTime();

do

{

repetitions ++;

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

a[i] = rn.nextInt(n);

a[i] = 100000; //Sentinel value

mSort.mergeSort(0, n - 1);

} while ( System.nanoTime() - start < 1000000000 );

/* repeat until enough time has elapsed */

duration = ( ( double ) ( System.nanoTime() - start ) ) / 1000000000;

duration /= repetitions;

System.out.println ( n + "\t" + repetitions + "\t\t" + duration );

}

}
}

OUTPUT:

Enter the Size of an Array:

5

System automatically generates numbers

Before Sort:

4 2 1 2 3

After Sort:

1 2 2 3 4

N Repetitions Time

5000 199 0.005027964120603015

7000 153 0.0065458487124183005

9000 97 0.010360987432989691

11000 59 0.017194349559322034

13000 54 0.018756191537037035

15000 42 0.024344312833333333

17000 33 0.030582966272727274

19000 27 0.03758708807407407

21000 22 0.046705298409090906

23000 18 0.05575357561111111

25000 16 0.0653416245625

27000 13 0.07881347792307693

29000 10 0.1020311572

31000 11 0.09932865818181819

33000 10 0.110072756

35000 9 0.12348744877777779
37000 8 0.139554033875

39000 7 0.15578334585714287

41000 7 0.16581026885714284

43000 6 0.19381527966666667

45000 5 0.215364133

47000 5 0.22233623480000003

49000 4 0.25112471825