# Algorithms Flashcards

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(n^{2})

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

O(n^{2})

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?