Algorithms

Question 1

insertionSort:

1. How does it work?
2. Why would you use it?

Answer 1

1. 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
2. It’s simply to write (but not very efficient)
   
   1. for a small list
   2. or nearly sorted list

Question 2

What are the four steps in quickSort?

Answer 2

1. Choose on item from the list as a pivot

2. 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
3. recursively quicksort smalls
4. recursively quicksort the bigs (now the array is completly sorted)

Question 3

What is worst case running time of selectionSort()?

Answer 3

O(n²)

Question 4

What is the worst case running time for insertionSort()?

Answer 4

O(n²)

Question 5

What is the worst case running time of quickSort()?

What is it’s average?

Answer 5

O(n^2)

The average is closer to (nlogn)

Question 6

What is the worst case running time for mergeSort()?

Answer 6

O(nlogn)

Question 7

What is the formula for determining the run time of Radix sort?

What does each variable stand for?

Answer 7

O(d(N + n)

d = digits

N = work to be done, number of buckets

n = amount of items

Question 8

How does mergeSort work?

What at the main functions?

Answer 8

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

Question 9

How does radixSort work?

Answer 9

In the case of int:

1. creates buckets(linkedlists) for each possible option(0-9)
2. puts each item in it’s corresponding one’s place bucket adding each item to the back of the list
3. it then concatinates all the bucks in order (0-9, first item in the bucket to the last). Order is important.
4. does step #2 for 10’s place
5. repeats #3
6. This continues until the final digit place has been reached and when the list is concatenated, its in order

Question 10

radixSort:

What would need to be done sorting strings of different lengths?

Answer 10

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

Question 11

For insertion sort, what are the main variables?

Answer 11

int siftVal

int j;

Question 12

For insertion Sort, what are the for loop conditions

Answer 12

for(int i = 1; i< a.length; i++)

Question 13

For insertion sort, what are the while loop conditions?

Answer 13

while(j >= 0 && a[j] > siftVal)

Question 14

for insertion sort, what is the for loop code?

Answer 14

for(int i = 1; i< a.length; i++){
siftVal = a[i];
j = i-1;
while(){
}
a[j+1] = siftVal;
}
}

Question 15

For insertion sort, what is the while loop code?

Answer 15

Question 16

What is the entire insertSort code?

Answer 16

Question 17

What is the public driver method of merge sort?

Answer 17

Question 18

What is the private helper method for mergeSort?

Answer 18

Question 19

For mergeSort what is the code for the merge function?

Answer 19

Question 20

For quickSort, what is the public driver method?

Answer 20

public void quickSort(int[] a){

quickSort(a, 0, a.length);

}

Question 21

What is the private helper method for quickSort?

Answer 21

Question 22

What is the code to chose a pivot randomly?

Answer 22

import java.util.*;

private static Random generator = new Random(System.nanoTyime());

int randomIndex;

randomIndex = generator.nextInt(end- start)+start;

Question 23

for quickSort, when partitioning, what is the form of the array?

Answer 23

Question 24

What is the partition function code for quickSort?

Answer 24

Question 25

Which sort uses a pivot?

Answer 25

QuickSort

Question 26

Which sort partitions?

Answer 26

quickSort

Question 27

which sort uses a temp array?

Answer 27

mergeSort

Question 28

How does Selection Sort work?

Answer 28

Question 29

What are the main variables of selection sort?

Answer 29

int n;

int minIndex;

Question 30

What is the code for the outer for loop for selectionSort?

Answer 30

for(int i = 0; i < n-1; i++){

minIndex = i;

for()

int temp = nums[i];

nums[i] = nums[minIndex];

nums[minIndex] = temp;

}

}

Question 31

What is the code for the inner for loop for selectionSort?

Answer 31

for(int j = i+1; j < n; j++){

if(nums[j] < nums[minIndex]

minIndex = j;

}

Question 32

What is the speed of selection sort?

Answer 32

O(n²)

Question 33

What is selection sorts entire code?

Answer 33

Question 34

What is the worst case scenario for insertionSort?

Answer 34

The list is in reverse order

Question 35

What is the worst case scenario for quick sort? What is it’s speed then?

Answer 35

We pick a pivot doesn’t split the list roughly in half.

Worst case: O(n²)