Using Java, implement the following sorting algorithms on random integer arrays

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.

PLEASE USE THIS MAIN METHOD and produce an OUTPUT SHOWN Below.

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

1) merge sort

2) Heap sort

3) quick sort : quick sort some what tricky so i am adding comments. if you need u can keep it otherwise you can remove.....

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.