Sorting and Searching Arrays

Tom Kelliher, CS18

Mar. 25, 1996

Pointers and Arrays

Consider:

int data[SIZE];
int i;
int* pi;
int val;

Array name is constant pointer to first element:

data == &data[0];

Arrays and pointers closely connected.

One Way to Initialize data

for (i = 0; i < SIZE; ++i)
   cin >> data[i];

Another Way of Initializing data

for (pi = data; pi < data + SIZE; ++pi)
   cin >> *pi;

But, an int is 2 bytes. ++pi???

Pointer Arithmetic

Valid pointer operations:

• Assignment.
• Addition/Subtraction of integer values.
• Subtraction of two pointers of the same type and pointing to elements of the same array.
• Comparison to other pointers of the same type and pointing to elements of the same array and NULL.
• De-referencing.

int* p = NULL;

pi = data + 2;

*pi = 45;

++pi;

*pi = 34;

*(pi - 3) = 98;

i = *pi + 2;

p = data;

pi = data + 4;

--pi;

cout << pi - p << endl;

cout << (pi == p) << endl;

cout << (pi < p) << endl;

Example: Determining the Length of a String

int strlen(char s[])
{
   int i = 0;

   while(s[i] != '\0')
      ++i;

   return i;
}

int strlen(char* s)
{
   char* t = s;

   while (*t != '\0')
      ++t;

   return t - s;
}

Typical call:

char str[] = "Hello world.\n";
int len;

len = strlen(str);

Binary Search

Example: Database of checking accounts.

class Checking
{
 private:
   char accountNumber[ACCOUNT_NUMBER_LENGTH];
   ...

 public:
   Checking( ... );
   ...
   char* getAccountNumber(char* buffer, int bufferLen);
};

char* Checking::getAccountNumber(char* buffer, int bufferLen)
{
   if (strlen(accountNumber) >= bufferLen)
      return NULL;

   return strcpy(buffer, accountNumber);
}

Checking accounts[MAX_ACCOUNTS];

int checkingAccountOpened(char* accountNumber)
{
   return binarySearchChecking(accountNumber, accounts,
                               accounts + numberOfAccounts - 1)

int binarySearchChecking(char* account, Checking* first, Checking* last)
{
   Checking* mid;
   char midAccount[ACCOUNT_NUMBER_LENGTH];
   int compare;

   while (first <= last)
   {
      mid = first + (last - first) / 2;
      assert (mid->getAccountNumber(midAccount, sizeof(midAccount))
              != NULL);

      if ((compare = strcmp(account, midAccount)) == 0)
         return 1;
      else if (compare < 0)
         last = mid - 1;
      else
         first = mid + 1;
   }
}

The Mergesort Algorithm

• Fewer comparisons than bubble or selection sorts.
• More memory required.

The Algorithm:

Mergesort(array)
{
   if array has less than two elements
      return
   else
      split array in half
      Mergesort(first  half)
      Mergesort(second half
      Merge(first half, second half)
   end_if
}

A program:

/**********************************************************************
 * mergesort.cc
 * Tom Kelliher
 *
 * Demonstrates the mergesort algorithm
 **********************************************************************/


#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>


const int DATA_SIZE = 20;   // Number of ints to sort.


// Prototypes.
void mergesort(int *, int);
void merge(int *, int);
void move(int *, int *, int);

/**********************************************************************
 * main
 **********************************************************************/

int main() {

    int data[DATA_SIZE];   // Storage for int to be sorted.
    int *intptr,           // "Index" pointer.

    // Seed the random number generator.
    srand((unsigned) time((time_t *) NULL));

    cout << "\nUnsorted list:\n\n";

    // Get random numbers for the unsorted data.
    for (intptr = data; intptr < data + DATA_SIZE; intptr++)
       cout << (*intptr = rand()) << endl;

    mergesort(data, DATA_SIZE);

    cout << "\nSorted list:\n\n";

    for (intptr = data; intptr < data + DATA_SIZE; intptr++)
       cout << *intptr << endl;

    return (0);
}

/**********************************************************************
 * mergesort
 *
 * data is the address of the first element to be sorted.
 * len is the number of elements to sort.
 **********************************************************************/

void mergesort(int *data, int len) {

    int half = len / 2;

    if (len < 2)
      return;

    mergesort(data, half);   // Sort first half of data.
    mergesort(data + half, len - half);   // Sort second half of data.

    // Merge two sorted halves into a sorted whole.
    merge(data, len);
}

/**********************************************************************
 * merge
 *
 * data is the address of the first element to be merged.
 * len is the number of elements in BOTH halves to be merged.
 **********************************************************************/

void merge(int *data, int len) {

    int half = len / 2;
    int *p1 = data;   // Pointer to elements in first half.
    int *p2 = data + half;   // Pointer to elements in second half.
    int *ary, *ap;   // Pointers for temporary array.

    // The merged whole is temporarily stored here.
    assert ((ap = ary = new int[len]) != NULL);

    // While neither half is exhausted, look at smallest element in
    // each half, moving the smaller into the temporary array.
    while (p1 < data + half && p2 < data + len)
      if (*p1 < *p2)
        *ap++ = *p1++;
      else
        *ap++ = *p2++;

    // Still a few elements left in first half, move them over to the
    // temporary array.
    if (p1 < data + half)
      move(ap, p1, data + half - p1);
    else   // Elements left in the second half.  Move them.
      move(ap, p2, data + len - p2);

    // Move elements from the temporary array back to the original array.
    move(data, ary, len);


    delete [] ary;   // Discard the temporary array.
}

/**********************************************************************
 * move
 *
 * Move len ints from source to target.
 **********************************************************************/

void move(int *target, int *source, int len) {

    int i;

    for (i = 0; i < len; i++)
      *target++ = *source++;
}