insertionSort:
- How does it work?
- Why would you use it?
- One by one, it compares each new value to the sort side of the list, when it find a number larger thant it on the sorted side or it hits zero, that value is inserted
- It’s simply to write (but not very efficient)
- for a small list
- or nearly sorted list
What are the four steps in quickSort?
1. Choose on item from the list as a pivot
- Partition list a into the following:
- smalls | pivot | bigs
- where:
- the smalls are the items < the pivot (in no particular order)
- the bigs are the items >= the ipivot (in no particular order
- Note: the pivot is in the position it should be for the final sorted order of the whole list
- recursively quicksort smalls
- recursively quicksort the bigs (now the array is completly sorted)
What is worst case running time of selectionSort()?
O(n2)
What is the worst case running time for insertionSort()?
O(n2)
What is the worst case running time of quickSort()?
What is it’s average?
O(n^2)
The average is closer to (nlogn)
What is the worst case running time for mergeSort()?
O(nlogn)
What is the formula for determining the run time of Radix sort?
What does each variable stand for?
O(d(N + n)
d = digits
N = work to be done, number of buckets
n = amount of items
How does mergeSort work?
What at the main functions?
While there is more than 1 item, creates a temp array, it splits the list in half, sorts each side, then merges the items back together.
Base Case:
- If only zero of one item to sort: done!
- if more than one item to sort:
- split the items into two (unsorted halves)
- do a recursive call to sort each half (two calls)
- Merge the two sorted halves into one sorted list
How does radixSort work?
In the case of int:
- creates buckets(linkedlists) for each possible option(0-9)
- puts each item in it’s corresponding one’s place bucket adding each item to the back of the list
- it then concatinates all the bucks in order (0-9, first item in the bucket to the last). Order is important.
- does step #2 for 10’s place
- repeats #3
- This continues until the final digit place has been reached and when the list is concatenated, its in order
radixSort:
What would need to be done sorting strings of different lengths?
strings would need to be padded on their right sides with null
It’s a sequence of 0-bits so it’s order is always smaller
For insertion sort, what are the main variables?
int siftVal
int j;
For insertion Sort, what are the for loop conditions
for(int i = 1; i< a.length; i++)
For insertion sort, what are the while loop conditions?
while(j >= 0 && a[j] > siftVal)
for insertion sort, what is the for loop code?
for(int i = 1; i< a.length; i++){
siftVal = a[i];
j = i-1;
while(){
}
a[j+1] = siftVal;
}
}
For insertion sort, what is the while loop code?
What is the entire insertSort code?
What is the public driver method of merge sort?
What is the private helper method for mergeSort?
For mergeSort what is the code for the merge function?
For quickSort, what is the public driver method?
public void quickSort(int[] a){
quickSort(a, 0, a.length);
}
What is the private helper method for quickSort?
What is the code to chose a pivot randomly?
import java.util.*;
private static Random generator = new Random(System.nanoTyime());
int randomIndex;
randomIndex = generator.nextInt(end- start)+start;
for quickSort, when partitioning, what is the form of the array?
What is the partition function code for quickSort?
