Sorting

Question 1

Selection Sort

Answer 1

Repeatedly select the smallest remaining item. First finds the smallest item in the array and exchanges it with the first entry (itself if the first entry is already the smallest). Then, find the next smallest item and exchange it with the second entry. Continue in this way until the entire array is sorted.

Question 2

Selection Sort Run Time

Answer 2

n**2 compares and n exchanges. Does not depend on initial order

Question 3

Insertion Sort

Answer 3

Consider elements one at a time, inserting each into its proper place among those already sorted. We need to make space to insert the current item by moving larger items one position to the right, before insertion the current item into the vacated position. Items to the left of current index are sorted, but not in their final position, as they may have to be moved to make room for smaller items.

Question 4

Insertion Sort Run Time

Answer 4

Depends on initial order. Worst case is n2 compares and n2 exchanges, best case is n-1 compares and 0 exchanges. Average is n**2 for both. Best for small or partially sorted arrays.

Question 5

Partially Sorted Arrays

Answer 5

Number of inversions in an array is less than a constant multiple of the array length.

Question 6

Shellsort

Answer 6

Extension of insertion sort that allows exchangers of array entries that are far apart, to produce partially sorted arrays that can be efficiently sorted by insertion sort. Creates h-sorted arrays or h independent sorted subsequences, interleaved together.

Question 7

Mergrsort

Answer 7

To sort and an array, divide it into two halves, sort the two halves (recursively), and then merge the results. Guarantees to sort an array in n log n, but uses n space.