Sorting

Introduction

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

  • Simple, yet 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, and average cases
  • Swaps (data movement)
  • Extra memory required (space complexity)

Other considerations:

  • Practical considerations: which 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 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 might produce $2_b, 2_a, 5, 10$.
  • Stable sorts are important for data presentation (e.g., sorting by two columns or categories).
  • Stability depends on the inequalities used and the specific behavior of the algorithm’s logic.

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

4 12 8 1 42 23 7 3

Bubble Sort

Bubble Sort

  • Pass through the list and swap adjacent pairs of elements if they are out of order.
  • At the end of the first pass, the largest element has “bubbled up” to the end of the list.
  • Repeat this process $n$ times.

Pseudocode

Algorithm 4: Bubble Sort

Analysis

  • Elementary operation: comparison
  • Performed once on line 3
  • Inner loop (line 2) executed $n - i$ times
  • Outer loop (line 1) executed $n$ times
  • Total comparisons:
    $$ \sum_{i=1}^n \sum_{j=2}^{n-i+1} 1 = \sum_{i=1}^n (n-i) = n^2 - \left(\sum_{i=1}^n i\right) = n^2 - \frac{n(n+1)}{2} = \frac{2n^2 - n^2 - n}{2} = \frac{n^2-n}{2} $$
  • Bubble sort’s time complexity is $O(n^2)$.

Code Samples

Code Sample 9: Java Bubble Sort for integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bubbleSort(int[] array) {
  int n = array.length;
  int temp = 0;
  // Outer loop to control the number of passes
  for (int i = 0; i < n; i++) {
    // Inner loop for each pass, adjacent comparisons and swaps
    // The largest i elements are already in place at the end
    for (int j = 1; j < (n - i); j++) {
      if (array[j - 1] > array[j]) {
        // Swap elements if they are in the wrong order
        temp = array[j - 1];
        array[j - 1] = array[j];
        array[j] = temp;
      }
    }
  }
}