Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 240 MT > Sorting Algos > Flashcards

Sorting Algos Flashcards

1
Q

Explain how Selection Sort works

A
  • Keep track of current item and current minimum
  • Start at first index and interate through the array, keeping track of the minimum item’s index
  • After iterating through the array, if the current minimum is less than the current index, swap the items
  • Continue for every index until array is sorted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Explain how Insertion Sort works

A
  • Start at the first index
  • Compare current item with item to the left
  • if it is greater, keep as it is
  • if it is less than, swap with left item until the item on the left is smaller
  • Continue for entire array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain how Merge Sort works

A
  • Recursively split the array in two until you are left with pairs of individual indexes
  • Take each pair of sub-arrays and MERGE them into another array in sorted order
  • Continue merging pairs until the entire array is sorted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Explain how Quick Sort works

A

Pivot conditions:

  • Correct position in final array
  • Items to the left are smaller
  • Items to the right are larger

ItemOnLeft - Starting from the left of the array, the first item that is larger than the pivot

ItemOnRight - Starting from right of the array, the first item that is smaller than the pivot

  • Choose a pivot in the array and swap it to the back
  • Find IOR and IOL and swap them
  • If the index of IOL > index of IOR, stop
  • Swap pivot (whic is at the back) with IOL
  • Recursively sort the LHS and RHS
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Explain how Heap Sort works

A
  • Initialize an empty Heap H
  • Insert all the items in the array into H
  • deleteMax and add to array starting from A[n-1] until A[0]
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain how Radix Sort works

A 
R= Radix (base system)
d = # of digits
  • Start at either at most or least significant digit
  • For each digit, add to count or buckets and sort back into the array by your current digit
  • Repeat d (or m?) times
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the best case complexity for Selection sort?

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the worst case complexity for Selection sort?

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the average case complexity for Selection sort?

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the best case complexity for Insertion sort?

A

Theta(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the worst case complexity for Insertion sort?

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the average case complexity for Insertion sort?

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the best case complexity for Merge sort?

A

Theta(nlog(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the worst case complexity for Merge sort?

A

Theta(nlog(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the average case complexity for Merge sort?

A

Theta(nlog(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Why are the complexities for Selection Sort the same?

A

Regardless of how much the array is sorted at the beginning, we will always have to iterate through n, n-1, n-2, …. 2, 1 indicies. This is n^2 time

17
Q

Why are the complexities for Insertion sort different?

A

If the array is already sorted, the number of swaps needed is 0, meaning we only have to do n comparisons and no swaps.

18
Q

Why are the complexities for Merge Sort the same?

A

At every recursive level we have Theta(n) operations. The number of levels is log(n). Regardless of how sorted the array is at the beginning, this is the case

19
Q

What is the best case complexity for Quick sort?

A

Theta(nlog(n))

20
Q

What is the worst case complexity for Quick sort?

A

Theta(n^2)

21
Q

What is the average case complexity for Quick sort?

A

Theta(nlog(n))

22
Q

Why is there a difference between the worst and best case complexity for Quick Sort?

A

It all depends on how you pick your partition. The best case will have a perfectly balanced partition while the worst case will have every partition include only one element.

23
Q

What is the average complexity for LSD Radix Sort?

A

Theta(m(n+R))
Where m = # of digits
R = Radix (base)

24
Q

Can Radix sort to better than comparison based sorting?

A

Yes, Radix can get to o(nlog(n))

25
Q

What is the complexity of Heap Sort

A

Heap sort in all cases is Theta(nlog(n))

26
Q

What is randomized Quick Sort?

A

Pick a random pivot at each step

27
Q

What is the complexity of Randomized Quick Sort?

A

Average run time of Theta(n)

Worst-Case expected of Theta(n) as well

28
Q

What is expected runtime?

A

For a randomized algorithm, you measure your complexity by “expected” runtime since it is randomized. Thus your worst, best and average runtimes are really “what is the expected runtime give the worst, best or average inputs”

29
Q

What is the lower bound for comparison-based sorting?

A

Omega(nlog(n)) - all comparison based sorting takes at least nlog(n) time

30
Q

Compare the runtime of comparison and non-comparison based sorting

A

Non-comparison based sorting can achieve o(nlog(n)) depending on the input while the lower bound for comparison-based sorting is Theta(nlog(n))

CS 240 MT (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions