Bubble Sort
This is one of the most slowest algorithms for sorting, but it’s extremely well known because of its easy to implement nature. However as I wrote past Fridays there are lots of sorting algorithms which are really fast, like the quicksort or mergesort. In the case of bubble sort the nature of the algorithm is described in its name. The smaller element goes to the top (beginning) of the array as a bubble goes to the top of the water.
There is a cool animation showing how bubble sort works in compare to the quick sort and you can practically see how slow is bubble sort because of all the comparing.
Pseudo Code
Actually what I’d like to show you is how you can move from pseudo code to code in practice. Here’s the pseudo code from Wikipedia.
procedure bubbleSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length(A) - 2 inclusive do: if A[i] > A[i+1] then swap( A[i], A[i+1] ) swapped := true end if end for while swapped end procedure |
JavaScript Source
var a = [34, 203, 3, 746, 200, 984, 198, 764, 9]; function bubbleSort(a) { var swapped; do { swapped = false; for (var i=0; i < a.length-1; i++) { if (a[i] > a[i+1]) { var temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; swapped = true; } } } while (swapped); } bubbleSort(a); console.log(a); |
As a result you’ve a sorted array!
Is that correct?
no
after your while statement, use
it should help to compare the array.
Thanks, saved me the trouble of doing it myself. Quick note – should probably declare the temp variable as private outside of the loop:
var swapped, temp;
Hooray for “Bubble Sorting”. Here’s the way I write them in Javascript:
var arr = [9, 2, 1, 3, 0, 8, 7, 6, 5, 4, 10];
function bubbleSort(theArray) {
var i, j;
for (i = theArray.length – 1; i >= 0; i–) {
for (j = 0; j <= i; j++) {
if (theArray[j + 1] < theArray[j]) {
var temp = theArray[j];
theArray[j] = theArray[j + 1];
theArray[j + 1] = temp;
}
}
}
return theArray;
}
console.log(bubbleSort(arr));
Is this correct? I don’t think your sorting implementationg will work correctly.
var numbers = [7,623,53,1,582,928];
function bubbleSort() {
numbers.sort(function(a, b){return a-b});
console.log(numbers);
}
bubbleSort();
var arr = [1, 6, 9, 2, 10, 34, 66, 3];
for(var i = 0; i < arr.length – 1; j++) {
for(var j = 1; j arr[j]) {
var t = arr[j];
arr[j] = arr[j – 1];
arr[j – 1] = t;
}
}
}
console.log(arr);