121 Week 16 - Sorting Algorithms Flashcards
Need for sorting algorithms
Most real world come in an unstructured, hard to use form. Sorting algorithms mean make the data easier/more efficient to work with.
Application of sorting algorithms
Ranking data (e.g., find top/bottom X results), searching data (e.g., sorting data so a binary search can be done on it)
Selection sort
2 arrays, input array and secondary sorted array.
Input array: holds the unsorted data.
Secondary sorted array an empty array of the same length as input array.
1. Find the lowest value in the input array and add into the next free space of sorted array
2. Remove the lowest value from input array
3. If input array is not empty, return to step 1.
4. If input array is empty, secondary sorted array will hold be the sorted version of input array.
In-place selection sort
1 array, input array. Has a pointer that starts by pointing at the first element in input array.
1. Find the lowest value in the input array and swap with the value at the pointer.
2. Increment the pointer by 1 to point to the next item in the array.
3. If the pointer does not point to the last item in the array, return to step 1.
4. If the pointer points to the last item, input array is sorted.
Selection sort correctness analysis
The algorithm is correct if:
for i = length -1, at the end of phase i the first i+1 entries of the array are sorted and contain the first i+1 values.
Selection sort time complexities
Worst case: O(n^2)
Best case: O(n^2)
Average case: O(n^2)
Insertion sort
2 arrays, input array and secondary sorted array.
Input array: holds the unsorted data.
Secondary sorted array an empty array of the same length as input array.
1. Retrieve the first value in input array and insert it into the secondary sorted array.
2. Retrieve the next value in input array and compare it to the last item in the secondary sorted array.
3. If it is less than the compared item, move down the secondary sorted array and compare again.
4. Repeat step 4 until the compared item is greater than the item to insert. At this point, insert the item into secondary sorted array at that point.
5. repeat from step 2 until all items have been inserted into secondary sorted array.
6. Once all items have been inserted, secondary sorted array holds the sorted version of the input array.
In-place insertion sort
1 array, input array.
Similar to regular insertion sort except you insert back into the input array and only compare the item you are inserting with already inserted items.
Insertion sort correctness analysis
The algorithm is correct if:
for i = length -1, at the end of phase i the first i+1 entries of the array are sorted
Insertion sort time complexities
Worst case: O(n)
Best case: O(n^2)
Average case: O(n^2)
Divide and conquer
Decomposing a problem into simpler sub problems of the same type. Then recursively solving the subproblems and combining the sub problems solutions to get a solution to the full problem.
Merge sort
- Recursively split up the array into subarrays until each subarray contains only 1 element.
- For all subarrays of the smallest size, merge 2 subarrays into 1 sorted array by inserting the smallest item from either array until both arrays have had all their items inserted.
- Repeat step 2 until all subarrays have been merged into a final sorted array.
How is merge sort a divide and conquer algorithm
The input array is split into equal halves (decomposition), sort the two subarrays independently (solve subproblems) then combine the sorted subarrays by merging to get an overall sorted array (combine solutions to get overall solution).
In-place merge sort
Cannot do merge sort in-place
Merge sort correctness analysis
Do not need to know. 121 Week 16 L2 notes have info in case.
Merge sort time complexities
Worst case: O(n log n)
Best case: O(n log n)
Average case: O(n log n)
Quick sort
1 array: input array
1. Set the pivot as the last item in the array.
2. Re-order the array so that all items lower than the pivot are to the left of the pivot and all items greater than the pivot are to the right of the pivot. The pivot is now in the correct place for the sorted array.
3. Repeat from step 2 but on a subarray of the items to the left of the pivot.
4. Repeat from step 2 but on a subarray of the items to the right of the pivot.
5. Input array is now sorted.
Quick sort in-place
Quick sort is always done in place.
Quick sort correctness analysis
Quick sort time complexities
Worst case: O(n log n)
Best case: O(n log n)
Average case: O(n^2)
