Data Structures & Algorithms Lecture Notes

30 October 2008 • Sorting Basics

Outline

• About sorting.

  • Motivation

  • Components

  • Properties

• Some sorting algorithms.

Some Questions

• Would you rather find my phone number given

  • My name?

  • Or my street address?

• Why?

  • The phone book easily answers the first question.

  • Even though it has the information, the phone book can’t easily answer the second question.

Arrangements and Access

• The phone book is organized to easily answer one kind of question but not another.

  • Even though the information is available.

• Data can be arranged to simplify selective data access.

  • Arrangement depends on data access.

  • The data must be explicitly arranged.

  • Data access should be selective.

Sorting

• Sorting arranges data for more efficient data access.

  • Efficient data access is determined by the application at hand.

• Internal sorting applies when all sort data fits in primary store.

  • This is what we’ll be looking at.

• External sorting applies when all sort data doesn’t fit in primary store.

  • The sort data resides on secondary store.

Sorting Properties

• Sorting requires work.

  • The arrangement-work vs. access-savings trade-off.

• The sorting work is dependent on the data access.

  • Sorting is non-trivial.

  • How to sort is easy (relatively, usually);
    what to sort is harder.

Sorting Components

• To sort, you need

  • Data.

  • An ordering over the data:

    bool ordering(const data &, const data &)
    

  • A sequencible collection holding the data.

    • A collection that supports before and after.

  • A sorting algorithm to do the re-arranging.

Sort Data

• Most generally, a sort datum is a record with one or more fields.

• Data are ordered by relative field values between records.

  • At least one field, possibly more.

  • The fields used in sorting are called sort keys.

• Mostly we’ll ignore sort-datum structure.

  • The whole datum is the key.

Sort Ordering

• The sort ordering is a binary predicate

  bool ordering(const data &, const data &)
  

• The ≤ ordering leads to an ascending-order sort.

  The ≥ ordering leads to an descending-order sort.

  • Mostly we’ll ignore the difference and assume an ascending-order sort.

• There are lots of other orderings available.

Data Collections

• The data collection must support before and after relations.

  • Otherwise data order doesn’t make sense.

  • Arrays and lists do; sets and hash tables don't.

• The cost and uniformity of data access is also usually important.

• Mostly we’ll be assuming arrays.

Sorting Algorithm

• A sorting algorithm permutes (re-arranges) the data in collection C according to the ordering O so that

  If a is before b in C then O(a, b) is true.

  

How to Sort

• A sorting algorithm repeatedly asks the question

  

• The answer is always the same.

• Sorting algorithms differ in the way they ask and how they answer this question.

Bubble Sort

• The proper value "bubbles up" into place.

bubble sort(T a[], n)
  for i = 0 to n - 2
    for min = n - 1 to i + 1
      if a[min - 1] > a[min]
        swap(a[min - 1], a[min])

Bubble Sorting

Another Question

• The question can’t be answered until the array’s completely sorted.

• But it can be answered relative to the sorted part.

  • How do you sort a hand of cards?

Insertion Sort

insertion sort(T a[], n)
  for i = 1 to n - 1
    T x = a[i]
    gap = i
    while gap > 0 and a[gap - 1] > x
      a[gap] = a[gap - 1]
      gap--
    a[gap] = x

Bubbling vs. Inserting

• Insertion sort slides elements.

• Bubble sort swaps elements.

• Insertion sort uses two-thirds fewer assignments than does bubble sort.

• Asymptotically, bubbling and inserting both use O(n²) assignments.

  • It’s the constants to O(n²) that differ.

  • Inserting should be somewhat faster than bubbling.

Oh Really?

The Timing Details

• Hardware: An IBM A31 laptop with 729 mbytes and a Pentium 4 Mobile 1.6 GHz CPU with a 512 kbyte cache.

• Software: Debian testing with g++ 4.0.3 compiled with -03.

• Data: arrays of either 32-bit integers or three-space points (three doubles, 24 bytes) with sorting done on the x coordinate.

• Execution: tests run with no other significant background or foreground tasks; each data point is a single timing measurement.

Bubbling Without Drag

• Both bubble and insertion sort move lots of data.

  • Moving data is expensive.

• Don’t drag the smallest element along in the scan.

  • Keep track of its index.

Selection Sort

selection sort(T a[], n)
  for i = 0 to n - 2
    min = i
    for j = i + 1 to n - 1
      if a[min] > a[j]
        min = j
    swap(a[min], a[i])

Selection Sorting

Selecting vs. Inserting

• Insertion sort uses fewer comparisons than does selection sort.

• Selection sort uses fewer assignments than does insertion sort.

• Assignment is more expensive than is comparing.

  • Selection sort wins!

Does It?

• When moving data is cheap, comparisons decide.