Notes

Slippery Rock University

Dr. Deborah Whitfield

Go Browns!

Chapter 3: Simple Sorting
Data Structures and Algorithms in Java
CpSc 374

Sorting

Place items in order
Ascending or Descending
Data frequently needs a key
If there are 3 numbers, sequence of ifs
4 numbers - more ifs
Array of N numbers - need a technique

Bubble Sort

Bubble highest (or lowest) to the top (or bottom)
Bubble 2nd highest, ...

code:

int i, j;

for (i=nElems-1; i > 0; i--)  //all elems (exc 1st)
     for (j=0; j<i; j++)   // all unsorted elem pairs
         if (a[j] > a[j+1])
            swap(j, j+1);

Analysis of code:

int i, j;

for (i=nElems-1; i > 0; i--)  //N-1 passes
     for (j=0; j<i; j++)   // N-1 + N-2 + ... + 2 + 1= N(N-1)/2
         if (a[j] > a[j+1])
            swap(j, j+1);

Average Case:
Comparisons: 1/2N² - 1/2N - 0
Swaps: 1/4N² - 1/4N - 0

O(N²)

Selection Sort

Each pass locates (selects) the smallest item remaining in unsorted portion, then puts it in the correct location.

code:

int i, j, minIndx;
for (i=0; i < nElems-1; i++) {
     minIndx = i;
     for (j=i+1; j<nElems; j++)
         if (a[j] < a[minIndx])
            minIndx = j;
     swap(i, minIndx);
     }

Analysis

for (i=0; i < nElems-1; i++) {  // N-1 passes 
     minIndx = i;
     for (j=i+1; j<nElems; j++) // N-1 + N-2 + ... +1
         if (a[j] < a[minIndx]) //  = N(N-1)/2
            minIndx = j;
     swap(i, minIndx); // N-1
     }

Comparisons: 1/2N² - 1/2N - 0
Swaps: N - 1 // far fewer than Bubble

Insertion Sort

Each element, one at a time, is added to a sorted (sub)array, which implies that elements are shifted to make room.

code:

int i, j;
for (i=1; i< nElems; i++){
    long temp = a[i];
    j = i;
    while (j>0 && a[j-1]>temp){
          a[j] = a[j-1];
          j--;
          }
    a[j] = temp;
    }

Analysis

for (i=1; i< nElems; i++){       // N-1 times
    long temp = a[i];
    j = i;
    while (j>0 && a[j-1]>temp){ // 1,2,... N-1 (max)
          a[j] = a[j-1];         // = N(N-1)/2 (max)
          j--;                   // = N(N-1)/4 (avg-rand)
          }
    a[j] = temp;
    }

Comparisons: 1/4N² - 1/4N - 0
Copies: 1/4N² - 1/4N - 1
Swaps: 1 // far fewer than Bubble

Wrap Up

What should be counted?
In some languages, swaps (and copies) are "expensive" for typical records.
References & pointers can reduce "cost"
Comparisons
- Cheap for numbers
- What about Strings?
  if (a[j].greaterThan(a[j+1]))
  Where greaterThan is defined elsewhere
- More complex comparison functions?
Worst case, best case, average case
- Random data leads to average behavior
  When is this a good assumption?
- Best case
  Data is (almost) sorted already
  adding new items to an already sorted list
  Insertion sort is O(N) !!
- Worst case
  For sorts: generally, sorted in reverse
- Bubble Sort is considered one of the worst (practical) sorts possible...
- If you ever try to pass off Bubble sort as reasonable, it had better be the "short circuit" version:
```
if (!swapped) break;
     swapped = false;
```
  Best case: Data is already sorted. One pass only or O(N).

Running Time Comparison

Algorithm	Average	Best	Worst
Bubble Swaps Compares	O(N²) 1/4N² 1/4N²	O(N) 1 N	O(N²) 1/2N² 1/2N²
Selection	O(N²)	O(N²)	O(N²)
Insertion Swaps Compares	O(N²) 1/8N² 1/4N²	O(N) 1/2N N	O(N²) 1/4N² 1/2N²

Space
- All of these sorts work "in place"
- Constant space requirements
Stability
- All are "stable"
- Do not re-order data that have the same key
When to use one of these simple sorts - See chart in Chapter 15
- Author suggests use of one of these for no more than 1000 data records
- Insertion sort often used for 10 or less
O(N²) compared to O(2N²)
- Compare N² + N + 10⁶ to 2N² - N + 1
- For N = 1000, almost equal
  10⁶ + 1000 + 10⁶