-
Notifications
You must be signed in to change notification settings - Fork 4
Sorting Fun
Kaelyn H. edited this page Dec 15, 2013
·
8 revisions
- Page numbers indicate where in the textbook (Data Structures: Abstraction and Design Using Java) the following sorts were talked about in.
- Sorts an array by making several passes through the array, selecting the next smallest item in the array each time, and placing it where it belongs in the array.
- See it in action @ http://www.youtube.com/watch?v=Ns4TPTC8whw
- Sorts by comparing adjacent array elements and then exchanges their values if they are out of order.
- The smaller values bubble up to the top of the array (toward the first element), while the larger values sink to the bottom of the array, hence the name.
- This sort works best when an array is nearly sorted to begin with.
- The worst case occurs when the array is inverted (elements are in descending order).
- Worst Case # of comparisons: O(n^2)
- Worst Case # of exchanges: O(n^2)
- The best case occurs when the array is already sorted.
- Best Case # of comparisons: O(n)
- Best Case # of exchanges: O(1)
- Performance is usually worst than selection sort
- See it in action @ http://www.youtube.com/watch?v=lyZQPjUT5B4
- Sorts by starting off with a subarray consisting of the first element only. Then, inserts the next element into the subarray into its proper ordered state. Continues this until the sort has gone through the entire array and thus the subarray has become the sorted version of the original array.
- No exchanges.
- Worst Case # of Comparisons: O(n^2)
- The best case occurs when the array is already sorted.
- Best Case # of Comparisons: O(n)
- See it in action @ http://www.youtube.com/watch?v=ROalU379l3U
- Sorts by creating initial subarrays with only 2-3 elements, and apply insertion sorts on those subarrays. After each collection of subarrays is sorted, a new collection of subarrays with approximately twice as many elements as before will be sorted. THe last step is to perform an insertion sort on the entire array, which has been presorted by the earlier sorts.
- Utilizes a divide-and-conquer strategy.
- A type of insertion sort with a better performance.
- See it in action @ http://www.youtube.com/watch?v=CmPA7zE8mx0
- Recursively splits the data into two halves (i.e. subsequences) until the subsequence contains only a single data item (i.e. singleton subsequence). Now, recursively merge these subsequences back together preserving their required order (i.e. ascending or descending order).
- See it in action @ http://www.youtube.com/watch?v=XaqR3G_NVoo
- See it in action @ http://www.youtube.com/watch?v=6NB0GHY11Iw
- Sorts by given an array with a first and last element, quicksort rearranges this array into two parts so that all the elements in the left subarray are less than or equal to a specified value (called the pivot) and all the elements in the right subarray are greater than the pivot.
- See it in action @ http://www.youtube.com/watch?v=ywWBy6J5gz8
| Sort | Best | Worst | Average |
|---|---|---|---|
| Selection | O(n^2) | O(n^2) | O(n^2) |
| Bubble | O(n) | O(n^2) | O(n^2) |
| Insertion | O(n) | O(n^2) | O(n^2) |
| Shell | O(n^7/6) | O(n^5/4) | O(n^2) |
| Merge | O(n log n) | O(n log n) | O(n log n) |
| Heapsort | O(n log n) | O(n log n) | O(n log n) |
| Quicksort | O(n log n) | O(n log n) | O(n^2) |