2.3.3 Sorting algorithms Flashcards
1
Q
What are the sorting algorithms you need to know?
A
- Bubble sort
- Insertion sort
- Merge sort
- Quick sort
2
Q
Explain bubble sort
A
- 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
3
Q
What are the time and space complexities of bubble sort?
A
- Time complexity: O(n^2)
- Space complexity: O(1)
4
Q
What is insertion sort?
A
- Places elements into sorted sequence
- Each iteration places one element into its correct position
5
Q
What are the time and space complexities for insertion sort?
A
- Time complexity: O(n^2)
- Space complexity: O(1)
6
Q
Explain merge sort
A
- Divide and conquer
- List is divided into parts until sublists of length 1 are obtained
- Sublists are grouped back together
- Final group is sorted
7
Q
What are the time and space complexities of merge sort?
A
- Time complexity: O(n log n)
- Space complexity: O(n)
8
Q
Explain quick sort
A
- 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
9
Q
What are the time and space complexities for quick sort?
A
- Time complexity: O(n^2)
- Space complexity: O(log n)
