Bubble Sort

Searching

Introduction

Problem (Sorting)
Given: a collection of elements, $A = {a_1, a_2, . . . , a_n}$
Output: A permuted list of elements $a_1’,a_2’,…,a_n’$ according to a specified order

• Simple, but ubiquitous problem
• Fundamental operation for data processing
• Large variety of algorithms, data structures, applications, etc.
Sorting algorithms are usually analyzed with respect to:
• Number of comparisons in the worst, best, average cases
• Swaps
• Extra memory required
Other considerations:
• Practical considerations: what ordered collections (Lists, arrays, etc.) are supported by a language
• Most languages provide standard (optimized, well-tested) sorting functionality; use it!
Sorting stability: A sorting algorithm is said to be stable if the relative order of “equal” elements is preserved.
• Example: suppose that a list contains $10,2_a,5,2_b$; a stable sorting algorithm would produce $2_a,2_b,5,10$ while a non-stable sorting algorithm may produce $2_a,2_b,5,10$
• Stable sorts are important for data presentation (sorting by two columns or categories)
• Stability depends on inequalities used and behavior of algorithms

Throughout, we will demonstrate examples of sorting based on the array in table (Unsorted Array).

4	12	8	1	42	23	7	3

Bubble Sort

• Pass through the list and swap individual pairs of elements if they are out of order
• At the end of the first pass, the maximal element has \bubbled up” to the end of the list
• Repeat this process n times

Pseudocode

Analysis

• Elementary operation: comparison
• Performed once on line 3
• Inner loop (line 2 executed n - i times
• Outer loop (line 1) executed n times
• In total: $$\sum_{i=1}^n \sum_{j=2}^{n-i+1} 1 = \sum_{i=1}^n (n-i)=n^2-(\sum_{i=1}^n i)=\frac{n^2-n}{2}$$
• Bubble sort is $O(n^2)$

Code Samples

Code Sample 9: Java Bubble Sort for integers

public static void bubbleSort (int array []) {
  int n = array.length ;
  int temp = 0;
  for (int i = 0; i < n; i++) {
    for(int j = 1; j < (n-i); j++) {
      if(array[j-1] > array[j]) {
      temp = array[j-1];
      array[j-1]= array[j];
      array[j]= temp ;
      }
    }
  }
}