Slide 8.11: Keysort.cpp
Slide 8.13: WriteFile.h
Home

Bubblesort.h

A keysort does not do the sorting itself. Instead, it needs to use a sorting algorithm to do the actual sorting work. This program uses a bubble sort, which is probably the simplest way of sorting an array of objects. Unfortunately it is also the slowest way! Given an array a of numbers, with length n, here's a snippet of C code for a bubble sort:

Algorithm of a Bubble Sort 

  for (i = 0;  i < n-1;  i++)
    for (j = 0;  j < n-1-i;  j++)
      if (a[j+1] < a[j]) {  /* compare the two neighbors */
        tmp    = a[j];      /* swap a[j] and a[j+1]      */
        a[j]   = a[j+1];
        a[j+1] = tmp;
      }

The basic idea is the pairs of adjacent values to be sorted are compared and interchanged if they are out of order; thus, list entries “bubble upward” in the list until they bump into one with a lower sort value.

 ~wenchen/public_html/cgi-bin/351/week8/Bubblesort.h  
#include  <cstring>
  using namespace  std;

void  Bubblesort( char key[MaxRecord][MaxStr],
    char rrn[MaxRecord], int number ) {
  int   temp;
  char  buffer[MaxStr];

  for ( int i = 0;  i < number-1;  i++ )
    for ( int j = 0;  j < number-1-i;  j++ )
      if ( strcmp( key[j+1], key[j] ) < 0 ) {
        /* compare the two neighbors */
        strcpy( buffer, key[j] );
        temp = rrn[j];   
        /* swap key[j] and key[j+1] */
        strcpy( key[j], key[j+1] );
        rrn[j] = rrn[j+1];
        strcpy( key[j+1], buffer );
        rrn[j+1] = temp;
      }
}