Note51

0.0 by Claude

12 min read

Chapter 8b – Algorithms for Sorting

Bubble Sort

Definition

Bubble sort is the simplest and slowest sorting algorithm. It compares two adjacent elements in sequence and swaps them if they are out of order. Larger values gradually “bubble” to the end of the array.

Causes

Not specified in notes.

Goals / Objectives

  • To arrange array elements into sorted order (increasing or decreasing).
  • To repeatedly move the largest element to the end of the array after each pass.

Importance

  • Helps demonstrate the basic concept of comparison-based sorting.
  • Useful as an introductory algorithm for learning sorting techniques.

Procedures

  1. Make several passes through the array.

  2. On each pass, compare neighboring pairs of elements.

    • If pair is in correct order → leave unchanged.
    • If pair is in wrong order → swap them.

  3. After the first pass, the largest element is placed at the last position.

  4. Repeat for the remaining unsorted portion until the array is sorted.

  5. If a pass occurs with no swaps → the array is already sorted.

Advantages & Disadvantages

Advantages:

  • Simple and easy to understand.
  • Can detect if an array is already sorted (early stopping).

Disadvantages:

  • Very slow compared to other sorting algorithms.
  • Requires multiple passes even for nearly sorted arrays.

Impact / Effect

  • Best case: Array is already sorted. Only one pass with n-1 comparisons is required.

    • Time complexity: O(n)

  • Worst case: Array is in reverse order. Requires maximum passes (n-1) and many comparisons.

    • Time complexity: O(n²)

Examples

Example from notes: Sorting [77, 44, 22, 88, 99, 55, 33, 66]

  • Original: 77 44 22 88 99 55 33 66
  • After Pass 1: 44 22 77 88 55 33 66 99
  • After Pass 2: 22 44 77 55 33 66 88 99
  • After Pass 3: 22 44 55 33 66 77 88 99
  • After Pass 4: 22 44 33 55 66 77 88 99
  • After Pass 5: 22 33 44 55 66 77 88 99
  • After Pass 6: 22 33 44 55 66 77 88 99

Key Takeaways

  • Bubble sort repeatedly compares and swaps adjacent elements.
  • Best case: O(n), Worst case: O(n²).
  • Easy to understand but inefficient for large datasets.
  • Stops early if no swaps are needed in a pass.

Selection Sort

Definition

Selection sort is a simple sorting algorithm that repeatedly selects the smallest element from the unsorted portion of the array and places it in its correct position in the sorted portion.

Causes

Not specified in notes.

Goals / Objectives

  • To rearrange array elements into sorted order.
  • To reduce the number of swaps compared to bubble sort.

Importance

  • Provides a clearer method of selecting and placing elements compared to bubble sort.
  • Often used for teaching purposes due to its simplicity.
  • Does not depend on the initial arrangement of data.

Procedures

  1. Make n–1 passes through the sequence of n elements.

  2. On the 1st pass:

    • Find the smallest element from a[0..n-1].
    • Swap it with the element at index 0.

  3. On the 2nd pass:

    • Find the smallest element from a[1..n-1].
    • Swap it with the element at index 1.

  4. Repeat until the second-last element is placed correctly.

Algorithm (Iterative):

for (index = 0; index < n-1; index++) {
   indexOfSmallest = index of smallest value among a[index..n-1]
   swap a[index] and a[indexOfSmallest]
}

Algorithm (Recursive):

selectionSort(a, first, last)
if (first < last) {
   indexOfSmallest = index of smallest value among a[first..last]
   swap a[first] and a[indexOfSmallest]
   selectionSort(a, first + 1, last)
}

Advantages & Disadvantages

Advantages:

  • Fewer swaps compared to bubble sort (only 1 swap per pass).
  • Works regardless of initial order of elements.
  • Slightly more efficient than bubble sort.

Disadvantages:

  • Time complexity is always O(n²) (no improvement for partially sorted data).
  • Inefficient for large datasets; only suitable for small arrays.

Impact / Effect

  • Requires (n-1) + (n-2) + … + 1 = n(n-1)/2 comparisons = O(n²).
  • Recursive version performs the same operations, also O(n²).

Examples

Example from notes: Sorting [77, 44, 22, 88, 99, 55, 33, 66]

  • Original: 77 44 22 88 99 55 33 66
  • After Pass 1: 22 44 77 88 99 55 33 66
  • After Pass 2: 22 33 77 88 99 55 44 66
  • After Pass 3: 22 33 44 88 99 55 77 66
  • After Pass 4: 22 33 44 55 99 88 77 66
  • After Pass 5: 22 33 44 55 66 88 77 99
  • After Pass 6: 22 33 44 55 66 77 88 99
  • After Pass 7: 22 33 44 55 66 77 88 99

Key Takeaways

  • Selection sort selects the smallest element each pass and places it in order.
  • Always runs in O(n²) time, regardless of input order.
  • Requires fewer swaps but still inefficient for large arrays.
  • Best suited for small datasets.

Insertion Sort

Definition

Insertion sort is a sorting algorithm that builds the sorted array one element at a time by inserting each element from the unsorted portion into its correct position in the sorted portion.

Causes

Not specified in notes.

Goals / Objectives

  • To sort an array by repeatedly inserting unsorted elements into the correct position.
  • To provide a faster alternative to bubble sort and selection sort for small datasets.

Importance

  • More efficient than bubble sort and selection sort for small or nearly sorted arrays.
  • Provides a foundation for understanding more complex algorithms.

Procedures

  1. Partition the array into two regions:

    • Sorted region (initially the first element).
    • Unsorted region (all remaining elements).

  2. Take the first element from the unsorted region.

  3. Compare it with elements in the sorted region, shifting elements to the right as needed.

  4. Insert the element in the correct position.

  5. Repeat for all elements until the array is sorted.

Iterative Algorithm:

for (unsorted = 1 through n-1) {
   firstUnsorted = a[unsorted]
   insertInOrder(firstUnsorted, a, unsorted - 1)
}

insertInOrder(element, a, end)
   index = end
   while (index >= 0) and (element < a[index]) {
       a[index + 1] = a[index]   // shift element right
       index--
   }
   a[index + 1] = element

Recursive Algorithm:

insertionSort(a, first, last)
if (array has more than one element) {
   Sort a[first..last-1]
   Insert a[last] into correct position in sorted region
}

Advantages & Disadvantages

Advantages:

  • Faster than bubble sort and selection sort.
  • Efficient for small arrays or arrays that are nearly sorted.
  • Simple to implement.

Disadvantages:

  • Time complexity still O(n²) in average and worst cases.
  • Not suitable for very large datasets.

Impact / Effect

  • Best case: Array is already sorted → only O(n) time needed.
  • Average case: O(n²).
  • Worst case: Array is in reverse order → O(n²).
  • Performance improves when data is closer to sorted order.

Examples

Example from notes: Sorting [77, 44, 22, 88, 99, 55, 33, 66]

  • Original: 77 44 22 88 99 55 33 66
  • After Pass 1: 44 77 22 88 99 55 33 66
  • After Pass 2: 22 44 77 88 99 55 33 66
  • After Pass 3: 22 44 77 88 99 55 33 66
  • After Pass 4: 22 44 77 88 99 55 33 66
  • After Pass 5: 22 44 55 77 88 99 33 66
  • After Pass 6: 22 33 44 55 77 88 99 66
  • After Pass 7: 22 33 44 55 66 77 88 99

Key Takeaways

  • Insertion sort inserts unsorted elements into the correct place in the sorted portion.
  • Best case: O(n), Average/Worst case: O(n²).
  • More efficient than bubble sort and selection sort, especially for nearly sorted data.
  • Practical for small datasets, but not for large ones.

Quick Sort

Definition

Quick sort is a recursive, divide-and-conquer sorting algorithm. It partitions an array into two segments based on a pivot element, then recursively sorts each segment.

Causes

Not specified in notes.

Goals / Objectives

  • To efficiently sort arrays by dividing the problem into smaller parts.
  • To use partitioning around a pivot element for faster sorting compared to simple algorithms.

Importance

  • Extremely fast in practice, especially for large datasets.
  • Outperforms other O(n log n) algorithms like merge sort due to lower memory requirements.
  • A widely used sorting algorithm in libraries and real-world applications.

Procedures

  1. Choose a pivot element from the array.

  2. Partition the array so that:

    • Elements before the pivot are smaller.
    • Elements after the pivot are larger.
    • Pivot is in its correct sorted position.

  3. Recursively apply quick sort to the left and right subarrays.

Algorithm:

quickSort(a, first, last)
if (first < last) {
   choose pivot
   partition array about pivot
   pivotIndex = index of pivot
   quickSort(a, first, pivotIndex - 1)   // sort left side
   quickSort(a, pivotIndex + 1, last)   // sort right side
}

Partition strategy:

  • Rearrange elements so that pivot is correctly placed.
  • Subarrays remain separated but unsorted.
  • After partition: one element (pivot) is fixed, recursion continues on others.

Pivot selection (median-of-three method):

  • Choose the median of:

    • First element
    • Middle element
    • Last element

  • This reduces the chance of worst-case scenarios.

Advantages & Disadvantages

Advantages:

  • Very efficient on average (O(n log n)).
  • Faster than merge sort in practice.
  • Requires no extra memory for merging.

Disadvantages:

  • Worst case: O(n²) (occurs if pivot selection is poor, e.g., already sorted array with bad pivot).
  • Performance depends heavily on pivot choice.

Impact / Effect

  • Average case: O(n log n).
  • Best case: O(n log n).
  • Worst case: O(n²).
  • Acceptable even in worst case for moderately large arrays.
  • Pivot selection strategies (like median-of-three) help avoid worst-case performance.

Examples

Example from notes (Exercise 8b.2): Sorting [55, 99, 44, 77, 88, 33, 22, 66]

  • Pivot chosen as first element (55).
  • After partitioning and swaps: pivot moves into correct position, elements smaller on left, larger on right.
  • Process repeats recursively for left and right segments until fully sorted. (Notes show step-by-step trace in appendix, not fully detailed in slides.)

Key Takeaways

  • Quick sort is a divide-and-conquer algorithm using a pivot for partitioning.
  • Average case: O(n log n), Worst case: O(n²).
  • Pivot selection is crucial for efficiency (median-of-three helps).
  • Faster than merge sort in practice and requires less memory.

Merge Sort

Definition

Merge sort is a recursive, divide-and-conquer sorting algorithm that splits an array into two halves, sorts them separately, and then merges the two sorted halves into one sorted array.

Causes

Not specified in notes.

Goals / Objectives

  • To sort arrays by dividing them into smaller parts and merging results.
  • To guarantee consistent performance regardless of initial element order.

Importance

  • Provides reliable O(n log n) performance in all cases.
  • Frequently used in programming libraries (e.g., Java Arrays.sort() for objects).
  • Demonstrates the divide-and-conquer paradigm in sorting.

Procedures

  1. Divide: Split the array into two halves.
  2. Conquer: Recursively apply merge sort to each half.
  3. Combine: Merge the two sorted halves into a single sorted array.

Algorithm (mergeSort):

mergeSort(a, first, last)
if (first < last) {
   mid = (first + last) / 2
   mergeSort(a, first, mid)
   mergeSort(a, mid+1, last)
   merge(a, first, mid, last)
}

Algorithm (merge):

merge(a, tempArray, first, mid, last)
beginHalf1 = first
endHalf1   = mid
beginHalf2 = mid + 1
endHalf2   = last
index = 0

while (beginHalf1 <= endHalf1) and (beginHalf2 <= endHalf2) {
   if (a[beginHalf1] < a[beginHalf2]) {
       tempArray[index] = a[beginHalf1]
       beginHalf1++
   } else {
       tempArray[index] = a[beginHalf2]
       beginHalf2++
   }
   index++
}

// At this point, one half is fully copied.
// Remaining elements from the other half are copied over.

Advantages & Disadvantages

Advantages:

  • Very efficient with consistent O(n log n) time complexity.
  • Performance is unaffected by the initial order of data.
  • Stable sorting algorithm (keeps equal elements in original order).

Disadvantages:

  • Requires additional memory (temporary array during merge step).
  • Slower than quick sort in practice due to memory overhead.

Impact / Effect

  • Best case: O(n log n).
  • Average case: O(n log n).
  • Worst case: O(n log n).
  • Extra memory requirement is the main drawback.

Examples

  • Merging two sorted arrays (from figures in notes): Example shows how two sorted halves are merged step by step into one sorted array.
  • Recursive breakdown: Each recursive call splits arrays into halves until size 1, then merges upward.

(Figures in notes illustrate this, but no numeric worked example given like bubble/selection/insertion sort.)

Key Takeaways

  • Merge sort follows divide → conquer → combine.
  • Always runs in O(n log n) regardless of input order.
  • Requires extra memory for merging.
  • Stable and consistent, widely used in libraries.

Comparing Sorting Algorithms & Choosing Suitable Methods

Definition

This section compares different sorting algorithms (bubble, selection, insertion, merge, quick, radix, shell) in terms of performance, memory needs, and suitability. It also discusses factors to consider when selecting a sorting method.

Causes

Not specified in notes.

Goals / Objectives

  • To evaluate which sorting algorithm is most appropriate for a given problem.
  • To understand trade-offs between speed, consistency, memory, and stability.

Importance

  • Helps programmers choose the right sorting algorithm for specific applications.
  • Recognizes that no single sorting algorithm is best for all cases.
  • Highlights efficiency differences in Big-O notation for best, average, and worst cases.

Procedures

Factors in selecting sorting methods:

  • Speed (how fast the algorithm works).
  • Consistency of performance (whether performance is stable across different inputs).
  • Memory requirements (whether extra memory is needed, e.g., merge sort).
  • Stability (whether equal elements keep their original order).
  • Versatility (whether it works on different data types).
  • Complexity of coding (ease or difficulty of implementation).
  • Nature of datasets (already sorted, reversed, large, small, etc.).

Advantages & Disadvantages

Selection Sort:

  • Always O(n²) → simple but slow.

Insertion Sort:

  • Best case O(n), worst/average O(n²).
  • Good for small or nearly sorted arrays.

Bubble Sort:

  • Same as insertion, but slower in practice.

Quick Sort:

  • Best/average O(n log n).
  • Worst case O(n²) if pivot choice is poor.
  • Fastest in practice, memory efficient.

Merge Sort:

  • Always O(n log n).
  • Stable and consistent.
  • Needs extra memory.

Radix Sort:

  • O(n) for best, average, and worst.
  • Suitable for integers or fixed-length strings.

Shell Sort:

  • O(n) in best case.
  • Worst case can reach O(n²).
  • Practical compromise for medium data sizes.

Impact / Effect

  • Sorting efficiency directly affects program performance, especially on large datasets.
  • Wrong choice of sorting method may cause significant slowdowns or excessive memory usage.

Examples

Comparison Table from Notes:

TechniqueBest CaseAverage CaseWorst Case
Selection SortO(n²)O(n²)O(n²)
Insertion SortO(n)O(n²)O(n²)
Bubble SortO(n)O(n²)O(n²)
Quick SortO(n log n)O(n log n)O(n²)
Merge SortO(n log n)O(n log n)O(n log n)
Radix SortO(n)O(n)O(n)
Shell SortO(n)O(n^1.5)O(n^1.5)–O(n²)

Key Takeaways

  • No single sorting algorithm is best for all situations.
  • Quick sort is usually the fastest in practice, but may degrade if pivots are poorly chosen.
  • Merge sort is reliable and stable, but needs more memory.
  • Insertion sort works well for small or nearly sorted arrays.
  • Radix sort is fastest for integers/strings but not general-purpose.
  • Choosing the right sorting algorithm depends on data size, type, and performance needs.

Graph View

Backlinks