Transcript 2-04-2005

February 4, 2005
Searching and Sorting Arrays
Searching
The Problem
Given an array of elements and a
particular element, determine whether that
element is in the array.
Linear Search
One obvious approach is to simply check
every element in the array.
Pros:
• conceptually simple
• easy to implement
Cons:
• slow for large arrays
int linearSearch(int list[], int numElements, int value)
{
int index=0;
int position = -1;
bool found = false;
while (index < numElements && !found)
{
if (list[index] == value)
{
found = true;
position = index;
}
index++;
}
return position;
}
Binary Search
The binary search is cleverer than linear
search.
Pros:
• Fast
• Fairly easy to implement
Cons:
• Values in array need to be in order
int binarySearch(int array[], int numElems, int value)
{
int first = 0;
int last = numElems-1;
int middle;
int position = -1;
bool found = false;
while (!found && first <=last)
{
middle = (first+last)/2; //calculate middle point
if (array[middle]==value)
{
found = true;
position = middle;
}
else if (array[middle]>value)
{
last = middle-1;
}
else
{
first = middle +1;
}
}
return position;
}
Sorting
The Problem
Given an array of elements, put them in
order.
There are many ways to do this.
The various ways differ in execution speed,
conceptual simplicity and in how easy they
are to implement.
Bubble Sort
Pro: Simplest way to sort
Con: Slowest way
The Idea
First put the elements one and two in order.
Then put elements two and three in order.
Then put elements three and four in order.
Etc.
After this process is over, you can be assured
of one thing – The largest element is in the
last position.
The Idea
Now forget about the largest element and
repeat the previous process on the
remaining elements.
After n-1 times, where n is the number of
elements in the array, the array will be
sorted.
Of course it may be sorted before n-1 times,
but you can’t guarantee that.
We say n-1 times is the worst case scenario.
#include <iostream>
#include <stdlib.h>
using namespace std;
void bubbleSort(int array[], int elems)
{
bool swap;
int temp;
do
{
swap = false;
for (int count =0; count < (elems-1); count++)
{
if (array[count] > array[count+1])
{
temp = array[count];
array[count]=array[count+1];
array[count+1]=temp;
swap=true;
}
}
} while (swap);
}
int main()
{
int values[] = {2,7,3,6,1};
bubbleSort(values, 5);
for (int i=0; i<5; i++)
{
cout << values[i] << " ";
}
cout << endl;
system("PAUSE");
return 0;
}
Application to 3n+1 Problem
Statement of Problem:
Take a positive integer.
If it is even, divide it by 2.
If it is odd, multiply it by 3 and add 1
Do this recursively: Stop if you get to 1.
e.g. 5 -> 16 -> 8 -> 4 -> 2 -> 1
Examples
17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5
We can stop here because we did 5 already
9->28->14 -> 7 -> 22 -> 11 -> 34 -> 17
The sequence for 27 takes 111 steps to get to 1
Question: Is there a number that does not go
to 1.
This question was first asked in 1937.
It remains unsolved.
All numbers up to 2 * 2^58 have been
checked as of December 16, 2004
If there are no such numbers, the problem is
to prove it. Some have said this problem is
to hard for modern day mathematics and
computer science.
Application of Searching to 3n+1
Write a function that takes a positive integer as an
input and returns the number of steps it takes to
get to 1. If it doesn’t go to 1 (!), the function will
never return.
Then create an array of one million random
integers, and a parallel array of the number of
steps to 0 for that random integer.
Using a search algorithm, you can investigate
what sorts of numbers are in the second array.
Perhaps there is a pattern.
Next Monday
Faster sorting algorithms