2.3.3 Sorting algorithms

Question 1

What are the sorting algorithms you need to know?

Answer 1

• Bubble sort
• Insertion sort
• Merge sort
• Quick sort

Question 2

Explain bubble sort

Answer 2

• Compares first pair of items
• Swaps them if they arent in order
• Compares next pair
• After one pass, largest/smallest is guranteed to be in corrrect position

Question 3

What are the time and space complexities of bubble sort?

Answer 3

• Time complexity: O(n^2)
• Space complexity: O(1)

Question 4

What is insertion sort?

Answer 4

• Places elements into sorted sequence
• Each iteration places one element into its correct position

Question 5

What are the time and space complexities for insertion sort?

Answer 5

• Time complexity: O(n^2)
• Space complexity: O(1)

Question 6

Explain merge sort

Answer 6

• Divide and conquer
• List is divided into parts until sublists of length 1 are obtained
• Sublists are grouped back together
• Final group is sorted

Question 7

What are the time and space complexities of merge sort?

Answer 7

• Time complexity: O(n log n)
• Space complexity: O(n)

Question 8

Explain quick sort

Answer 8

• Select middle element as pivot
• Place elements smaller than the pivot to its left and elements larger to its right
• Select pivot from each sublist
• Repeat until every item has been selected as a pivot

Question 9

What are the time and space complexities for quick sort?

Answer 9

• Time complexity: O(n^2)
• Space complexity: O(log n)