01:198:111 Lecture Notes - Lecture 26: Insertion Sort, Merge Sort, Selection Sort
3 Dec 2018
School
Department
Course
Professor
01:198:111 verified notes
26/28View all
❖ Fast Sorting Algorithms
➢ Basic Sorting Algorithms
■ Insertion Sort”
● Best Case: O(n) - linear
● Worst Case: O(n^2) - quadratic
● Extra Array? No
■ Selection Sort
● Best Case: O(n^2)
● Worst Case: O(n^2)
● Extra Array? No
■ Overall, insertion sorting is generally the sorting method that one should
always use
➢ Importance of sorting
■ Java has its own method for sorting programs
● Arrays.sort(a)
◆ This will result in array a being sorted
◆ Java here is using the mergesort instead of selection and
insertion sorting
➢ Merge Sorting
■ Goal
● Given two sorted arrays, merge them into a single sorted array
◆ E.g. array a is [ 1,3,6] and array b [2,5,8]
➢ Both arrays are sorted
➢ How would we create an array merging them?
■ Create array of length of both of the lengths
of the arrays combined
● So array c.length=6
■ Now we create a pointer for each array, i
and j for a and b respectively, and k for
array c
■ Compare a[i] and b[j] and whichever one is
lower, in this case a[i] insert that into c[k]
and increment k and i.
■ Repeat the comparisons and insertions until
the array is sorted
■ What if the array is not sorted?
● Well you can break the array into smaller and smaller mini
arrays(even arrays of size 1), and then merge those into bigger
sorted arrays until you have one fully sorted array
■ How efficient is this program?
● Best Case: log n
● Worst Case:n log n
◆ What is n log n?
Document Summary
Overall, insertion sorting is generally the sorting method that one should always use. Java has its own method for sorting programs. This will result in array a being sorted. Java here is using the mergesort instead of selection and insertion sorting. Given two sorted arrays, merge them into a single sorted array. E. g. array a is [ 1,3,6] and array b [2,5,8] Create array of length of both of the lengths of the arrays combined. Now we create a pointer for each array, i and j for a and b respectively, and k for array c. Compare a[i] and b[j] and whichever one is lower, in this case a[i] insert that into c[k] and increment k and i. Repeat the comparisons and insertions until the array is sorted. Well you can break the array into smaller and smaller mini arrays(even arrays of size 1), and then merge those into bigger sorted arrays until you have one fully sorted array.
