week 4 - What is sorting? - Naive Sorting Flashcards
What is sorting?
Sorting is the process of placing elements from a collection in some kind of order.
What is the connection between sorting and ordering?
Central to sorting is the concept of ordering: it must be possible to say whether, of any two values, one is larger or smaller than the other.
Two different units of computation are commonly considered when measuring the complexity of a sorting algorithm. What are they?
a) Comparison of one item with another (whether this one is larger or smaller than that one) is the most common unit of computation used in measuring the complexity of a sorting algorithm.
b) If, during sorting, two values are found to be out of order, they are swapped. This can be expensive computationally, and so a second possible unit of computation is the swap: exchanging the positions of two items.
What the devil is a bubble sort?
Each pair of a list is compared and they are swapped if necessary, the ‘largest’ term bubbles to the ‘top’ or ‘end’ of the list after each pass, so that n-1 passes are necessary to complete a bubble swap.
What is a short bubble?
A bubble pass has the benefit that it can detect when a list has been sorted early, it can therefore stop prematurely.
What is the Big O Notation for a bubble swap, why?
it is n^2, this is because the sum of the first n integers of a list is 0.5(n^2) + 0.5(n)
In what respects are bubble sort and selection sort similar?
Both algorithms make multiple passes over the sequence being processed, accumulating sorted items at the end of the sequence.
What is selection sort?
Selection sort iterates through alist n-1 times, each time finding the largest item in the list and moving it to the ‘next fill spot’ initially the last item in the list which then moves down 1 with each iteration.
How does the inner loop processing carried out by selection sort differ from that in bubble sort?
Bubble sort bubbles larger items up towards the end of the sequence in a series of comparisons and swaps within the unsorted portion. Selection sort processes the whole unsorted portion to find the largest item and then moves it into place in a single swap.
What are the key similarities and differences between insertion sort and the two algorithms we’ve discussed: bubble sort and selection sort?
Insertion sort, like bubble sort and selection sort, involves two nested loops. It also processes a partition of the sequence that diminishes in size by 1 on each iteration of the outer loop. By contrast, though, the inner loop takes the first item of the unsorted part of the list. It then successively shifts items in the sorted part to the right until it finds the correct place for the item from the unsorted part and inserts it there. Sorted items thus accumulate at the beginning of the sequence. The use of shifts instead of exchanges also means that fewer assignments are required, somewhat reducing the number of processing steps. Insertion sort does well on benchmark studies, though it has the same worst-case performance of O(n2) as bubble sort and selection sort
What is in-place sorting?
no other list needs to be created; the items are moved around within the original list. all of them depend on two loops, one embedded inside the other.
