Q: Is there a proof of why the minimum complexity is n*log(n)?
A1: live answered
A2: Take CS161 and you get to prove it yourself on a pset!
Q: how do you determine what type of list is already almost sorted?
A1: live answered
Q: What sorting algorithm is does vec.sort() use in “vector.h”?
A1: quick-insert hybrid
Q: Would we be discussing Big O for these sorts? Is the Big O for Insertion is O(n^2)?
A1: live answered
Q: to insert 2 in the correct place, could you use some kind of binary method to insert it properly more efficiently?
A1: live answered
Q: But we will still need to check every element, correct? Therefore it’s O(n) for the best case
A1: Yes!
Q: Is O(n^2) because we have to shift n times for each elment (in total n elements)?
A1: Yes
Q: So, that’s also gonna be O(n^2)?
A1: correct!
Q: WHy is it O(n^2)?
A1: live answered
Q: Would the runtime be O(Xn) for the one use of selection sort (findining the top X elements)?
A1: Correct
Q: why are we using vectors instead of queues?
A1: live answered
Q: What if we had [2,5] and [1,9]? Wouldn’t they need to split and merge again?
A1: live answered
Q: mergeSort doesn't do any of the actual sorting right?
A1: live answered
Q: Sounds like it is O(n log n), correct?
A1: correct
Q: if you split by 3, would it be log3 (n)
A1: live answered
A2: Yes but the merge step would be come a lot harder
Q: Is the base always 2 for log in computer science?
A1: live answered
A2: Not always, but a lot of the time. The base doesnt matter in big O expressions but in general since we split in half a lot, base is 2 a lot of the time
Q: does the creation of two more vectors slow down the efficiency when the first vector is very large?
A1: live answered
Q: Don’t you have to constantly update the pivot?
A1: Correct
Q: Is it possible to do merge sort in place?
A1: live answered
A2: Yes, but rather challenging
Q: Is there any significance of picking a certain pivot or do we usually just pick the first element?
A1: live answered
Q: can’t we somehow know that it is sorted and stop before having to go over the elements again in the final step?
A1: We could, but checking if sorted is a O(N) step
Q: What if your pivot is 6 and you have another 6 in the list?
A1: You can choose how to handle values equal to the pivot
Q: why do you add the pivot to the left list?
A1: You can choose, either way will work the same
Q: can we assume picking a random index in a range of numbers is O(1)?
A1: live answered
Q: Why would you want to sort something that's already sorted
A1: live answered
Q: Can we check first how many elems are unsorted and pick an algorithm based on that?
A1: live answered
A2: There’s no great algorithm to decide which ones are unsorted without doing the sort itself
Q: Is Quicksort considered better than Merge Sort?
A1: Not necessarily. Merge sort is more consistent. Quick sort can be better or worse
A2: It depends – both are used in practice
Q: Why is worst case n^2 for quicksort because you only need n lists?
A1: If the pivot doesnt actually split the elements in half every time, there will be n split steps along the way because list size only decreases by 1 every time
Q: Would it be super slow to check if a vector is sorted at the beginning and/or after each sort operation?
A1: Adds an O(N) step for each check
A2: It would be an extra O(n) operation at each step, you could do it but it would be extra work
Q: Would a pivot that divides elements in 2 be the fastest algorithm?
A1: Yes, exactly (the median is the best pivot)
Q: What are the signals to pay attention to to pick a good algorithm for a specific situation?
A1: live answered
Q: why does shell sort take so long with the few unique?
A1: live answered
A2: Seems like the animation might be broken
Q: Ooh what are bubble sort and shell sort?
A1: Lots of good algorithms to look into outside of class!
Q: And heap sort?
Q: Which sort is used by the default sort function in C++?
A1: live answered
Q: We used bubble sort (up/down) the other day with the binary heap, no?
A1: We didn’t exactly do bubble sort – we did bubble operations but we weren’t sorting the array
Q: How come they can’t figure out the complexity using Timed Test :)
Q: on CS106M page?
A1: cs106m.stanford.edu
A2: cs106m.stanford.edu