Bubble Sort | Chinese Rule of Eight

http://www.geeksforgeeks.org/bubble-sort/

“Bubble” up the largest number in the array. Once that’s done, we “Bubble” again to the array-1 for the next largest number. We keep doing it until we have “Bubbled” every number in the array.

Think of it as looping through the array and looking at each tuple. If a tuple is where element1 > element2, then we swap. This way, the largest element of this run will “Bubble” up to the end. (very right side).

Due to us checking every tuple, we need to makes sure we check from 1..length-1 and NOT 1..length:

(5 1) 4 2 8 –> [1 5] 4 2 8, Here, algorithm compares the first two elements, and swaps since 5 > 1.
1 (5 4) 2 8 –> 1 [4 5] 2 8, Swap since 5 > 4
1 4 (5 2) 8 –> 1 4 [2 5] 8, Swap since 5 > 2
1 4 2 (5 8) –> 1 4 2 [5 8], Now, since these elements are already in order (8 > 5), algorithm does not swap them.

As tuples, the last index should be
element[last-1], element[last]

Therefore, we only need to check from (index 0) to (< lastIndex-1) because it does not make sense at all to swap the very last element of the array to its next element because the next element does not exist. The last swap we do should be data[lastIndex-1], data[lastIndex]. That is why we give outer - 1 into bubbleUpLargest.

Example

Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Numerical example

Given: 6 8 0 7 6 4 3 1 5 10

We compare tuples, so we loop a total of length – 1 times.

[6 8] 0 7 6 4 3 1 5 10

is 6 > 8? no

6 [8 0] 7 6 4 3 1 5 10

is 8 > 0? yes, swap

6 0 [8 7] 6 4 3 1 5 10

is 8 > 7? yes, swap

6 0 7 [8 6] 4 3 1 5 10

is 8 > 6? yes, swap

6 0 7 6 [8 4] 3 1 5 10

is 8 > 4? yes, swap

6 0 7 6 4 [8, 3] 1 5 10

is 8 > 3? yes, swap

6 0 7 6 4 3 [8, 1] 5 10

is 8 > 1? yes, swap

6 0 7 6 4 3 1 [8, 5] 10

is 8 > 5? yes, swap

6 0 7 6 4 3 1 5 [8 10]

is 8 > 10? no

pass 1 finished, so as you can see 8 “bubbles up”, until it meets 10.

Since we’re done, we are confident that the last number is largest. 10 is done, so we move our lastIndex down and process the leftover array for the 2nd pass.

[6 0] 7 6 4 3 1 5 8 (10)

is 6 > 0? yes, swap

0 [6 7] 6 4 3 1 5 8

is 6 > 7? no, move on

0 6 [7 6] 4 3 1 5 8

is 7 > 6? yes, swap

0 6 6 [7 4] 3 1 5 8

is 7 > 4? yes, swap

0 6 6 4 [7 3] 1 5 8

is 7 > 3? yes, swap

0 6 6 4 3 [7 1] 5 8

is 7 > 1? yes, swap

0 6 6 4 3 1 [7 5] 8

is 7 > 5? yes, swap

0 6 6 4 3 1 5 [7 8]

is 7 > 8? no

pass 2 finished, so as you can see, 7 “bubbles up”.

0 6 6 4 3 1 5 7 (8) (10) so now, 8, 10 done. We need to process 0 6 6 4 3 1 5 7.

We move our lastIndex down and process the leftover array for the 3rd pass.

..this keeps going until all numbers are sorted from smallest to largest.

the bubble sort

function bubbleSort(intArray) {

var data = intArray.slice(0); // own copy

var numElements = data.length;

for (var lastIndex = numElements-1; lastIndex >=1; lastIndex--) {

console.log("---"+lastIndex+"---");

bubbleUpLargestViaTuples(data, lastIndex);

}

return data;

}

bubbleUpLargest

Then in here, we simply go through all the elements and do its swapping. Think of it as
looping through tuples and swapping them.

function bubbleUpLargestViaTuples(data, lastIndex) {

for (var inner = 0; inner < lastIndex; inner++) {

console.log("inner: " + inner);

console.log("data[inner]: " + data[inner]);

console.log("data[inner+1]: " + data[inner+1]);

if(data[inner] > data[inner+1]) {

swap(data, inner, inner+1);

}

The swap function is just a standard swap

function swap(arr, index1, index2) {

var temp = arr[index1];

arr[index1] = arr[index2];

arr[index2] = temp;

}

Worst-case performance O(n^2)
Best-case performance O(n)
Average performance O(n^2)

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex.

However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions).

Bubble sort should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.

source code

"user strict";

var dataArray = [6,8,0,7,6,4,3,1,5,10];

function swap(array, index1, index2) {

var temp = array[index1];

array[index1] = array[index2];

array[index2] = temp;

}