You are invited to Log in or Register a free Frihost Account!

selection, bubble; loop invariant: Python

What is the best way to sort a list? It appears 'divide and conquer' may be, but lecture tutorial looked at Selection and Bubble sorts.

Selection Sort
is based on a technique called Loop Invariant

Loop Invariant splits (in this case) a list into prefix and suffix.
The prefix is sorted, the loop then runs through the suffix.
At the end of the loop, the prefix has increased in size and is ready to run through the (now smaller) suffix, and loops until it is all prefix.

In selection sort, the program checks index 0, and compares it with all the other numbers, looking for the lowest. If there is a lower one, after checking all numbers, it swaps it.

Thus, the position index 0 is now the lowest.

Next, look at index 1, and compare etc.

Loop through until getting to the end.

Bubble sort

is another variant way to sort. It kind of 'bubbles' up the chain, swapping, and kind of working backwards to the selection sort.

It runs through the list, first comparing 0 and 1, then 1 and 2, then 2 and 3 and so on, swapping pairs whose neighbour is larger, til it gets to the end.
It runs through the list again and again until the list has been checked the same number of times as the length of the list, or until it is complete.

Each time it runs through, the last number in the list will be the largest, the next time both the last and the second last etc.


Both these ways are O(n^2)

Which is better?

Selection sort is better. Because there are less swaps, it only swaps once each time through, whereas bubble sort is swapping often.

On the other hand, bubble sort can be cut short when list is sorted, without needlessly running through a sorted list.

It is not so clear to me why selection sort is so much better, seeing as they are both n^2, nevertheless that is apparently the verdict. I guess for each 1 action in selection sort, there are often 2 actions in bubble sort.

In any case, there is another way which is better again.

0 blog comments below

© 2005-2011 Frihost, forums powered by phpBB.