list of random integers like assignment 2, create 3 methods of sorting them then sort them. This time, you choose 3 algorithms but not the one we coded in A2.

Part 1: Stacks

o Pseudocode: Write 3 algorithm for sorting (Not used before!!!) o Calculate their time complexity (as a function of f(n)) oThen calculate their big-O o Decide which one is better when our input size n is 100 vs 10 vs 1000 Part2: LinkedList insert We will implement a program that will use your sorting algorithm. We will create a list of random integers, create 3 methods of sorting them then sort them.

use the code to start

import java.util.Random; // this creates random for our program

public class App {

//sample code for methods, create your own public static int mySort(int[] arr) { // YOUR CODE GOES HERE

return 0; }

public static void main(String[] args) throws Exception { int numItem = 100; // This decide how big you array is int[] myArr = new int[numItem]; Random myRand = new Random(); // creating Random object // Range for random to select from int min = 5; int max = 1000;

int indexMin = 0;

for (int i = 0; i < myArr.length; i++) { myArr[i] = myRand.nextInt(max - min + 1) + min; // storing random integers in an array }

// Now sort it double startTime = System.nanoTime(); // YOURSORTINGMETHOD(); double endTime = System.nanoTime(); double duration = (endTime - startTime); // divide by 1000000 to get milliseconds. System.out.println("the time it took to sort is " + duration); } }

sorting algorithm o Run them with n is 10, 100, or 1000

: if you can run them many times and average the time of running, it would be much easier to see the behavior.

help with these answera

Can you comment which one is faster?

Why did you choose them?

What was the big-O of them, did they perform the way you expected?

Can you re-do it in such a way that your array (your random array, if not random) is worst-case scenario?