Sorting Algorithms

Question 1

Bubble Sort

Answer 1

Bubble Sort: Makes comparisons & swaps between pairs of elements
- Largest element in unsorted part “bubbles” to the top of data w/ each iteration
- Starts at 1st element in array & compares to 2nd
- If in wrong order, algorithm swaps the pair. Otherwise, moves on
- Process repeated for every adjacent pair of elements, until end of array is reached
- This is 1 pass of the algorithm, n elements = n passes
- O(n^2)

Question 2

Insertion Sort

Answer 2

Insertion Sort: Places elements into sorted sequence
- Stars at 2nd element in input, compares it to element to its left
- If the 2 elements are in wrong order, smaller element is placed in lowest position
- 3rd element then selected, inserted into correct position in the sorted portion of the input to its left
- Continues until last element is inserted into correct position, resulting in fully sorted array
- Same time complexity as bubble sort, O(n^2)

Question 3

Merge Sort

Answer 3

Merge Sort: “Divide & conquer” algorithm formed from 2 functions
- MergeSort: Divides its input into 2 parts & recursively calls MergeSort on each of those 2 parts until they are of length 1
- Merge: Puts groups of elements back together in special way, ensuring that final group produced is sorted
- More efficient, worst case time complexity of O(n logn)

Question 4

Quick Sort

Answer 4

Quick Sort: Works by selecting an element, often central element (called a pivot), & dividing the input around it
- Elements smaller than pivot are placed in list to the left of pivot & others are placed in list to the right
- Process repeated recursively on each new list until all elements are old pivots themselves or form a list of length 1
- Time complexity is O(n^2)