Bubblesort

• Algorithms Lesson 1: Bubblesort

http://www.youtube.com/watch?v=P00xJgWzz2c&feature=relmfu

• Bubble sort - algorithm and analysis

http://www.youtube.com/watch?v=PdmyYqO_59s&feature=related

• Bubble sort

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order

Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted

procedure bubbleSort( A : list of sortable items )
   repeat    
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure


http://en.wikipedia.org/wiki/Bubble_sort

• Bubble Sort

Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes.

Java

public void bubbleSort(int[] arr) {
      boolean swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < arr.length - j; i++) {                                      
                  if (arr[i] > arr[i + 1]) {                        
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }              
      }
}

http://www.algolist.net/Algorithms/Sorting/Bubble_sort