Sorting Flashcards
What is the purpose of Bubble Sorting?
Repeatedly compare and swap adjacent elements in an array until the array is sorted.
What is the largest number of swaps performed by Bubble Sort per item in the list?
The largest number of swaps performed by Bubble Sort per item in the list is n-1, where n is the size of the list.
What is the best case and worst case complexity of bubble sorting? Explain
The best case and worst case time complexity of Bubble Sort are O(n) and O(n^2), respectively. The best case occurs when the list is already sorted, and the algorithm only needs to make one pass through the list. The worst case occurs when the list is in reverse order, and the algorithm needs to make n-1 passes through the list.
What is the result of applying one iteration (list traversal) of Bubble Sort if one wants to sort the list in increasing order and starts from the left?
- Example: [5, 20, -5, 10, 3]
- Example: [-5, -20, -5, -10, 3]
- [5, -5, 10, 3, 20]
- [-20, -5, -10, -5, 3]
When does Bubble Sort stop? Describe at least one way to improve Bubble Sort.
Bubble Sort stops when the list is sorted, which means that no swaps are made in the last pass through the list. One way to improve Bubble Sort is to use a flag variable to check if any swaps were made in the last pass. If no swaps were made, then the list is already sorted and the algorithm can stop. This can reduce the number of unnecessary passes through the list. Another way to improve Bubble Sort is to use a variable to keep track of the last position where a swap was made. This can reduce the size of the unsorted portion of the list, since all the elements after the last swap are already in their final positions.
What does it mean for a sorting algorithm to be incremental?
An algorithm is incremental if it does not need to re-compute everything after a small change (not make more iterations)
Is Bubble Sort incremental? Why and when?
Bubble Sort is incremental when an element is appended to the start of the list, (Bubble sort II).
What does it mean for a sorting algorithm to be stable? Why?
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input data set. Stability is mainly important when we have key-value pairs with duplicate keys possible (like people’s names as keys and their details as values). And we wish to sort these objects by keys. Stability is also useful when we want to sort a collection on multiple keys, such as first by name and then by age.
Is Bubble Sort stable?
Yes, but using => instead of > makes it non-stable
What is the main idea of Selection Sort?
The main idea of Selection Sort is to find the minimum element in the unsorted portion of the array and swap it with the first unsorted element. Repeat this process until the array is sorted.
What is the best case and worst case complexity of Selection Sort? Explain?
The best case and worst case time complexity of Selection Sort are both O(n^2), where n is the size of the list. This is because the algorithm always needs to make n-1 passes through the list, and each pass requires n-i comparisons, where i is the current pass number.
What is the result of applying one iteration of SelectionSort if one wants to sort the list in increasing order and starts from the left?
- Example: [5, 20, -5, 10, 3]
- Example: [6, 5, 4, 3, 2, 1]
One iteration of Selection Sort is to find the minimum element in the unsorted portion of the list and swap it with the first unsorted element. An example of applying one iteration of Selection Sort to sort the list [5, 20, -5, 10, 3] in increasing order is:
- Find the minimum element in the unsorted portion of the list, which is -5.
- Swap -5 with the first unsorted element, which is 5. The list becomes [-5, 20, 5, 10, 3].
- The first iteration is done, and the smallest element -5 is in its final position.
An example of applying one iteration of Selection Sort to sort the list [6, 5, 4, 3, 2, 1] in increasing order is:
- Find the minimum element in the unsorted portion of the list, which is 1.
- Swap 1 with the first unsorted element, which is 6. The list becomes [1, 5, 4, 3, 2, 6].
- The first iteration is done, and the smallest element 1 is in its final position.
Is Selection Sort stable?
No
Is Selection Sort incremental?
No
What is the main idea of Insertion Sort?
The main idea of Insertion Sort is to divide the array into two parts: a sorted part and an unsorted part. Initially, the sorted part contains only the first element of the array, and the unsorted part contains the rest of the elements. Then, one by one, take each element from the unsorted part and insert it into its correct position in the sorted part. Repeat this process until the array is sorted.
