Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-03-14

posted Mar 14, 2019, 6:25 AM by Konstantinovich Samuel   [ updated Mar 14, 2019, 7:17 AM ]
Happy PI day!

DO NOW
Write your name and perio on a piece of paper (can be in notes)
Discuss, write down your answer + justification (algorithm) for each of these:

1a. When sorting with the quicksort, do values that are equal
      stay in the same order or are they sometimes shifted?
1b. When does this matter?

2a. What is the runtime of taking two sorted arrays of size m and n,
and making one sorted array out of them?
2b. What if you had one array, that has the left side sorted, and right side sorted e.g.:
  { 1, 9, 10, 55, 230, 5000, 5, 22, 55, 59,100 }
-What is the runtime of merging the values into sorted order?
-Do you need extra space?


3.
def foo():
    count = 0
    for i in range(100000):
        x = random.random()  #between 0 and 1
        y = random.random() #between 0 and 1
        if(x**2 + y**2 < 1):
            count+=1
    print(count/100000.0*4)






Consider the diagram of the merge sort:




Testing your quicksort:

public static void main(String[]args){
  System.out.println("Size\t\tMax Value\tquick/builtin ratio ");
  int[]MAX_LIST = {1000000000,500,10};
  for(int MAX : MAX_LIST){
    for(int size = 31250; size < 2000001; size*=2){
      long qtime=0;
      long btime=0;
      //average of 5 sorts.
      for(int trial = 0 ; trial <=5; trial++){
        int []data1 = new int[size];
        int []data2 = new int[size];
        for(int i = 0; i < data1.length; i++){
          data1[i] = (int)(Math.random()*MAX);
          data2[i] = data1[i];
        }
        long t1,t2;
        t1 = System.currentTimeMillis();
        Quick.quicksort(data2);
        t2 = System.currentTimeMillis();
        qtime += t2 - t1;
        t1 = System.currentTimeMillis();
        Arrays.sort(data1);
        t2 = System.currentTimeMillis();
        btime+= t2 - t1;
        if(!Arrays.equals(data1,data2)){
          System.out.println("FAIL TO SORT!");
          System.exit(0);
        }
      }
      System.out.println(size +"\t\t"+MAX+"\t"+1.0*qtime/btime);
    }
    System.out.println();
  }
}



Comments