Data Structure and Algorithm Design

Chapter 9

Xingang (Ian) Fang

Sections

Sorting Overview
Quick Sort
Merge Sort
Radix Sort

Sorting Algorithms

Xingang (Ian) Fang

Sections

Overview
Categories
Sorting Array and Linked List
Time Complexity and Space Complexity

Overview

Sorting algorithms are used to arrange a sequence in a particular order. The base type must be comparable.
Visualizations
- Our Card Sort Visualizer demonstrates selection, insertion, merge, and textbook quick sort.
- visualgo.net
- Data Structure Visualization
- Sorting algorithms
Application
- Part of many other algorithms
- Database system
- File system
- Operating system

Array vs Linked List

For array

Array property
- fast access by index
- slow insertion and deletion of elements except at the end
Preferred general purpose sorting algorithms
- Quick sort
- Merge sort
- Heap sort
- Tim sort (a hybrid method, FYI)

For linked list

Linked-list property
- slow access by index
- fast reconstruction of new list
- fast access to neighboring nodes
With the same time complexity, consider data movement overhead
Preferred general purpose sorting algorithms
- Merge sort
- Insertion sort

Real-World Choices (FYI)

Summary of real-world state-of-art for array

For small arrays
- Insertion sort
For large arrays
- Quick sort > Merge sort > Heap sort
- In parallel environment
  - Merge sort
  - Quick sort
Overall winner for array: hybrid method
- Quick sort + Insertion sort
- Merge sort + Insertion sort

Summary of real-world state-of-art for linked list

For linked list
- Direct sort
  - Merge sort for large linked list (can be parallelized)
  - Insertion sort for small linked list
- Sort as array of pointers
  - Make an array of pointers
  - Let each element point to the corresponding node in the linked list
  - Sort the array of pointers
  - Generate the new linked list according to the sorted array

Time Complexity

Comparison-based sorting algorithms (Array)
- Bubble sort \(\Theta(n^2)\)
- Selection sort \(\Theta(n^2)\)
- Insertion sort \(\Theta(n^2)\)
- Merge sort \(\Theta(n \log n)\)
- Quick sort \(\Theta(n \log n)\) (average), \(\Theta(n^2)\) (worst)
- Heap sort \(\Theta(n \log n)\)
Non-comparison-based sorting algorithms (Array)
- k is a constant value depending on algorithms
- Radix sort \(\Theta(nk)\)
- Counting sort \(\Theta(n+k)\)
- Bucket sort \(\Theta(n+k)\)
Linked list
- Merge sort \(\Theta(n \log n)\)
- Insertion sort \(\Theta(n^2)\)

Space Complexity

The following discussion is on array only.

In-place sorting algorithms (swap based) \(\Theta(1)\)
- \(\Theta(1)\) for swapping
- \(\Theta(\log n)\) to \(\Theta(n)\) for recursion stack
- Iterative: swapping only
- Recursive: swapping + recursion stack
Out-of-place sorting algorithms \(\Theta(n)\)
- \(\Theta(n)\) for a new array
- \(\Theta(\log n)\) to \(\Theta(n)\) for recursion stack

Quick Sort

By Sir Tony Hoare in 1959.
One of the most widely used
Characteristics
- Divide and conquer algorithm
- Comparison based (general purpose)
- Recursive
- In-place
- Efficient
- Unstable - relative order of equal elements is not preserved

Quick partition algorithm

The core of quick sort
Many variations: Stick to our variation from zyBook!
Steps
1. Pick an element, called a pivot, from the list.
2. Use the pivot to partition the list into two sublists.
3. Reorder the list in the process so that all elements less than the pivot come before the pivot, and all elements greater than the pivot come after it.
4. Return the location of the partition.

Quick Partition Algorithm

Lomuto’s partition scheme (FYI)
Hoare’s partition scheme (zyBook variation)
1. Let two cursor indices to point to the first - 1 and last + 1 positions of the list respectively.
2. Keep moving the left cursor to the right until it points to an element greater and equal than the pivot.
3. Move the right cursor to the left until it points to an element less and equal than the pivot.
4. If the left cursor meets or passes the right cursor, the partition is complete. Return the right cursor.
5. Swap the elements pointed by the two cursors.
6. Move both cursors one more step
7. Repeat steps 2-6 until the partition is complete (step 4 returns).

Quick Partition Algorithm: Our Variation (Hoare’s Scheme)

Hoare’s partition scheme
Middle element as pivot
Cursor will not pass by the pivot, so the pivot will be swapped many times.
The returned index is the final position of the pivot

int quickPartition(int *arr, int low, int high) {
  int mid = (high + low) / 2;
  // int mid = low + (high - low) / 2;
  int pivot = arr[mid];
  while (true) {
    while (arr[low] < pivot) ++low;
    while (arr[high] > pivot) --high;
    if (low >= high) break;
    swap(arr[low], arr[high]);
    ++low;
    --high;
  }
  return high;
}

Quick Partition Example (con’d)

Given an int array {42, 7, 85, 23, 64, 91, 9, 73, 18, 56}

First round of partitioning

// low is 0, high is 9 initially
middle = (low + high) / 2 = 4
pivot = arr[middle] = 64

{42, 7, 85, 23, 64, 91, 9, 73, 18, 56} find position
        l                          h
{42, 7, 56, 23, 64, 91, 9, 73, 18, 85} swap 85, 56, and move by 1
            l                  h
{42, 7, 56, 23, 64, 91, 9, 73, 18, 85} find position (hit pivot)
                l              h
{42, 7, 56, 23, 18, 91, 9, 73, 64, 85} swap 64, 18, and move by 1
                    l      h
{42, 7, 56, 23, 18, 91, 9, 73, 64, 85} find position
                    l   h
{42, 7, 56, 23, 18, 9, 91, 91, 64, 85} swap 91, 9, and move by 1
                    h  l
h <= l, return h; left: low to h, right: h + 1 to high

The pivot is moved only once.
The returned index is NOT the final position of the pivot!
Exercise:
- How about the first element is selected as the pivot? Is there more movement of data?

Quick Sort Algorithm

Recursive
In-place
Need a helper function to work on a sublist
1. If the range is empty, return.
2. Call quick partition algorithm to partition the list into two sublists.
3. Recursively call quick sort on both sublists.

void quicksort(int *arr, int size) {
  quicksortHelper(arr, 0, size - 1);
}

void quicksortHelper(int *arr, int low, int high) {
  if (low >= high) return;
  int part = quickPartition(arr, low, high);
  quicksortHelper(arr, low, part);
  quicksortHelper(arr, part + 1, high);
}

Complexity

Time
- Depends on whether the pivot can partition the list into two sublists of roughly equal size
- \(\Theta(n \log n)\) average case
- \(\Theta(n^2)\) worst case, extremely uneven partitioning
Space - \(\Theta(\log n)\) to \(\Theta(n)\) depending on partition
Improvement attempts
- Pivot selection
  - Randomized quick sort
  - Median of three
- Shuffling the list before sorting

Visualization For Quick sort

Quick Sort visualizers use different partition rules. Our lab demonstrates textbook Quick Sort with a middle pivot and two-way scans; compare those details with the assigned zyBook variant before treating the traces as identical.

Our Card Sort Visualizer
Some of them uses Lomuto’s scheme
Some of them uses Hoare’s scheme but select a different pivot
- http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Merge Sort

John von Neumann in 1945. (Do you know who he is?)
Characteristics
- Divide and conquer algorithm
- Comparison based (general purpose)
- Recursive
- Out-of-place
  - Requires additional memory
  - Efficient for linked lists
- Efficient for large data sets
- Stable - relative order of equal elements is preserved
- Parallelizable

Algorithm Details

Steps (top-down)
1. Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
2. Conquer: Sort the two subsequences recursively using merge sort.
3. Combine: Merge the two sorted subsequences to produce the sorted sequence.
Variations
- top-down
  - usually recursive
  - stop repetition when the size of section is 1 or 0
- bottom-up (FYI)
  - usually iterative
  - merge all n size 1 sections (single element) into n/2 size 2 sections
  - merge all size 2 lists to n/4 size 4 lists
  - continue until done

Complexity

Time
- \(\Theta(n \log n)\) array and linked list
Space
- Array: \(\Theta(n)\) optimized
- Linked list: \(\Theta(1)\)

Visualization Website

Our lab steps through top-down merge sort and shows whether equal cards retain their relative order.

Radix Sort

Manual sorting methods 19th century
Characteristics
- Non-comparison-based sorting algorithm
- Only works with integers, strings whose length is finite
- Digit/character-based
- Stable
- Out-of-place

Algorithm Details

Example Steps (sorting decimal integers)
1. Initialize a list of buckets, one for each digit (0-9)
2. Group by digits (two methods):
  - LSD: Start from the least significant digit (rightmost) and group the numbers into buckets based on that digit
  - MSD: Start from the most significant digit (leftmost) and group the numbers into buckets based on that digit
3. Collect the numbers from the buckets in order
4. Move to the next digit and repeat the group and collect steps until all digits have been processed
Further improvement
- Zero-padding
- Negative number support
- Buckets storage

Complexity

Time: \(\Theta(nk)\)
Space: \(\Theta(n+k)\) (single array method)
When k is a constant or much smaller than n, time complexity is \(\Theta(n)\).
When k is comparable to n or even greater, DO NOT use radix sort!

Visualization

The single array method is demonstrated.
- https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
The more abstract version is demonstrated without implementation details
- https://visualgo.net/en/sorting

Data Structure and Algorithm Design

Sections

Sorting Algorithms

Sections

Overview

Categories

Other Method To Categorize

Array vs Linked List

Real-World Choices (FYI)

Time Complexity

Space Complexity

Quick Sort

Quick partition algorithm

Quick Partition Algorithm

Quick Partition Algorithm: Our Variation (Hoare’s Scheme)

Quick Partition Example (con’d)

Quick Sort Algorithm

Complexity

Visualization For Quick sort

Merge Sort

Algorithm Details

Complexity

Visualization Website

Radix Sort

Algorithm Details

Complexity

Visualization