Differences between current version and revision by previous author of BubbleSort.
Other diffs: Previous Major Revision, Previous Revision, or view the Annotated Edit History
| Newer page: | version 4 | Last edited on Sunday, August 24, 2003 2:08:19 pm | by AristotlePagaltzis | |
| Older page: | version 1 | Last edited on Sunday, August 24, 2003 11:57:41 am | by StuartYeates | Revert |
@@ -1,22 +1,28 @@
-[BubbleSort] is the cannonical example of an inefficient SortingAlgorithm
.
+[BubbleSort] is the cannonical example of an inefficient sorting [Algorithm]
. It works by moving through the array comparing each element with the next element and swapping them if they're in the wrong order. In each iteration, it moves the next largest element into the next last position, stopping one position earlier than previously. An example:
-It works by moving through the array comparing each element with the next element and swapping them if they're in the wrong order. The processes is repeated until all the elements are in order
.
+||After Iteration||||Element Nr
.
+|Outer|Inner||1|2|3
+||^Initial state | D | B | C | A
+| 1 | 1 | [[B] | [[D] | C | A
+| 1 | 2 | B | [[C] | [[D] | A
+| 1 | 3 | B | C | [[A] | [[__D__]
+| 2 | 1 | [[B] | [[C] | A | D
+| 2 | 2 | B | [[A] | [[__C__] | D
+| 3 | 1 | [[A] | [[__B__] | C | D
-The source code looks a little like:
+The brackets denote the elements which were compared (and possibly swapped) during an iteration. Bold elements have reached their final position. As you can see, the next largest element falls into the next last position after each iteration.
+
+A sample implementation might be
int [] array;
- boolean sorted
= false
;
- while(!sorted
) {
- sorted = true;
- for (int i
;i < array.length-1
;i++)
- if (array[[i
]>array[[i
+1]) {
- sorted = false;
- int tmp =
array[[i
];
-
array[[i] = array[[i
+1];
- array[[i+1] = tmp;
- }
+ for(int i
= array.length - 2
; ; i--
) {
+ for(int j =
; j <
i ; i++)
+ if (array[[j
]>array[[j
+1])
+ swap(
array[[j
],
array[[j
+1])
;
}
-BubbleSort does have some good features:
-# If
you know that ``
a'' unsorted elements have been prefixed to an otherwise sorted list then the list and
be sorted in time
O(na
).
-# [BubbleSort] can use fine-grained [Synchronisation] to sort a list while other threads or processes are updating it or changing it
+It is obvious that, with ''n'' being the array's length, the inner loop will total ''(n / 2) * (n - 1)'' iterations - which is ''(n^2 - n) / 2''. Therefor, in [BigONotation], the complexity of BubbleSort is ''O(n^2)''. Clearly, its performance will degrade quickly as the array grows.
+
+
BubbleSort does have some good features, though
:
+# The weakness of BubbleSort is that it never shuffles non-adjacent elements - that's why it's so slow. But it also means that never degrades the order in its input, so you can take shortcuts if
you know your list is nearly sorted. F.ex, if ''
a'' unsorted elements have been prefixed to an otherwise sorted list then the outer loop can
be aborted early, reducing the complexity to ''
O(a n
)''. For small values of ''a'', this will likely be less than the ''O(n log n)'' required f.ex by a full QuickSort run
.
+# [BubbleSort] can use fine-grained [Synchronisation] to sort a list while other threads or processes are updating it or changing it.
