# 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.
• 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.
Examples (What do these do?):
```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++;
}
```

Thomas P. Kelliher
Thu Mar 21 09:37:30 EST 1996
Tom Kelliher