If you know anything about "Bubble Sorts" please leave it here, the teacher said, "Use bubble sort to sort numbers into decreasing numerical value." Then she started eating lunch and said we were on our own...LAME
hi
let me tell u what i know about bubble sort
Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list via the swaps.
at the end of each pass the largest element in the list will reach its final position.
the pseudocode for this is
function bubble_sort(list L, number listsize)
loop
has_swapped := 0 //reset flag
for number i from 1 to (listsize - 1)
if L[i] > L[i + 1] //if they are in the wrong order
swap(L[i], L[i + 1]) //exchange them
has_swapped := 1 //we have swapped at least once, list may not be sorted yet
endif
endfor
//if no swaps were made during this pass, the list has been sorted
if has_swapped = 0
exit
endif
endloop
endfunction
Analysis
Worst-case performance
Bubble sort has worst-case complexity O(n2) on lists of size n. To see why, note that each element is moved no more than one step each time. No element can be more than a distance of n - 1 away from its final sorted position, so we use at most n - 1 = O(n) operations to move an element to its final sorted position, and use no more than (n - 1)2 = O(n2) operations in the worst case.
However, on a list where the smallest element is at the bottom, each pass through the list will only move it up by one step, so we will take n - 1 passes to move it to its final sorted position. As each pass traverses the whole list a pass will take n - 1 = O(n) operations. Thus the number of operations in the worst case is also o(n2). We have a tight worst-case complexity bound of O(n2).
Best-case performance
When a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. This means the list is already sorted. Thus bubblesort will take O(n) time when the list is completely sorted. It will also use considerably less time if the elements in the list are not too far from their sorted places.
however this algorithm is not considered to be the most efficient algorithm.
hope this is helpful to you
64
