bubble sort vs quick sort

• bubble sort vs quick sort

http://www.youtube.com/watch?v=vxENKlcs2Tw
bubble sort compares every adjacent element(something next to it) and moves the biggest element forward

(if you are supposed to list numbers in descending order)
the same operation is run on the remaining part of the elements

• Bubble sort

Bubble 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.
The algorithm gets its name from the way smaller elements "bubble" to the top of the list. 
Because it only uses comparisons to operate on elements, it is a comparison sort. 
Although the algorithm is simple, most other algorithms are more efficient for sorting large lists
Bubble sort has worst-case and average complexity both ?(n2), where n is the number of items being sorted

There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). 
Even other O(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort
Therefore, bubble sort is not a practical sorting algorithm when n is large.
Performance of bubble sort over an already-sorted list (best-case) is O(n).

 Large elements at the beginning of the list do not pose a problem, as they are quickly swapped. 
 Small elements towards the end, however, move to the beginning extremely slowly.
 This has led to these types of elements being named rabbits and turtles, respectively



 Pseudocode implementation

 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

many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort


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

• Code snippets

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;
                  }
            }                
      }
}
C++

void bubbleSort(int arr[], int n) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - 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