Sorting
Selection Sort
1. Algorithm:
- Split the array in two parts such that:
- the first part of the array is sorted.
- the second part contains elements
than the elements in the first part.
- Pick the smallest element from the second part.
- Swap it with the element on the position right after the sorted part.
- The first part is initially empty.
![](/2020/04/14/ds5/selection_sort.png)
Pseudocode:
1 | void selection_sort(int[] arr){ |
2. Time Complexity
Heap Sort
1. Algorithm:
- Build a (min) heap1 from the elements in the array.
- Then, do the following n-times:
- Pick the smallest element from the heap (root).
- Place it on the position right after the sorted part.
2. Time Complexity:
- Building the heap is in
. - Deleting the minimum from a heap is in
- we do this n-times: .
Pseudocode:
1 | void heap_sort(int[] arr){ |
Theoretically best
No comparison-based sorting algorithm has the Worst Case time complexity better than
Merge Sort
1. Idea:
- Split the array into two halves.
- Sort each of them recursively.
- Merge the sorted parts.
2. Merging two sorted arrays a[-]
and b[-]
efficiently
Pseudocode:
1 | void mergesort(int[] arr){ |
3. Time Complexity
Quick Sort
1. Idea
- Select an element of the array, which we call pivot.
- Partition the array so that the "small entries" (
pivot) are on the left, then the pivot, then the "large entries" ( pivot). - Recursively (quick) sort the two partitions.
2. Pseudocode
1 | void quicksort(int[] arr){ |
3. Partitioning array arr
Idea
- Choose a pivot
p
fromarr
. - Allocate two temporary arrays:
tmpLE
andtmpG
. - Store all elements less than or equal to
p
totmpLE
. - Store all elements greater than
p
totmpG
. - Copy the arrays
tmpLE
andtmpG
back toarr
and return the index ofp
inarr
.
4. Time Complexity
Best Case:
Worst Case:
Average Case:
5. Pivot-selection strategies
You should consider the case that your array is already sorted, or that portions are.
It can be shown that if all permutations are equally likely, then regardless of pivot selection strategy, quicksort takes
Choose pivot as:
- the middle entry (good for sorted sequences, unlike the leftmost-strategy).
- the median of the leftmost, rightmost and middle entries.
- use Quickselect to choose median in
. - a random entry (there is 50% chance for a good pivot).
Min heap - The priority of every node is lower than that of its children.↩