Data Structures
Data Structure Lecture No 4
Searching and Sorting in Array
Data Structures
In This Lecture Topics Covered
Searching
Linear Search
Binary Search
Sorting
Bubble Sort
Selection Sort
Insertion Sort
Data Structures
Searching
Important area in Computer Science
The Process of finding particular element in an
array is called searching
The Technique we use for searching an element
from the array is called Linear Search
The element which is searched is sometimes
called the Key Element
Data Structures
Linear Search or Sequential Search
This is Very Simple Algorithm
It uses a loop to sequentially step through an
array , starting with the first element.
It Compares each element with the value being
searched for and stops when that value is found
or the end of the array is reached.
Data Structures
Linear Search or Sequential Search
Linear Search or Sequential Search is one of the
Searching Algorithm in which we have some
data in a data structure like array data structure
and we have to search a particular element in it
which is known as key.
By traversing the whole data structure
elements from start to end one by one to find
the key comparing with each other structure
element the key.
Data Structures
Linear Search or Sequential Search
There can be two possible outcomes if we are
assuming that data structure like array contains
unique values.
Linear Search Key Found
Linear Search failed
Data Structures
Linear Search or Sequential Search
0 1 2 3 4 0 1 2 3 4
5 3 17 60 2 5 3 17 60 2
Key Key
0 1 2 3 4 0 1 2 3 4
5 3 17 60 2 5 3 17 60 2
0 1 2 3 4
Key 5 3 17 60 2 Key
Key
Data Structures
Linear Search or Sequential Search
For Example An Array is
int array[8] = {6 4 1 97 3 2 8}
If we have to find the 3 how we find using the
Linear Search?
Compare 3 with each element of the array
if it match with any element of the array then it
returns its index.
Otherwise No is Not found in the array
Data Structures
Linear Search or Sequential Search
Key List
3 6 4 1 9 7 3 2 8
3 6 4 1 9 7 3 2 8
3 6 4 1 9 7 3 2 8
3 6 4 1 9 7 3 2 8
3 6 4 1 9 7 3 2 8
3 6 4 1 9 7 3 2 8
Data Structures
Linear Search or Sequential Search
#include<iostream.h>
Using namespace std;
int main(){
cout<<“Enter the size of Array”;
int size;
cin>>size;
int array[size] , key , i;
for(int j = 0;j<size;j++){
cout<<“Enter”<<j<<“Elements”;
cin>>array[j];
}
Data Structures
Linear Search or Sequential Search
for(int a = 0; a<size;a++){
cout<<“Array[”<<a<<“] is =”;
cout<<array[a];
}
Cout<<“Enter Key to Search in the Array”;
Cin>>key;
for(i = 0; i<size;i++){
if(key = array[i])
cout<<“Key Found at Index No”<<i<<endl;
Break;
}
}
Data Structures
Linear Search or Sequential Search
If(i!=size){
cout<<“Key Found at index”<<i<<endl;
}
else{
cout<<“Key Not Found”<<endl;
}
return 0;
}
Data Structures
Linear Search or Sequential Search
If(i!=size){
cout<<“Key Found at index”<<i<<endl;
}
else{
cout<<“Key Not Found”<<endl;
}
return 0;
}
Data Structures
Analysis & Conclusion
Worst Case: The Worst Case for Linear Search is that
if the element to be searched is not found in the
list. This traverse the entire array and return
nothing. Worst case running time is O(n)
Average Case: The Running Time of Average case is
also O(n)
Best Case: The Best case can be reached if the
element to be found is the first one in the list. So
the time is constant O(1)
Data Structures
Efficiency of the Linear Search
The Advantage is its Simplicity
it is easy to understand
Easy to Implement
Does Not required the array in order
The Disadvantages
if there are 20,000 items in the array and what
you are looking for is in the 19,999th element we
need to search through the entire list.
Data Structures
Binary Search Algorithm
Following C++ Program first ask to the user to
enter how many elements he want to store in the
array then ask to enter the elements.After
storing the elements in the array program ask to
the user to enter the element which he wan to
search in the array wheter that no is present or
not. The Searching Technique is Binary Search.
Data Structures
Binary Search Algorithm
#inlcude<iostream>
using namespace std;
int main(){
int n , i , arr[50] , search , first , last , middle;
cout<<“Enter Total No of Elements”<<endl;
cin>>n;
cout<<“Enter”<<n<<“No”<<endl;
for(i = 0; i<n;i++){
cin>>arr[i];
cout<<“Enter a no to find”<<endl;
cin>>search;
}
Data Structures
Binary Search Algorithm
first = 0;
last = n-1;
middle = (first + last)/2;
while(first <= last){
if(arr[middle]<search){
first = middle + 1;
}
else if(arr[middle] == search){
cout<<search<<“Found at location”<<endl;
}
}
}
Data Structures
Sorting in Array
Arrangement of Data in the array is called
sorting.
We Can Sort data in ascending or Descending.
Lot of Techniques or algorithms are used to sort
the data in array
First Technique which is used is called bubble
sort.
Data Structures
Sorting in Array
Bubble Sort is sorting tecnique in which each pair
of adjacent elements are compared if they are in
wrong order we swap them.
The Process is carry on until the whole array is
sorted.
This algorithms is named as bubble sort because
same as like bubbles the smaller or lighter
elements comes up (at start) and bigger or havier
element goes down (at end).
Data Structures
Bubble Sort
0 1 2 3 4
3 1 15 57 9
Decsending 57 15 9 3 1
Ascending 1 3 9 15 57
Data Structures
Bubble Sort
Array 2 1 3 4 5
Array 2 1 3 4 5
Data Structures
Bubble Sort
Array 2 1 3 4 5
Array 2 1 3 4 5
2 3 1 4 5
Data Structures
Bubble Sort
Array 2 1 3 4 5
Array 2 1 3 4 5
2 3 1 4 5
2 3 4 1 5
Data Structures
Bubble Sort
Array 2 1 3 4 5
Array 2 1 3 4 5
2 3 1 4 5
2 3 4 1 5
2 3 4 5 1
Data Structures
Binary Search Algorithm
#inlcude<iostream>
using namespace std;
Void bubblesort(int number[] , int size);
int main(){
int size , number[size];
cout<<“Enter the size of array”<<endl;
cin>>size;
cout<<“Enter”<<n<<“No”<<endl;
for(i = 0; i<size; i++){
cin>>number[i];
bubblesort(number , size);
}
Data Structures
Binary Search Algorithm
Void bubblesort(number[] , size){
cout<<“Sorted Array”<<endl;
for(int I = 0;i<size-1;i++){
for(int j = 0;j<size-1;j++){
if(number[j] < number[j+1]){
int temp = number[j];
number[j] = number[j+1];
number[j+1] = temp;
}
}
}
}
}
Data Structures
Explaination of Code
Now this program will be explained with proper
example.
Just Consider the array entered by the user.
10 40 13 20 8
Now the program will use the nested loop to
perform sorting. The iterations of outer loop will
specified the number of passes and the inner
loop will specify the number of iterations.
Data Structures
Explaination of Code
At the beginning when the loop begins, the
value of i = 0 , Therefore first pass is started.
Just Consider the array entered by the user.
10 40 13 20 8
In the first pass the value of i = 0 and the inner loop
came into action it will perform 4 iteration and
check the condition of the following block of
statement.
Data Structures
Explaination of Code
Iteration No 1:-
10 40 13 20 8
At first Iteration the value of j =0 and the value of
j = j+1 , Therefore it will compare the values of zero
index and the first index of an array. As we can see
that the value at zero index is smaller than first
index therefore array remains same.
Data Structures
Explaination of Code
Iteration No 1:-
10 40 13 20 8
At first Iteration the value of j =0 and the value of
j = j+1 , Therefore it will compare the values of zero
index and the first index of an array. As we can see
that the value at zero index is smaller than first
index therefore array remains same.
