|
|
|
Search and Sort Examples
1. Bubble Sort
Here's the algorithm to sort an array in ascending order: scan the list
repeatedly, comparing consecutive items and switching them if they are
in the wrong order.
Pass 1
92 27
16 57 14 38
27 92 16
57 14 38
27 16 92 57
14 38
27 16 57 92
14 38
27 16 57 14 92 38
27 16 57 14 38 92 92 bubbled to end
of list
Pass 2
27 16
57 14 38 92
16 27 57
14 38 92
16 27 57 14
38 92
16 27 14 57
38 92
16 27 14 38 57 92 enough: 92
already in place
etc.
% more bubSort.cpp
// Bubble Sort
#include<iostream>
using namespace std;
int main()
{
int a[] = {92, 27, 16, 57, 14, 38
};
int i, hold, size = 6;
cout << "The original array: " << endl;
for(i=0; i < size; i++)
{
cout << a[i] << " ";
}
cout << endl;
// Bubble sort
for (int pass=0; pass < size-1; pass++)
{
for(i=0; i < size-1; i++)
{
if( a[i] > a[ i+ 1] )
{
hold = a[i];
a[i] = a[i + 1];
a[i+1] =
hold; // swap
}
}
}
cout << "The sorted array: " << endl;
for(i=0; i < size; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
% g++ bubSort.cpp
% a.out
The original array:
92 27 16 57 14 38
The sorted array:
14 16 27 38 57 92
2. Binary Search
The binary search algorithm repeatedly divides a sorted list into a "left" part and
a "right" part. Variable left
is the index of the left-most element. Variable right is the index of the
right-most element. Variable key
holds the value we are searching for. The array is named list.
Set midpt = (left + right) / 2
if list[midpt] == key, return midpt
else if key > list[midpt] , set left = midpt + 1
else if key < list[midpt], set right = midpt -1
% cat binSearch.cpp
// Binary Search
#include <iostream>
using namespace std;
const int NUMEL = 10;
int binarySearch(int [], int, int); // declaration
int main()
{
int nums[NUMEL] = {5,10,22,32,45,67,73,98,99,101};
int item, location;
cout << "Enter the item you are searching for: ";
cin >> item;
location = binarySearch(nums, NUMEL, item);
if (location > -1)
cout << "The item was found at index location "
<< location
<< endl;
else
cout << "The item was not found in the
array\n";
return 0;
}
// this function returns the location of key in the list
// a -1 is returned if the value is not found
int binarySearch(int list[], int size, int key)
{
int left, right, midpt;
left = 0;
right = size -1;
while (left <= right)
{
midpt = (left + right) / 2;
cout << midpt << endl; // diagnostic
ouput statement
if (key == list[midpt])
{
return midpt;
}
else if (key > list[midpt])
left = midpt + 1;
else
right = midpt - 1;
}
return -1;
}
% g++ binSearch.cpp
% a.out
Enter the item you are searching for: 73
4
7
5
6
The item was found at index location 6
% a.out
Enter the item you are searching for: 80
4
7
5
6
The item was not found in the array
|
|
