• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/14

Click to flip

Use LEFT and RIGHT arrow keys to navigate between flashcards;

Use UP and DOWN arrow keys to flip the card;

H to show hint;

A reads text to speech;

14 Cards in this Set

  • Front
  • Back

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?

Units of computation:



  • 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.


  • 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.

Specify the computational problem of sorting in ascending order.

Bubble sort:


 


Sketch the state of the list after the third iteration of the outer loop is complete.

Bubble sort:



Sketch the state of the list after the third iteration of the outer loop is complete.

Comparing and swapping from item 0 to 8 in the list, the third iteration of the outer loop leaves the list in the state in the diagram.

Comparing and swapping from item 0 to 8 in the list, the third iteration of the outer loop leaves the list in the state in the diagram.

Why does the bubble sort algorithm reduce the length of the section of the sequence over which the comparisons and swaps are made by 1 on each iteration of the outer loop.

The comparing and swapping process will always move the largest item to the end of the sequence (you can see this has happened in Figures 3.2(a) and (b)). It is therefore in its correct position, so there is no need for this item to be compared to, or swapped with, any of those remaining. So, the next iteration ignores this item and only considers the remaining unsorted portion of the sequence.

in a bubble sort, where in the sequence do sorted items accumulate?

Sorted items accumulate in their correct positions at the end of the sequence.

What is the key difference between basic bubble sort and the short version? Miller and Ranum use a variable exchanges as part of the guard of the outer loop. What is its purpose?


If no exchanges are made during an inner loop, this means the list must already be sorted. No further processing is necessary, and so the short bubble sort algorithm stops at this point, rather than continue with unnecessary iterations. The Boolean variable exchanges changes from false to true as soon as an exchange is made. If it has not changed to true during an iteration of the inner loop, the algorithm terminates.

Focus on the list item (99) marked in black highlight and the one marked in red (1). What do you think is the problem here?

Focus on the list item (99) marked in black highlight and the one marked in red (1). What do you think is the problem here?

The item 99 (a hare), located at the beginning of the list, makes its way speedily up to its place at the end. By contrast, 1 (a tortoise) is situated at the end of the list and crawls down to its correct place at the beginning with tortuous slowness.

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.

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 to 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.

Selection sort:


 


Sketch the state of the  list after the third iteration of the outer loop, and after the fourth iteration of the outer loop.

Selection sort:



Sketch the state of the list after the third iteration of the outer loop, and after the fourth iteration of the outer loop.

Three steps in the sorting of the list [17, 2, 5, 3, 13, 25, 9, 61, 16, 4, 18] are shown.


 


Sketch the state of the list after the third iteration of the outer loop, and after the fourth iteration of the outer loop.

Three steps in the sorting of the list [17, 2, 5, 3, 13, 25, 9, 61, 16, 4, 18] are shown.



Sketch the state of the list after the third iteration of the outer loop, and after the fourth iteration of the outer loop.

Write notes on the three algorithms (short, bubble sort, selection sort, and insertion sort) with respect to:


  • the number of comparisons
  • the number of alterations to the sequence (swaps or shifts)

each will make, in the best and worst cases. What is the complexity of each algorithm, based on the comparison as the unit of computation? How do the complexities compare?

Before we start, let’s note that the best case for each of the three algorithms will be when the sequence is already sorted. The worst case for all three will be when the sequence is sorted, but in reverse order, with the smaller elements at the end.


With this in mind, let’s take each of the three algorithms in turn.



  • Short bubble sort

In ordinary bubble sort, as we stated above, the outer loop makes n − 1 passes over the sequence of n items. The length of the sublist processed on each pass (let’s call this length p) diminishes by 1 on each pass. And on each pass p − 1 comparisons are made by the inner loop. On the first pass, p = n, so n − 1 comparisons are made. On the second pass, p reduces by 1, so n − 2 comparisons are made. The process continues until p is 1, so the algorithm will make (n − 1) + (n − 2) + ⋯ + 1 = ½n2 − ½n comparisons.


However, as we’ve already noted, the short bubble sort algorithm will stop as soon as the sequence is sorted. Thus, in the best case (where the sequence is already sorted), the outer loop will make only one pass, taking n − 1 comparisons (within a single execution of the inner loop) to establish this fact. In the worst case (the list is sorted in reverse order), the outer loop makes n − 1 passes, leading to a maximum of ½n2 − ½n comparisons, as outlined above.


In terms of the number of swaps, in the best case bubble sort will make no swaps (since the list is already sorted). In the worst case, every item will have to be swapped: every comparison will lead to a swap, so the number of swaps will equal the number of comparisons.


If we take our unit of computation to be the comparison, then, in the best case, the short bubble sort’s complexity is O(n). In the worst case, it is O(n2).



  • Selection sort

Selection sort also makes n − 1 passes over a sequence of n elements. Its inner loop makes exactly the same number of comparisons as bubble sort, so the worst-case maximum number of comparisons will be the same. If the comparison is again taken as the unit of computation, selection sort’s worst-case complexity is O(n2), and in the best case it is also O(n2). Selection sort is worse than bubble sort on a sorted sequence because it doesn’t seem to be possible to stop the outer loop when no swaps are made, as is done in short bubble sort.


However, since selection sort only makes one swap on each iteration of its inner loop, it will need to make a maximum of n − 1 swaps to move every item to its correct position.



  • Insertion sort

Insertion sort works by placing items, one by one, into their correct positions in a sorted partition maintained at the start of the sequence. The correct position for an item is determined by comparing it with the items in the sorted partition and this requires a total of ½n2 − ½n comparisons, as with bubble and selection sorts, in the worst case, and only n − 1 comparisons in the best case.


However, insertion sort does not work by exchanging elements, but by shifting them. Whatever value is already in the slot to which an item is shifted is overwritten, rather than preserved and moved to a new place. Miller and Ranum note that this only takes one third of the computational effort of swapping.


Once again, taking the unit of computation to be the comparison, in the best case, then, the insertion sort’s complexity is O(n). In the worst case, it is O(n2).



Short bubble sort is clearly the worst algorithm here. It makes as many comparisons as the other two, and generally makes many more swaps than the insertion or selection sorts.


Selection sort and insertion sort: in the worst case, both algorithms make the same number of comparisons as short bubble sort.


Insertion sort, working by shifting elements rather than swapping them, may be more efficient in practice. But in the end, with comparison as the unit of computation, all three algorithms have similar worst-case complexity of O(n2).

Basically, why are bubble sort, insertion sort and selection sort all O(n2)?

All three algorithms use one loop nested inside another. Thus, we have to multiply the number of computational steps, as in the analysis you encountered in Reading 2.6 of Unit 2