Sorting algorithms

Question 1

List all sorting algorithms (3)

Answer 1

1. Bubble sort
2. Merge sort
3. Quick sort

Extra: To understand how they work, watch videos. They are really helpful.

Question 2

Explain Bubble sort

Answer 2

Start from the beginning of the list. Compare two elements. If first element is larger then the second, switch their places. Proceed to the next pair of elements and repeat until the end.

Extra: after we finish each loop, meaning we went from first element to the last, we know the last element is the largest so we don’t have to compare against him anymore. After each loop we gain another one of those, set in stone elements.

Question 3

Explain Merge sort

Answer 3

Continue to divide the list in half until you are left with as many groups as there are elements. Then compare the first two elements and sort them. Continue with next two elements and so on. Then you will have groups of two elements. Join those together into groups of four and while doing that sort them. After final iteration of this method you will get sorted list.

Extra: To distinguish between Mergesort and Quicksort use the graphical representation. Remember the divide and conquer look of mergesort and it will be fine.

Question 4

Explain Quick sort

Answer 4

Start with a pivot (can be any element). On the left side of the pivot put all elements that are smaller than the pivot and on the right side put all elements that are the same or greater than pivot.

Continue this until you are left with one element groups. Then you can reconstruct the sorted list by looking at which side of the pivot the element is. Go from the bottom to the top.

Question 5

Merge sort: Time complexity

Answer 5

Best case: O(nlog(n))

Worst case: O(nlog(n))

Question 6

Quick sort: Time complexity

Answer 6

Base case: O(nlog(n))
Worst case: O(n^2)
Average case: O(nlog(n))