In a linear search we search an array for an element by starting at the first element in the array and traversing till we find the element.
From the book.
int searchList(const int list[], int numElems, int value)
{
int index = 0; // Used as a subscript to search array
int position = -1; // To record position of search value
bool found = false; // Flag to indicate if the value was found
while (index < numElems && !found)
{
if (list[index] == value) // If the value is found
{
found = true; // Set the flag
position = index; // Record the value's subscript
}
index++; // Go to the next element
}
return position; // Return the position, or -1
}
If we have an array of 10 elements and we can assume that each element has the same likelihood to be searched then the number of comparisons needed by our algorithm is
1 for position 0
2 for position 1
10 for position 9
The average number of comparisons is 1+2 +3 ..+ 10 = 55 /10 = 5.5 .
This makes sense since 5 is about the middle of the array.
Binary search assumes that the elements are sorted to begin with.
Ex:
1 2 4 5 7
Let's assume our array contains the above.
Let's assume our array contains the above and we are looking for the number 1 . Our pseudo code starts like this.
LeftIndex = 0
RightIndex = 4
We take the middle
middle = LeftIndex + RightIndex / 2
and compare the number with 1. 4 is not equal to 1 . That tells us if the number 1 did exist then it must be to the left of the number 4 since the array is sorted.
So now our RightIndex becomes 2-1 which is 1 .
middle = LeftIndex + RightIndex / 2
middle = 0 + 1 / 2 = 0
Now we compare middle value of 1 with the value that we are searching for and that value is 1 so we are done. We keep narrowing our subsection of the array till our value is either found or not found.
Since we cut the array by 2 every time we only need log n worst case searches where the base is 2 .
In bubble sort the array is traversed from left to right and the maximum element is placed to the right.
Ex:
4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4
//The element 4 is exchanged with the right element and bubbles to the right.
2 3 1 4
2 1 3 4
//Now 3 has been placed to the right
1 2 3 4
//Now 2 is placed to the right and we have a sorted array.
Ex1:
#include <iostream>
#include <stdlib.h>
#include <time.h> /* time */
using namespace std ;
int searchList(const int list[], int numElems, int value)
{
int index = 0; // Used as a subscript to search array
int position = -1; // To record position of search value
bool found = false; // Flag to indicate if the value was found
while (index < numElems && !found)
{
if (list[index] == value) // If the value is found
{
found = true; // Set the flag
position = index; // Record the value's subscript
}
index++; // Go to the next element
}
return position; // Return the position, or -1
}
int main()
{
int arr1[] = { 1, 2, 3, 4, 5 , 6, 7, 8, 9, 10 } ;
cout << searchList( arr1, 10, 3 ) << endl ;
return (0) ;
}
Convert the function "searchList" to use a for loop instead of a while loop.
Ex2:
Below is the bubble sort algorithm from the book. The for loop runs to (size-1 ) every time. Is this necessary ? Modify the algorithm so that the loop does not run to the end.
#include <iostream>
using namespace std ;
void showArray(const int array[], int size)
{
for (int count = 0; count < size; count++)
cout << array[count] << " ";
cout << endl;
}
void sortArray(int array[], int size)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (size - 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 arr1[] = { 5 , 4 , 3 , 2 , 1 } ;
sortArray( arr1, 5 ) ;
showArray( arr1 , 5 ) ;
return ( 0 ) ;
}
Ex3:
Selection sort from the book is:
void selectionSort(int array[], int size)
{
int startScan, minIndex, minValue;
for (startScan = 0; startScan < (size - 1); startScan++)
{
minIndex = startScan;
minValue = array[startScan];
for(int index = startScan + 1; index < size; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
array[minIndex] = array[startScan];
array[startScan] = minValue;
}
}
Modify the code so that instead of the minimum element being placed in the first position we are placing the max element in the last position.
Sol1:
#include <iostream>
#include <stdlib.h>
using namespace std ;
int searchList(const int list[], int numElems, int value)
{
int index = 0; // Used as a subscript to search array
int position = -1; // To record position of search value
bool found = false; // Flag to indicate if the value was found
for( int i1=0 ; i1 < numElems ; i1++ )
{
if( list[i1] == value )
return i1 ;
}
return position; // Return the position, or -1
}
int main()
{
int arr1[] = { 1, 2, 3, 4, 5 , 6, 7, 8, 9, 10 } ;
cout << searchList( arr1, 10, 3 ) << endl ;
return (0) ;
}
Sol2:
#include <iostream>
using namespace std ;
void showArray(const int array[], int size)
{
for (int count = 0; count < size; count++)
cout << array[count] << " ";
cout << endl;
}
void sortArray(int array[], int size)
{
bool swap;
int temp;
int right = size - 1 ;
do
{
swap = false;
for (int count = 0; count < right ; count++)
{
if (array[count] > array[count + 1])
{
temp = array[count];
array[count] = array[count + 1];
array[count + 1] = temp;
swap = true;
}
} //for
right-- ;
} while (swap);
}
int main()
{
int arr1[] = { 5 , 4 , 3 , 2 , 1 } ;
sortArray( arr1, 5 ) ;
showArray( arr1 , 5 ) ;
return ( 0 ) ;
}
Sol3:
#include <iostream>
using namespace std ;
void showArray(const int array[], int size)
{
for (int count = 0; count < size; count++)
cout << array[count] << " ";
cout << endl;
}
void selectionSort( int array[], int size )
{
int startScan, minIndex, minValue;
for (startScan = 0; startScan < (size - 1); startScan++)
{
minIndex = startScan;
minValue = array[startScan];
for(int index = startScan + 1; index < size; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
array[minIndex] = array[startScan];
array[startScan] = minValue;
}
}
void selectionSort1( int array[], int size )
{
int startScan, maxIndex, maxValue;
int k1 = size-1 ;
//showArray( array , 4 ) ;
for (startScan = k1; startScan > 0 ; startScan-- )
{
maxIndex = 0 ;
maxValue = array[0] ;
for(int index = 0; index <= startScan; index++)
{
if (array[index] > maxValue)
{
maxValue = array[index];
maxIndex = index;
}
}
array[ maxIndex ] = array[ startScan ] ;
array[ startScan ] = maxValue;
showArray( array , 4 ) ;
//break ;
//k1-- ;
} //for
}
int main()
{
//int arr1[] = { 5 , 4 , 3 , 2 , 1 } ;
int arr1[] = { 3 , 4 , 2 , 1 } ;
selectionSort1( arr1, 4 ) ;
//showArray( arr1 , 4 ) ;
return ( 0 ) ;
}