Discrete Structures
Sneek back to Chpt 3.1 Algorithms
Def 1: An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.
Example
Describe an algorithm for finding the maximum value in a finite sequence of integers.
Any ideas??
Algorithm 1:
Finding the maximum element in a finite sequence:
procedure max(a1, a2, a3.......an: integers)
max=a1
for i=2 to n
if max <ai then max = ai
{max will be the largest element}
General properties that algorithms share:
- input - An algorithm has input values from a specified set.
- output -From each set of input values an algorithm produces output values from a specidied set. The output values are the solution to the problem.
- Definiteness - The steps of an algorithm MUST be defined PRECISELY.
- Correctness - An algorithm should produce the correct output values for each set of input values.
- Finiteness - An algorithm produce output after a finite number of steps for any input in the set.
- Effectiveness - It must be possible to perform each step of an algorithm exactly and in a finite amount of time.
- Generality - The procedure should be applicable for all problems of the desired form, not just for a particular set of input values.
Linear Search in C:
This is a very straightforward loop comparing every element in the array with the key. As soon as an equal value is found, it returns. If the loop finishes without finding a match, the search failed and -1 is returned.
For small arrays, a linear search is a good solution because it's so straightforward. In an array of a million elements, a linear search will take, on average, 500,000 comparisons to find the key. For a much faster search, take a look at binary search. Example:
int linearSearch(int a[], int first, int last, int key) {
// function:
// Searches a[first]..a[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -1.
// parameters:
// a in array of (possibly unsorted) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -1 if key is not in the array.
for (int i=first; i<=last; i++) {
if (key == a[i]) {
return i;}
}
return -1; // failed to find key
}
Binary Search in C:
#include <stdio.h>
#define SIZE 15
int binarySearch( const int b[], int searchKey, int low, int high );
int main() {
int a[ SIZE ];
int i;
int key = 10;
int result = -1;
for ( i = 0; i < SIZE; i++ ) {
a[ i ] = 2 * i;
}
result = binarySearch( a, key, 0, SIZE - 1 );
if ( result != -1 ) {
printf( "\n%d found in array element %d\n", key, result );
} else {
printf( "\n%d not found\n", key );
}
return 0;
}
int binarySearch( const int b[], int searchKey, int low, int high )
{
int middle;
while ( low <= high ) {
middle = ( low + high ) / 2;
if ( searchKey == b[ middle ] ) {
return middle;
} else if ( searchKey < b[ middle ] ) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
Sorting Algorithms in C:
Bubble Sort
Bubble Sort is probably one of the oldest, most easiest, straight-forward, inefficient sorting algorithms. It is the algorithm introduced as a sorting routine in most introductory courses on Algorithms. Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is "bubbled" to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of "selecting" maximum values, they are bubbled to a part of the list. An implementation in C.
void BubbleSort(int a[], int array_size)
{
int i, j, temp;
for (i = 0; i < (array_size - 1); ++i)
{
for (j = 0; j < array_size - 1 - i; ++j )
{
if (a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
A single, complete "bubble step" is the step in which a maximum element is bubbled to its correct position. This is handled by the inner for loop.
for (j = 0; j < array_size - 1 - i; ++j )
{
if (a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
6 8 3 1 2 5 4 10 } pass 1
6 3 1 2 5 4 8 10 } pass 2
3 1 2 5 4 6 8 10 } pass 3
1 2 3 4 5 6 8 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
The above tabulated clearly depicts how each bubble sort works. Note that each pass results in one number being bubbled to the end of the list.
Selection Sort
The idea of Selection Sort is rather simple. It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where its supposed to be. The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list. The below is an implementation of the algorithm in C.
void SelectionSort(int a[], int array_size)
{
int i;
for (i = 0; i < array_size - 1; ++i)
{
int j, min, temp;
min = i;
for (j = i+1; j < array_size; ++j)
{
if (a[j] < a[min])
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
Consider the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
1 6 10 3 8 2 5 4 } pass 1
1 2 10 3 8 6 5 4 } pass 2
1 2 3 10 8 6 5 4 } pass 3
1 2 3 4 8 6 5 10 } pass 4
1 2 3 4 5 6 8 10 } pass 5
1 2 3 4 5 6 8 10 } pass 6
1 2 3 4 5 6 8 10 } pass 7
At pass 0, the list is unordered. Following that is pass 1, in which the minimum element 1 is selected and swapped with the element 8, at the lowest index 0. In pass 2, however, only the sublist is considered, excluding the element 1. So element 2, is swapped with element 6, in the 2nd lowest index position. This process continues till the sub list is narrowed down to just one element at the highest index (which is its right position).
Insertion Sort
The Insertion Sort algorithm is a commonly used algorithm. Even if you haven't been a programmer or a student of computer science, you may have used this algorithm. Try recalling how you sort a deck of cards. You start from the begining, traverse through the cards and as you find cards misplaced by precedence you remove them and insert them back into the right position. Eventually what you have is a sorted deck of cards. The same idea is applied in the Insertion Sort algorithm. The following is an implementation in C.
void insertionSort(int a[], int array_size)
{
int i, j, index;
for (i = 1; i < array_size; ++i)
{
index = a[i];
for (j = i; j > 0 && a[j-1] > index; j--)
a[j] = a[j-1];
a[j] = index;
}
}
Examine the following table. (Note that each pass represents the status of the array after the completion of the inner for loop, except for pass 0, which represents the array as it was passed to the function for sorting)
8 6 10 3 1 2 5 4 } pass 0
6 8 10 3 1 2 5 4 } pass 1
6 8 10 3 1 2 5 4 } pass 2
3 6 8 10 1 2 5 4 } pass 3
1 3 6 8 10 2 5 4 } pass 4
1 2 3 6 8 10 5 4 } pass 5
1 2 3 5 6 8 10 4 } pass 6
1 2 3 4 5 6 8 10 } pass 7
The pass 0 is only to show the state of the unsorted array before it is given to the loop for sorting. Now try out the deck-of-cards-sorting algorithm with this list and see if it matches with the tabulated data. For example, you start from 8 and the next card you see is 6. Hence you remove 6 from its current position and "insert" it back to the top. That constitued pass 1. Repeat the same process and you'll do the same thing for 3 which is inserted at the top. Observe in pass 5 that 2 is moved from position 5 to position 1 since its < (6,8,10) but > 1. As you carry on till you reach the end of the list you'll find that the list has been sorted. It didn't take a course to tell you how to sort a deck of cards, did it; you prolly figured it out on your own. Amazed at the computer scientist in you ? ;)