unit.11

Unit Overview

• Focus on sorts using keys or parts of keys as indices.

• Topics covered:

  • Counting Sort

  • Key-Indexed Counting

  • Least Significant Digit (LSD) Radix Sort

  • Most Significant Digit (MSD) Radix Sort

  • Three-Way Quicksort

  • Sorting Strings

Sorting Review

Elementary Sorts (O(N^2))

• Bubble Sort

• Insertion Sort

• Selection Sort

• Shell Sort (a small multiple of N times increments)

Advanced Sorts (O(N log N))

• Mergesort

• Treesort

• Heapsort

• Quicksort (worst case O(N^2))

Lower Bound for Sorting

• Any sort using only key comparisons requires O(N log N) comparisons.

Key-Indexed Sorting

• Improves on the O(N log N) lower bound using keys as indices in an array.

• Example: Sorting an array of 1,000,000 grades (0 to 100) by counting:

  • Create an array count[101] to tally occurrences.

  • Code executes in O(N + M) where N is array size, M is the range of grades.

Key-Indexed Counting

• Sorts records by their keys within a limited range of integers from 0 to R-1.

• Process:

  • Count the frequency of each key.

  • Calculate starting indices for records with each key.

  • Allocate records in the correct order in a scratch array and copy back.

Key-Indexed Counting Code Example

• Define arrays and count frequencies:

  int *count = new int[R+1];
  for(int i=0; i<N; i++) (*count)[a[i].getKey().getNumber()+1]++;
  {
  // Further operations...
  }

Key-Indexed Counting Analysis

• Key-indexed counting requires 8N + 3R + 1 accesses to stably sort N records.

• Operates in linear time if R is constant relative to N.

Programming with Punched Cards

• Programs typed on cards, 80 columns wide, 12 rows.

• Characters represented by punched holes.

• Card punching via a keyboard-operated machine.

Reading Cards

• Programs handed to an operator and read by a card reader.

• Results printed on-line printers.

Card Deck Management

• Decks can be vast; require organization to prevent mixing.

• Card numbering used for reordering if needed, with dedicated sorters for mechanical sorting.

Card Sorter Mechanism

• Simple sorters can separate by leading character using bins.

• Each digit in the cards directs which bin they enter (0-9).

Sorting Multi-Digit Numbers

• Sorting multi-digit structured data requires multiple passes through the sorter.

LSD Radix Sort Mechanism

• Generalized sorting for W-digit numbers; sorts from least to most significant digit.

• It uses key-indexed sorting for each digit position.

LSD Radix Sort Code Example

• Uses a counting principle for sorting by each column:

  for(int d=0; d<W; d++) {
      int* count = new int[11];
      for(int i=0; i<N; i++) (*count)[digitAt(a[i], d)+1]++;
      // Additional processing...
  }

LSD Radix Sort for Strings

• Works similarly for fixed-length strings, treating characters as digits in a base R system.

• Changes in count array size and access methods are required to accommodate string processing.

MSD Radix Sort Overview

• Cards are sorted by the most significant digit first, involving recursive sorting of each bin.

• Uses counting methods for separation and sorting of elements.

Three-Way String Quicksort

• Adapts quicksort for strings using three-way partitioning based on leading character.

• Recursively sort subarrays where keys share the same starting character.

Performance and Analysis

• Three-way string quicksort has efficient performance, using approximately 2N ln N character comparisons on average for N random strings.