Data Structures and Algorithms Lecture Notes

13 April 2011 • 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:

    public interface Comparable<T>
      public int compareTo(T o)
    

  • 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 Predicates

• The sort ordering is a binary predicate

  bool ordering(const data &, const data &)
  bool operator < (const T &, const T &) const

• Java uses interfaces to indicate instances that can be ordered:

  public interface Comparable<T>
    public int compareTo(T o)
  
  public interface Comparator<T>
    public int compare(T o1, T o2)
    public boolean equals(Object o)

Sort Ordering

• 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.

Summary

• Sorting is an important, basic algorithmic technique.
• Trade-off early work for later work.
  • Pre-process the data for easier use.
• Basic sorting is concerned with finding out where each element goes.
  • Or which element goes in a particular array location.