Searching and Sorting

Searching and Sorting Notes

Searching

Sequential Search
Sequential Search
Output

set low to 0
set high to size of array - 1
while high >= low
  calculate mid
  if searchfor < array[mid]
    high = mid -1
  else if searchfor == array[mid]
     answer is mid
  else
     low = mid + 1

Binary Search

Sorting

Bubble sort bubbles the highest number up each pass

int i, j;

for (i=nElems-1; i > 0; i--)  //all elems (exc 1st)
     for (j=0; j<; 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<; j++)   // N-1 + N-2 + ... + 2 + 1= N(N-1)/2
         if (a[j] > a[j+1])
            swap(j, j+1);

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);
     }

More sorting in CpSc 374