Using Java, implement the following sorting algorithms on random integer arrays
ID: 3740482 • Letter: U
Question
Using Java, implement the following sorting algorithms on random integer arrays of sizes: 1000, 10,000,
and 100,000.
• Merge Sort
• Heap Sort
• Quick Sort
TOPOLOGICAL SORT:
You will be provided a DAG in the GR format (from Assignment 4). Your program will print out the
topological sort of the vertices. You will accomplish this by creating a new class DAG from the provided
Graph object. The DAG class will provide two functions –
1. TopologicalSort()
2. Print()
The Print function will print the list of vertices sorted by their topological ordering.
Also, analyze your program and provide the T(n) and O(n) estimates for your Topological Sorting
algorithm.
public class Main {
public static void main(String[] args) {
String grFile = args[0];
// Create Graph Object
Graph graph = new Graph(grFile);
graph.PrintGraph();
DAG dag = new DAG (graph);
dag.TopologicalSort();
dag.Print();
}
}
Sample Input:
c -- Sample DAG
c -- Many topological sorts exist on this graph
c -- Ex. 1, 2, 5, 4, 3, 6, 7
c -- Ex. 2, 1, 5, 4, 7, 3, 6
c -- Ex. 2, 5, 1, 4, 7, 3, 6
c -- etc.
p sp 7 10
a 1 3 1
a 1 4 1
a 2 4 1
a 2 5 1
a 3 6 1
a 4 3 1
a 4 6 1
a 4 7 1
a 5 4 1
a 5 7 1
Output:
Adjacency List for the Graph
From Vertex: 1 -> 3 (1) 4 (1)
From Vertex: 2 -> 4 (1) 5 (1)
From Vertex: 3 -> 6 (1)
From Vertex: 4 -> 3 (1) 6 (1) 7 (1)
From Vertex: 5 -> 4 (1) 7 (1)
From Vertex: 6 ->
From Vertex: 7 ->
TOPOLOGICAL ORDERING OF VERTICES ..
1 --> 2 --> 5 --> 4 --> 3 --> 6 --> 7
Explanation / Answer
Quick sort:-
package com.java2novice.sorting;
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
Output:-
2 2 12 20 24 45 53 56 56 75 99
Merge sort:-
heapsort:-
output:-
Topology sort:-
import java.io.*;
import java.util.*;
// This class represents a directed graph using adjacency
// list representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; // Adjacency List
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;
// Recur for all the vertices adjacent to this
// vertex
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
// Push current vertex to stack which stores result
stack.push(new Integer(v));
}
// The function to do Topological Sort. It uses
// recursive topologicalSortUtil()
void topologicalSort()
{
Stack stack = new Stack();
// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to store
// Topological Sort starting from all vertices
// one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
// Print contents of stack
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}
// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}
// This code is contributed by Aakash Hasija
Output:-
import java.io.*;
import java.util.*;
// This class represents a directed graph using adjacency
// list representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; // Adjacency List
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;
// Recur for all the vertices adjacent to this
// vertex
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
// Push current vertex to stack which stores result
stack.push(new Integer(v));
}
// The function to do Topological Sort. It uses
// recursive topologicalSortUtil()
void topologicalSort()
{
Stack stack = new Stack();
// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to store
// Topological Sort starting from all vertices
// one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
// Print contents of stack
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}
// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}
// This code is contributed by Aakash Hasija
Output:-
Following is a Topological Sort of the given graph 5 4 2 3 1 0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.