Sorting and Searching Flashcards
Selection Sort: Operation
Find the smallest element in a and exchange it with a[0]. Repeat the process with the subarray a[1]…a[n-1]… then sort a[n-2] and a[n-1] at the end.
Selection Sort: Passes to sort the array
An array of n elements is sorted after n-1 passes.
Selection Sort: Elements sorted after k passes
After the kth pass, the first k elements are in their sorted positions.
Selection Sort: Worst Case
Selection Sort always requires the same number of comparisons/moves
Selection Sort: Best Case
Selection Sort always requires the same number of comparisons/moves
Insertion Sort: Operation
The array consists of sorted and unsorted portions. Insertion sort moves elements from the unsorted subarray to their correct positions in the sorted subarray, moving elements in the sorted subarray as necessary.
Insertion Sort: Passes to sort the array
An array of n elements is sorted after n-1 passes.
Insertion Sort: Elements sorted after k passes
The elements in a[0]..a[k] are sorted with respect to each other (though not necessarily in their final positions).
Insertion Sort: Worst Case
The array is sorted in reverse order (maximum possible number of comparisons and moves).
Insertion Sort: Best Case
The array is already sorted in increasing order (each pass involves one comparison that confirms that the sort order is correct).
Mergesort: Operation
Mergesort the left and right halves of an array, then merge the two sorted lists. In doing this, n subarrays of length 1 are created and then recursively merged to form the final sorted array.
Mergesort: Disadvantages
Mergesort requires a temporary array of length n to sort an array of length n, so it may not be space-efficient.
Mergesort: Worst Case
The performance of mergesort is not affected by the initial ordering of elements in the array.
Mergesort: Best Case
The performance of mergesort is not affected by the initial ordering of elements in the array.
Sequential Search: Operation
Start at the first element and compare the key to each element. If the list is known to be sorted, the search could be stopped early if the key is less than the current element.
Sequential Search: Best Case
The key is in the first slot.
Sequential Search: Worst Case
The key is in the last slot or not in the array.
Sequential Search: Average Case
There are n/2 comparisons.
Binary Search: Operation
Find the midpoint of the array at index k and compare it to the key. If the key is less than a[k], recursively search a[0]..a[k-1]. If it is greater than a[k], recursively search a[k+1]..a[n-1].
Binary Search: Preconditions
The array is sorted on the search key.
Binary Search: Best Case
The key is at the midpoint of the array (i.e. a[n/2]).
Binary Search: Worst Case
The key is not in the list or is at either end of a subarray (subarrays must continually be divided until a subarray of length 1 is found and tested).
