# Algorithms Flashcards

1
Q

insertionSort:

1. How does it work?
2. Why would you use it?
A
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
2
Q

What are the four steps in quickSort?

A

1. Choose on item from the list as a pivot

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

What is worst case running time of selectionSort()?

A

O(n2)

4
Q

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

A

O(n2)

5
Q

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

What is it’s average?

A

O(n^2)

The average is closer to (nlogn)

6
Q

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

A

O(nlogn)

7
Q

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

What does each variable stand for?

A

O(d(N + n)

d = digits

N = work to be done, number of buckets

n = amount of items

8
Q

How does mergeSort work?

What at the main functions?

A

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
9
Q

A

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
10
Q

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

A

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

11
Q

For insertion sort, what are the main variables?

A

int siftVal

int j;

12
Q

For insertion Sort, what are the for loop conditions

A

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

13
Q

For insertion sort, what are the while loop conditions?

A

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

14
Q

for insertion sort, what is the for loop code?

A

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

15
Q

For insertion sort, what is the while loop code?

A
16
Q

What is the entire insertSort code?

A
17
Q

What is the public driver method of merge sort?

A
18
Q

What is the private helper method for mergeSort?

A
19
Q

For mergeSort what is the code for the merge function?

A
20
Q

For quickSort, what is the public driver method?

A

public void quickSort(int[] a){

quickSort(a, 0, a.length);

}

21
Q

What is the private helper method for quickSort?

A
22
Q

What is the code to chose a pivot randomly?

A

import java.util.*;

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

int randomIndex;

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

23
Q

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

A
24
Q

What is the partition function code for quickSort?

A
25
Q

Which sort uses a pivot?

A

QuickSort

26
Q

Which sort partitions?

A

quickSort

27
Q

which sort uses a temp array?

A

mergeSort

28
Q

How does Selection Sort work?

A
29
Q

What are the main variables of selection sort?

A

int n;

int minIndex;

30
Q

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

A

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

minIndex = i;

for()

int temp = nums[i];

nums[i] = nums[minIndex];

nums[minIndex] = temp;

}

}

31
Q

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

A

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

if(nums[j] < nums[minIndex]

minIndex = j;

}

32
Q

What is the speed of selection sort?

A

O(n2)

33
Q

What is selection sorts entire code?

A
34
Q

What is the worst case scenario for insertionSort?

A

The list is in reverse order

35
Q

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

A

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

Worst case: O(n2)