The selection sort algorithm is a sorting algorithm that selects the smallest element from an array of unsorted elements called a pass. In each pass, it selects an unsorted element from the array and compares it with the rest of the unsorted array.
If any element smaller than the current smallest is found, replace it with a new element. This process is repeated until there are no more small elements. The entire array is sorted in this way.
The steps performed in each pass is as follows.
Given an array, .
Find the smallest element in the array, .
Replace with with the resultant smallest element and repeat the process again for , and so on.
Stop the search process when smallest elements are found, the last one is the largest in the array.
Selection-Sort Algorithm
Algorithm Selection-Sort(A)
{
for i = 1 to n-1
i:= min
for j:= i +1 to n
if A[j] < A[min]) then
T: = A[min]
A[min] := A[j]
A[j] := T
}
The running time of the selection sort algorithm is then for both best-case and worst-case. Even in best-case, we will run a comparison in sub-array in the same manner as worst-case. Thus, the running time is .
The hash table is perfect solution to store dictionary where each data is uniquely identified using a key. The dictionaries are implemented using arrays. The key are stored with the object itself and each data element has its own index value. Therefore, data is stored in the array as key-value pair.
The hash table uses a hash function which is a mathematical function to compute a hash value which is the index L of the data element in the array. The hash function uses key to compute .
The hash table allows three types of operations.
Insertion of a new value.
Deletion of an existing value.
Search for a value in the array.
Direct Addressing Scheme
The hash table uses a numerical key or characters that are converted to numeric equivalent for computing the hash value where is the index of data element in the array.
Suppose is the universal set of all keys from where we use to map from an array of size It means every is mapped to every . Also, no two keys have same hash value.
This type assigning a unique value to each an every data element in array is called direct-addressing.
Example
In this example, our universe U = { all English letters } from where we get our keys . The size of the array is where is equal to , the size of the array.
Each letter is a key is converted to a number equivalent to its position in the English alphabets. For example, A = 1, B = 2, and so on.
Key
Hash Function
Hash Value
A
H(A)
1
B
H(B)
2
C
H(C)
3
D
H(D)
4
T
H(T)
20
V
H(V)
22
X
H(X)
24
Y
H(Y)
25
Z
H(Z)
26
Table 1 English letters as key
The direct-addressing is fine as long as the size of the data elements are small in number. Therefore, using a unique key for each an every element is impractical and difficult to maintain. We can use a small subset of keys from universal set of keys where .
Another problem with direct addressing is computer memory, we cannot store all the values of array because memory size is limited.
Finally, the direct addressing requires you to use the whole array regardless of whether you want to store anything or not. The empty spaces are wasted.
Hash Function
If we are to use a small subset of keys such that maps all elements of array where is the size of the array. Each array position has an index value .
Figure 1 – Hash function takes the key value and compute the index of the array
Hash function is a mathematical function such as a mod function which is a popular method of computing hash value. If range of the array is , for any key ,
\begin{aligned}
&H(k_{i}) = L_{i}\\
&H(k_{i}) = k_{i} \hspace{2 mm} MOD \hspace{2 mm} N
\end{aligned}
The MOD function takes a value as key and gives remainder as output. In this way, more than one key value or index will have same hash value.
Figure 2 – The key is 24 and hash value is 4 which corresponds to index in the array.
In the figure above, we have key and which is size of the array. A MOD operation on key gives which is the location of the data element in the array.
Similarly, if , then hash value is again. Therefore, we want a hash function which always gives same results for a key. The key values with same hash value are called synonyms.
Synonyms
We can treat hash value or index in an array as a bucket holding slots for each synonym. So, a bucket can be can have slots. Such type of representation requires a two-dimensional array where a row indicates buckets with slots.
Figure 3 – Each row is a bucket with m number of slots
The figure above shows that the first column of the two dimensional array is buckets and other columns are slots.
Example
Let be set of keys and size of array be . The hash function we are going to use is .
Figure 4 – Each row is a bucket that has 3 slots to store data elements with same hash value.
Each of the row in above figure has 3 slots per bucket to store values that have same hash values. for example,
\begin{aligned}
&77\hspace{2 mm} MOD \hspace{2 mm}10 = 7\\
&87\hspace{2 mm} MOD \hspace{2 mm} 10 = 7
\end{aligned}
Since, two slot have same value, it will cause problem during hash table operations – insertion, deletion and search.
Collision
When hash value is computed using hash function and if two keys and has same hash value then it cause a collision.
The Fibonacci search algorithm is another variant of binary search based on divide and conquer technique. The binary search as you may have learned earlier that split the array to be searched, exactly in the middle recursively to search for the key. Fibonacci search on the other hand is bit unusual and uses the Fibonacci sequence or numbers to make a decision tree and search the key.
Like binary search, the Fibonacci search also work on sorted array ( non-decreasing order).
The Fibonacci Sequence
Simply said the Fibonacci sequence is a set of numbers where any term is equal to the sum of previous two terms.
F_{n} = F_{n-1} + F_{n-2}
If we try to generate first few terms of a Fibonacci sequence then we get the following numbers.
Algorithm Fibonacci_Search(A, n, key)
{
low:= 0
high:= n - 1
loc:= -1
flag:= 0
while(flag != 1 && low <= high)
{
// get the fibonacci f[m-1] < n
index:=get_fibonacci(n)
if ( key == A[index + low]) then
{
flag:= 1
loc:= index
break
}
else if ( key > A[index + low] ) then
{
//adjust the low
low:= low + index + 1
}
else
{
//adjust the high
high:= low + index - 1
}
//adjust the n
n:= high - low + 1
} // end of while
//return success or not
if ( flag = 1) then
{
return (loc + first + 1 )
}
else
{
return -1
}
} //end
Algorithm Fibonacci(n)
{
fibk2:= 0
fibk1:= 1
fibk:= 0
if ( n = 0 || n = 1) then
return 0
while ( fibk <n)
{
fibk:= fibk2 + fibk1
fibk2:= fibk1
fibk1:= fibk
}
return fibk2;
}
How Fibonacci Search Works?
Fibonacci search uses the Fibonacci numbers to create a search tree. These are the steps taken during Fibonacci search.
Step 1:
The first step is to find a Fibonacci number that is greater than or equal to the size of the array in which we are searching for the key.
Suppose the size of the array is and fibonacci number is . We must find a such that
and Let and If key > A[8] is true, Then search A[9:9] = { 88 }
Step 6:
If the key is not found, repeat the step step 1 to step 5 as long as , that is, Fibonacci number >= n. After each iteration the size of array is reduced.
Fibonacci Search Example
In this example, we will take a sorted array and find the search key with the array using Fibonacci search technique. Each iteration will show you the state of lower index, higher index and current value of size n, and Fibonacci number used to locate the key.
Consider the following sorted (non-decreasing) array with 10 elements.
Iteration 1
Figure 1- Sorted array with 10 elements
There are 10 elements in the above sorted array S. Therefore,
low = 0
n = 10
high = n-1 = 9
index = get_fibonacci(n) = 8 //because F_{k} = 13
loc = -1 //currect location of the key is outside array
flag = 0 //check whether key is found or not , flag = 1 indicates it is found
key = 65 // we are trying to find 65 in the array
is key == S[ index + low] ?
65 == 81 => NO
is key > S [ index + low] ?
65 > 81 => NO
is key < S[ index + low ] ?
65 < 81 =>YES
high = low + index - 1 // adjust the higher index and keep the low = 0
high = 0 + 8 - 1 = 7
n = high - low + 1 // adjust the size of the array
n = 7 - 0 + 1 = 8
Iteration 2
Figure 2- key is less than S[8]. We must search left sub-tree. The array size n is adjusted to 8 elements.
There are 8 elements in the above sorted array S. Therefore,
low = 0
n = 8
high = 7
index = get_fibonacci(n) = 5 //because previous F_{k} = 8
loc = -1 //currect location of the key is outside array
flag = 0 //check whether key is found or not , flag = 1 indicates it is found
key = 65 // we are trying to find 65 in the array
is key == S[ index + low] ?
65 == 54 => NO
is key > S [ index + low] ?
65 > 54 => YES // key is higher than the array element S[5], move to right sub=-tree
low = low + index + 1 // adjust the lower index and keep the high = 7
low = 0 + 5 + 1 = 6
n = high - low + 1 // adjust the size of the array
n = 7 - 6 + 1 = 2
Iteration 3
Figure 3 – We now have only two elements in the array to search the key
There are 2 elements in the above sorted array S. Therefore,
low = 6
n = 2
high = 7
index = get_fibonacci(n) = 1 //because previous F_{k} = 5
loc = -1 //currect location of the key is outside array
flag = 0 //check whether key is found or not, flag = 1 indicates it is found
key = 65 // we are trying to find 65 in the array
is key == S[ index + low] ?
65 == 75 => NO
is key > S [ index + low] ? // key is higher than the array element S[1], move to right sub=-tree
65 > 75 => NO
is key < S[ index + low ] ? // key is higher than the array element S[1], move to left sub=-tree
65 < 81 =>YES
high = low + index - 1 // adjust the lower index and keep the high = 7
high = 6 + 1 - 1 = 6
n = high - low + 1 // adjust the size of the array
n = 6 - 6 + 1 = 1
Iteration 4
Figure 4 – Now only one element is remained in the array which is the key
Only 1 element remained in the array, still we must go through the iteration.
low = 6
n = 1
high = 6
index = get_fibonacci(n) = 0 // because when n = 0 or n = 1, simply return 0.
loc = -1 //currect location of the key is outside array
flag = 0 //check whether key is found or not , flag = 1 indicates it is found
key = 65 // we are trying to find 65 in the array
is key == S[ index + low] ? // A[ 6 + 0] = S[6] = 65
65 == 65 => YES
flag = 1
Key is found !
Time Complexity of Fibonacci Search
Here is the Fibonacci search decision tree for .
Figure 5- Fibonacci Search Decision Tree
The Fibonacci search also perform like binary search on a sorted array; therefore, the time complexity is in worst case is .
We can clearly note a few things from the above decision tree.
If the difference in index of grandparents and parent of a node is then
The left sub-tree is of order .
The left sub-tree is of order .
This is true for every sub-tree.
The difference between parent and both children is the same.
The leftmost path represents a Fibonacci sequence that starts with 0, 1, 2, 3, … .
C++ Implementation Of Fibonacci Search Algorithm
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
int get_fib(int);
int main()
{
int S[10]= { 5, 23, 34, 42, 48, 54, 65, 75, 81, 95 };
int n,key, index, low, high, loc, flag;
n = 10;
low = 0;
int location = -1;
high = n-1;
flag = 0; //Read the key
cout << "Enter Key To Search:";
cin >> key;
index = 0;
while ( flag != 1 && low <= high)
{
index = get_fib(n);
if ( key == S[index + low])
{
location = low + index;
flag = 1;
break;
}
else if( key > S[index + low])
{
low = low + index + 1;
}
else
{
high = low + index -1;
}
n = high - low + 1;
}
if ( flag == 1)
{
cout << "Element Found at Index =" << location << endl;
}
getch();
return 0;
}
int get_fib(int n)
{
int fibk = 0;
int fibk2 = 0;
int fibk1 = 1;
if( n == 0 || n == 1)
{
return 0;
}
while(fibk < n)
{
fibk = fibk1 + fibk2;
fibk2 = fibk1;
fibk1 = fibk;
}
return fibk2;
}
Input
Enter Key To Search:65
Output
Element Found at Index = 6
In the next post, we shall discuss about searching though Hash Table.
The binary search algorithm is very popular search algorithm. It is also known as half-interval search or uniform binary search as it split the array of data into two equal parts recursively until a solution is found. The array in binary search must be sorted.
Binary search employ an algorithm design technique known as divide and conquer. In this technique, a given problem is divided into smaller sub-problems and this is done until no more sub-division is possible.
Then solution to the smallest problem is found and all solutions are combined to get the overall solution to the problem. The divide and conquer technique is not limited to binary search; therefore, we shall discuss this separately in another article.
Binary Search Algorithm
Algorithm Binary Search (S, n , key)
{
low := 0
high = n - 1
while (low <= high)
{
//compute the mid value
mid = low + (high - low)/2
if (key < S[mid]) then
high := mid - 1
else if ( key > S[mid]) then
low := mid + 1
else
return mid
}
}
The elements of binary search are as follows.
– The sorted array with data.
– It is the number of elements in the array.
– The search key to be found.
Mid Value
The mid value is most important in binary search as it split the array in to two parts. Then the sub-array is split in the similar way based on divide and conquer technique. The mid is an index of the element in the middle of the array.
mid = low + (high - low)/2
How Binary Search Works?
The binary search works on a sorted array. Suppose we have an array with elements in non-decreasing order. To search for a given key, binary search will compute the mid value and thus break the array into equal halves. The key is compared with array element with index value as mid.
The high and low are equal which will be last iteration of while loop in the binary search algorithm. However, is still calculated for the last iteration.
How much time binary search take on average to search for an element in the array ? Before we try to answer that question, let us understand the decision tree for binary search.
Figure 5 – Decision Tree for Binary Search
A decision tree is the pattern that the binary search follows to get to the element. Suppose that each of the node in binary search has two child including the root. Then the total number of nodes in the decision tree is given by the equation.
\begin{aligned}
&N <= 2^L - 1\\
&N + 1 <= 2^L\\
&Where \\
&N \hspace{1mm} is \hspace{1mm}total \hspace{1mm} number \hspace{1mm} of \hspace{1mm} nodes\hspace{1mm} in \hspace{1mm} the\hspace{1mm} decision\hspace{1mm} tree.\\
&L \hspace{1mm} is \hspace{1mm} the \hspace{1mm} number\hspace{1mm} of \hspace{1mm}levels\hspace{1mm} in \hspace{1mm} the\hspace{1mm} decision\hspace{1mm} tree.
\end{aligned}
The decision tree above is from an array of size where is the mid value. If we compute other mid values we get the above decision tree. The difference between parent and child is where .
Relationship between Nodes and Elements of Sorted Array
In the above decision tree, we have number of elements that match with the tree. Each of the node in the decision tree has exactly 2 child. But this is not possible all the time because number of elements of an array for binary search can be different.
Figure 6- Decision Tree for Array with size 10.
Therefore,
\begin{aligned}
&N + 1 >= n + 1\\
&where \\
&N + 1 \hspace{1mm}is \hspace{1mm}the\hspace{1mm} number\hspace{1mm} of\hspace{1mm} nodes\hspace{1mm} in the\hspace{1mm} tree\\
&n + 1\hspace{1mm} is \hspace{1mm}the \hspace{1mm}number \hspace{1mm}of \hspace{1mm}elements\hspace{1mm} in \hspace{1mm}the \hspace{1mm}array
\end{aligned}
Using the above information we can say that
2^L >= N + 1 >= n + 1
Taking log of equation will give us, . Therefore, the time complexity of binary search in average and worst case is given as .
C++ Implementation of Binary Search
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
int main()
{
int S[10] = { 6, 23, 34, 42, 48, 54, 65, 75, 81, 95};
int key,low,high;
int mid= 0;
//Read key value
cout <<"Enter your key:" ;
cin >> key;
low = 0;
high = 9;
//Binary search
while(low <= high)
{
mid = low + (high - low)/2;
if (key < S[mid])
{
high = mid - 1;
}
else if ( key > S[mid])
{
low = mid + 1;
}
else
{
cout <<"Key found at " << mid << ": " << S[mid]<<endl;
return mid;
}
}
}
Input:
Enter your key: 65
Output:
Key found at 6: 65
In the next article, we will discuss another variant of binary search called the interpolation search.
The interpolation is an advanced version of binary search algorithm. It performs better than the binary search algorithm for large data sets.
Remember how we look for a word in the dictionary. If you want to search for word “Cat” immediately we open that part of the dictionary because we have an idea about where to look for that word. A word that starts with letter ‘T’ then you would jump to that location in the dictionary which contains all words that start from letter ‘T’. The interpolation search is inspired by this idea of finding the key based on its probed position from the beginning of the array.
Like binary search, the interpolation search also need a sorted array.
Interpolation Search
Algorithm interpolation_search(S, n, Key)
{
low := 0
high := n - 1
mid := 0
while ((S[high] != S[low]) && (key >= S[low]) && (key <= S[high])) {
mid = low + ((key - S[low]) * (high - low) / (S[high] - S[low]));
if (S[mid] < key)
low = mid + 1;
else if (key < S[mid])
high = mid - 1;
else
return mid;
}
if (key = S[low])
return low
else
return -1
}
In the above pseudo code we have following
S[ ] – It is the array with n elements.
n – It is the number of elements in the given array.
Key – it is the search key we are trying to locate within the array.
low – lowest index which start at 0
high – highest index which is n-1 if low starts at 0.
mid – middle value of the array.
How Interpolation Search Works?
Suppose you have to search a number between 0 to 99. You are given an array of size 10 to search and all number are equally distributed. Consider the image below.
Figure1- DistribFigure1- Distribution of numbers into 10 array positions with low = 1 and high =10
Each position has a separate range of number possible because the array must be sorted. So, in first position we can have any number from 0-9 and second position we can have a number between 20-29 and so on.
The numbers may or may not be equally distributed. Suppose if the numbers are equally distributed as per the figure below.
Figure2 -Sorted array with equally distributed values.
The interpolation search will use the following equation to probe the position of middle (mid) element. If right index is found return the index or continue the probe.
We were directly able to probe the correct position of the search key 35.
Let us consider another situation where array is not distributed equally, however, the array is sorted in non-decreasing order. See the image below.
Figure 3 – Interpolation array is not distributed equally,but sorted in non-decreasing order
In this array, we must search for key = 86 using interpolation search technique. The algorithm determine if the search key falls within the range S[low] and S[high], otherwise it will report false and terminate.
The next step is to compute the mid value using equation of mid.
By probing the correct position or even closer to the key in an array, the interpolation search takes full advantage of the sorted array where binary search will take more steps by splitting the array into half the size repeatedly. In smaller searches the binary search may be faster than interpolation search, but if you have an extremely big data to search interpolation search algorithm will take less time.
In the above example, to search for key = 86, the interpolation search took 2 steps to complete. The above computation will give you an idea that the binary search is not good when compared with interpolation search while working on a large data set.
Time Complexity
On average the interpolation search perform better than binary search.The time complexity of binary search in average case and worst case scenario is .
The interpolation search on average case has assuming that the array is evenly distributed. If the array is increasing exponentially then the worst case happens. Then we must compare the search key to each element of the array. This will give a time complexity of .
C++ Implementation of Interpolation Search
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
int main()
{
int S[10] = { 6, 22, 29, 34, 43, 57,66, 86, 88, 96};
int key,low,high;
int mid= 0;
//Read key value
cout <<"Enter your key:" ;
cin >> key;
low = 0;
high = 9;
//Interpolation search
while((S[low] != S[high]) && (key >= S[low]) && ( key <= S[high]))
{
mid = low + ((key - S[low]) * (high - low)/(S[high] - S[low]));
if (S[mid] < key)
{
low = mid + 1;
}
else if ( key < S[mid])
{
high = mid - 1;
}
else
{
cout <<"Key found at " << mid << ": " << S[mid]<<endl;
return mid;
}
}
if ( key == S[low])
{
return low;
}
else
{
return -1;
}
}
Earlier you learned about linear search which search for a key from a given array. The search is affected by whether the array is ordered or unordered. The performance get better if the key is found at the beginning of the array. The transpose sequential search does that for repeated searches. It is also known as self-organizing linear search.
With each time you search for a key in the array, the transpose sequential search will shift the key at the beginning of the array. Therefore, next time you search for the same key you will find it in less time.
Transpose Sequential Search Algorithm
//Algorithm : Transpose Sequential Search
Algorithm Transpose_Sequential_Search(S, n, K)
{
i := 0
while (i < n and K != S[i]) do
{
i := i + 1 // move through the array as long as K is not matching any element
}
if K = S[i] then
{
print ("Key found !")
swap( S[i], S[i-1])
}
else
{
print ("Key not found !")
}
}
In the algorithms above,
– It is the search key which we are trying to locate in the array.
– It is the array of numbers.
– it is the number of elements in the array.
Example #1
Suppose there is an array of numbers and we want to search for a key . We will do the usual search, but repeat our search several times for the same key . This will show us the use of transpose sequential search in repeated searches.
Let \hspace{1mm}S[0: 9] = \{ 42, 54, 10, 59, 32, 11, 77, 21, 99, 66 \} \hspace{1mm} and \hspace{1mm} search \hspace{1mm} key \hspace{1mm} be \hspace{1mm} K = 99.
We will do repeated search for in following way.
99, 10, 99, 32, 99
In between our searches, we are trying to search other numbers also, so that it look natural. With each search attempt the original array will change in following way.
Figure 1 – Each search attempt will improve the position of search key 99
Each of the search will swap the search key with its previous element, if we are searching for , first it gets found and then it is swapped with previous element initially. With each subsequent search the position of goes to the beginning of the array.
Time Complexity of Transpose Sequential Search
If the search key is at the end of the array then it is worst case scenario and time taken is . Each search attempt improves the position and the search is done in constant time .
C++ Implementation of Transpose Sequential Search
PROGRAM : TRANSPOSE SEQUENTIAL SEARCH
#include <iostream.h>
#include <stdio.h>
int main()
{
//Declare all variables and the array
int S[] = { 42, 54, 10, 59, 32, 11, 77, 21, 99, 66 };
int K;
int temp = 0;
int n = 10;
int i = 0;
// Read the input value
cout << "Input the value of K: ";
cin >> K;
while (i < n && K != S[i])
{
i = i + 1; //Move through the array
}
if(K == S[i])
{
cout << "Key Found!" << endl;
//swap
temp = S[i];
S[i] = S[i-1];
S[i-1] = temp;
cout << S[i-1];
}
else
{
cout << "Item not found" << endl;
}
return 0;
}
Input:
Input the value of K: 99
Output :
Key Found!
99
In the next article, you will learn about some other forms of linear search algorithms.
The linear search is the simplest search where we try to find an element K from the list L. We have to compare K with each and every item in the list. The search is affected when the list if sorted or unsorted.
Linear Search
Suppose we want to find search key from array with elements
\{ s_1, s_2, s_3, s_4,\cdots,s_n \}
There is two possible situations.
The array is ordered from lowest to highest.
The array is unordered.
If the array is sorted then the search is called an ordered linear search. If a search is performed on unordered array then it is called an unordered linear search.
Unordered Linear Search
Algorithm Ordered_Linear_Search ( S, n, K)
{
// S[0: n-1] is the array with n sorted elements
// n is the total number of elements in the array
// K is the key we are trying to find in the array S
i : = 0
while (i < n and K > S[i]) do //keep moving through the elements
{
i := i + 1
}
if K = S[i] then
print("Key found!")
return(i) // return the index of the element found
else
print("Key not found!")
}
In the above algorithm, we have following:
– An array with n elements that is sorted already.
– It is the number of elements in the array. The array starts with index and that last element has an index of .
– It is the value we are searching within the array. If found then algorithm return the location index of else it will simply print “Not found”. is called the search key.
We want to search for in the array. The algorithm goes through each item in the array as long as
is greater than element , that is, is greater than any element in the array keep moving.
When is equal to any element ,that is, . We have found the element successfully and return the index value.
In the above example, are less than ; therefore, search algorithm will skip all of these elements and stop at which is true. The index is returned.
Note that the ordered linear search will not continue anymore and terminate successfully.
Figure 1 – Ordered Linear Search
Time Complexity of Ordered Linear Search
Since the array is ordered, it is easy to compute the time complexity. If the search key is at the beginning which is the best case, it takes constant time to find the element.
What if the element is not available ? The algorithm goes through each and every element in the array. If array has n element then the complexity is which is the worst case.
C++ Implementation Of Ordered Linear Search
//PROGRAM: ORDERED LINEAR SEARCH
#include <iostream.h>
#include <stdio.h>
int main()
{
//Declare all variables and the array
int S[] = {12,23,34,56,67,77,85,89,91,100};
int K;
int n = 10;
int i = 0;
// Read the input value
cout << "Input the value of K: ";
cin >> K;
while (i < n && K > S[i])
{
i = i + 1; //Move through the array
}
if(K == S[i]) //Check if the key is equal to any element in the array
{
cout << "Key Found!" << endl;
cout << "Location = " << i << endl;
}
else
{
cout << "Item not found" << endl;
}
return 0;
}
Program Input :
Input the value of K: 85
Program Output:
Key Found!
Location = 6
Unordered Linear Search
The unordered linear search is where the array has unordered elements. If we want to search for the key, then we must go through all elements.
Algorithm Unordered_Linear_Search ( S, n, K)
{
// S[0: n-1] is the array with n sorted elements
// n is the total number of elements in the array
// K is the key we are trying to find in the array S
i : = 0
while (i < n and K != S[i]) do //keep moving through the elements until a match is found
{
i := i + 1
}
if K = S[i] then
print("Key found!")
return(i) // return the index of the element found
else
print("Key not found!")
}
The above algorithms is similar to ordered linear search, however it does not search in ascending order or descending order. The array may contain the key value at any location.
Example #2
Suppose an unordered array contain following elements,
We want to search for in the array. The algorithm goes through each item in the array as long as elements are not equal to the key.
Figure 2 – Unordered Linear Search
Time Complexity of Unordered Linear Search
The time complexity is very much similar to ordered linear search. If you locate the element at the beginning of the search then the complexity is and worst case it is .
But, think about search on average the ordered array will stop searching as soon as the right element is found and unordered array has to go through all elements because the key could be scattered anywhere.Therefore, ordered linear search perform better on average.
C++ Implementation Of Unordered Linear Search
#include <iostream.h>
#include <stdio.h>
int main()
{
//Declare all variables and the array
int S[] = {34, 66, 2, 44, 10, 22, 100, 88, 54, 93 };
int K;
int n = 10;
int i = 0;
// Read the input value
cout << "Input the value of K: ";
cin >> K;
while (i < n && K != S[i])
{
i = i + 1; //Move through the array
if(K == S[i])
{
cout << "Key Found!" << endl;
cout << "Location = " << i << endl;
}
else
{
cout << "Item not found" << endl;
}
return 0;
}
Program Input:
Input the value of K: 22
Program Output:
Key Found!
Location = 5
In the next article, you will learn about other linear search algorithms.
Given a piece of code, how to determine the complexities without much effort? Each piece of code has a time complexity associated with it which you need to learn. Next time, you see any complex code break it into individual pieces and count the time complexity.
Before you begin, learn the basics of algorithm performance and its complexity.
For the if-then-else block, only one block gets executed, based on the condition. But the run time for the block may be different from other blocks in the if-then-else statement.
if (condition) then
{
block 1;
}
else
{
block2;
}
Therefore,
\begin{aligned}
Total \hspace{1mm}runtime = Max(time(block 1), time(block2));
\end{aligned}
The Big O notation, the theta notation and the omega notation are asymptotic notations to measure the order of growth of algorithms when the magnitude of inputs increases.
In the previous article – performance analysis – you learned that algorithm executes in steps and each step takes a “constant time“. You can count the number of steps and then arrive at total computing time required for the algorithm.
Background
You also learned that complexity affects the performance of the algorithm. These complexities are space complexity and time complexity.
Complexity means how do use of resources usage scale for an algorithm, whereas performance account for actual resources (e.g disk, memory, CPU time) used by algorithms during execution. Complexity affects the performance, performance does not change complexity.
If you leave fixed space like variables, constants etc, and fixed time like compile time, the complexity depends on instance characteristics (operations or steps ) of the algorithm like input size or magnitude.
What is a suitable method to analyze the algorithm?
When we consider instance characteristics which are the number of operations performed by an algorithm to solve a problem of size n. You want to analyze three cases.
Worst Case Performance
Average Case Performance
Best Case Performance
Worst Case Performance: given an instance of a problem with the maximum number of operations what is the time required for the algorithm to solve the problem. This is the worst-case analysis for the algorithm.
Average Case Performance: the instance of a problem has the average number of operations that the algorithm needs to solve. The time to complete such operations is the average case analysis of the algorithm.
Best Case Performance: the problem is already in a solved state or needs fewer steps to solve.
While analyzing an algorithm you should be more concerned about the worst case than average or best case. It is better to compare two algorithms based on the worst-case scenario.
Notations for Complexity
The number of operations for an algorithm when counted will give a function.
For example
an^2+ bn + c
This equation represents an exact step count for an algorithm. You do not need an exact count for the algorithm because when we analyze the algorithm for the worst case, consider only higher-order term and drop the lower order terms because they are insignificant when the input is huge.
This symbol is known as Landau symbol or notation named after German mathematician Edmund Landau. It tells us the fastest growing term in the function called the Order or rate of growth. That is why the lower order terms become insignificant and dropped.
The asymptotic notations such as is used to describe the running time of the algorithms. There are other notations to describe the running time as well.
Suppose is the function of the algorithm for input size n,
then running time is given as
T(n) = O(n^2)
Formal Definition of Big O
Let and be two functions, then is asymptotic upper bound to for a problem size of n.
For a given function , the function is a set of functions
\begin{aligned}
&O(g(n)) = f(n) : there \hspace{1mm}exist \hspace{1mm} positive \hspace{1mm}constants \\ \\
&\hspace{1mm}c \hspace{1mm}and \hspace{1mm} n_0 \hspace{1mm} such \hspace{1mm}that \\\\
&0 \leq f(n) \leq cg(n), for \hspace{1mm} all \{n \geq n_0\}\end{aligned}
The graph of the function is given by the following.
Big O notation graph
Formal Definition of Theta-Notation
Let and be two functions. Then the function gives asymptotic upper bound and asymptotic lower bound, its means that the function is “sandwiched” between and
\begin{aligned}
&\theta (g(n)) = f(n) \hspace{1mm} such \hspace{1mm} that \\\\
&there \hspace{1mm} exist \hspace{1mm} positive\hspace{1mm} constants\hspace{1mm} c_1,c_2 \hspace{1mm} and\hspace{1mm} n_0 \hspace{1mm} such\hspace{1mm} that \\\\
&0 \leq c_1g(n) \leq f(n)\leq c_2g(n) for \hspace{1mm} all \{n \geq n_0\}
\end{aligned}
The graph of Theta notation is given below.
Theta Notation Graph
Formal Definition of Omega-Notation
Let and be two functions. Then the function gives asymptotic lower bound, its means that the function is greater than .
\begin{aligned}
&\Omega(g(n)) = f(n) :there \hspace{1mm}exists \hspace{1mm}positive \hspace{1mm}constants \hspace{1mm}c and \hspace{1mm} n_0 \hspace{1mm}such \hspace{1mm}that \\ \\
&0 \leq c g(n) \leq f(n) \hspace{1mm}for \hspace{1mm} all \{n \geq n_0\}
\end{aligned}
Performance analysis of an algorithm is done to understand how efficient that algorithm is compared to another algorithm that solves the same computational problem. Choosing efficient algorithms means computer programmers can write better and efficient programs.
A computer resource is memory and CPU time and performance analysis revolves around these two resources. Two ways to evaluate an algorithm is listed below.
Space requirement
Computation time
Space Complexity
The space requirement is related to memory resource needed by the algorithm to solve a computational problem to completion. The program source code has many types of variables and their memory requirements are different. So, you can divide the space requirement into two parts.
Fixed Variables
The fixed part of the program are the instructions, simple variables, constants that does not need much memory and they do not change during execution. They are free from the characteristics of an instance of the computational problem.
Dynamic Variables
The variables depends on input size, pointers that refers to other variables dynamically, stack space for recursion are some example. This type of memory requirement changes with instance of the problem and depends on the instance characteristics. It is given by the following equation.
\begin{aligned}&S(P) = c + SP \\
&where \\
&S(P) \hspace{1mm} is \hspace{1mm}space\hspace{1mm} requirement\\
&c \hspace{1mm}is\hspace{1mm} a \hspace{1mm}constant \\
&SP\hspace{1mm} is\hspace{1mm} the \hspace{1mm}instance \hspace{1mm}characteristics
\end{aligned}
Instance characteristics means that it cannot be determined unless the instance of a problem is running which is related to dynamic memory space. The input size usually has the control over instance of a computational problem.
Time Complexity
The time complexity is the amount of time required to run the program to completion.It is given by following.
The computer executes a program in steps and each step has a time cost associated with it. It means that a step could be done in finite amount of time.See the table below.
Program Step
Step Value
Description
Comments
zero
comments are not executed
Assignments
1 step
can be done in constant time
Arithmetic Operations
1 step
con be done in constant time
Loops
Count Steps
if loop runs n times, count step as n+1 and any assignment inside loop is counted as n step.
Flow Control
1 step
only take account of part that was executed.
You can count the number of steps an algorithm performed using this technique.
The result of the step count is which is a linear function. The performance analysis begins by counting the steps but count the steps to execute is not the goal. The goal is to find a function that will describe the algorithm in terms of its input size. This function will tell you how the algorithm will perform for different input size and magnitude.