Chapter 10 - Algorithms
Looking for an element in a list can be
done in different ways, some are more
efficient than others. We could look at
all the elements in the list one by one
until the desired one is found, or we
could develop a better method.
Finding the Smallest Element
Input: An array a, of integers, with
indices start to end.
Output: The index of the smallest
element in the array.
Algorithm:
- Assume that the first element is the
minimum ( a[start] ).
- Look at all the elements from
a[start+1] to a[end], when a number
smaller than the minimum is found,
replace the minimum with it.
code:
int FindMin(IntArray a, int start, int end)
{
int min = a[start],
where = start;
for (i = start + 1 ; i <= end; i++)
if (a[i] < min)
{
min = a[i];
where = i;
}
return where;
}
Finding an element (linear search)
Input: An array a, of integers, with
indices 0 to end, an integer X
Output: The index of the first element in
the array that is equal to X. -1 if no
element matches X
Algorithm:
- Look at all the elements from 0 to end,
as soon as a match is found return the
index of the matching element,
- If the end of the array is reached and
no match is found, return -1.
Code:
int Find(IntArray a, int x, int end)
{
for (int i = 0; i <= end; i++)
if (a[i] == x)
return I;
return -1;
}
Finding an element (binary search)
If we had to search a large list of
elements, it would be of great help if the
list was sorted. This would allow us to
look only at the middle element of the
list, compare it to the element we are
trying to find, and then decide where to
continue the search.
This is known as binary search, a very
fast search algorithm.
int RFind(SortedArray a, int x, int start,
int end)
{
if (start == end)
return start;
else
{
int middle = (start + end) / 2;
if (x < a[middle])
return Rfind(a, x, start, middle);
else if (x > a[middle])
return Rfind(a, x, middle + 1, end);
else
return middle;
}
}
This piece of code is an example of
recursion. The Rfind function calls itself in
repeated ocasions until the problem is
solved.
Whenever we decide to solve a problem
recursively, we must use a function that
takes care of these two cases:
1. The exit case, when the problem is
solved at once.
2. The recursive case, when the
problem is solved by solving smaller
problems.
Sorting
A simple although not very efficient
algorithm is selection sort.
This algorithm finds the smallest
element in the list, marks where it is
found and swaps it with the first element
in the list. Then the process is repeated
starting at the next element in the list.
We go on until the end of the list is
found.
code:
void SelectionSort( IntArray& a, int start,
int end)
{
int k;
for (int i=start; i < end; i++)
{
k = findmin(a. i, end)
Swap(a[i], a[k]);
}
Faster Sorting (QuickSort)
This is a much faster algorithm than
selection sort. It uses recursion to
provide a more clever and more efficient
method of sorting the elements in an
array.
Input:
An array a of integers.
Output:
The same array of integers, sorted.
Algorithm:
If the list has more than 1 element, split
it and apply QuickSort to each resulting
sublist.
To split the list:
Choose a pivot value (the first array
element).
Set an index to the start of the list, and
one to the end of the list, left and right.
- Begin with left = start -1 and
right = end + 1
- While left < right
increment left until a[left] >= pivot
decrement right until a[right] <= pivot
Swap a[left] and a[right]
- Again swap a[left] and a[right]
Return split equals to right.
Code:
void QuickSort (IntArray& a, int start, int end)
{
if (start < end) {
int split = Partition(a, start, end);
QuickSort(a, start, split);
QuickSort(a, split+1, end);
}
}
int Partition (IntArray& a, int start, int end)
{
int top = end + 1, bottom = start -1;
int pivot = a[start];
while (top > bottom) {
do {bottom ++; }
while (a[bottom] < pivot);
do {top--;}
while (a[top] > pivot);
Swap(a[top], a[bottom]);
}
Swap(a[top], a[bottom]);
return top;
}