SEARCHING AND

SORTING ALGORITHMS
5
Chapter 5
ARRAYS
Section 5.1
An array
• is a collection of variables of the same type that are
referenced by a common name.

• Arrays consist of contiguous memory locations.

• Declaraction syntax:
Consists of elements sample[0],
sample[1], sample[2]... sample[9]
• Type var_name[size];
• Example:
• int sample[10];

• In C, all arrays have zero as the index of their first element.

Sample program on SINGLE-DIMENSIONAL ARRAY
#include <iostream>
int main()
{ int A[10],x, s=0;
for(x=0; x<=9;x++){ //x=10
cout<<"Enter number:”;
cin>>A[x]; //A[0]=1 A[1]=2+……10
s=s+A[x]; //s=3
}
cout<<"Total is “<<s<<endl; //Total is 55
return 0;
}
TWO-DIMENSIONAL array
• int sample[x][y];

# of rows # of columns

• int sample[3][3];

0 1 2
0 [0][0] [0][1] [0][2]
1 [1][0] [1][1] [1][2]
2 [2][0] [2][1] [2][2]
Sample program on two-dimensional array
#include <iostream>
int main()
{
int i, j;
int x[3][3]={{10,25,33}, {21,32,43},{20,42,51}};
cout<<"\n3x3 arrays' subscripts and\n“;
cout<<"their respective elements\n“;
Cout<<"--------------------------\n“;
// the outer for loop, reading the row by row...
for(i=0; i<3; i++) //i=1
// the inner loop, for every row, read every column by column...
for(j=0; j<3; j++) //j=0
cout<<"[“<<i<<“]“<<“[“<<j<<“]”<<“=“<<x[i][j]; //[0][0]= 10 [0][1]=25
[0][2]=33
return 0;
}
Multi-dimensional array
• data_type array_name[size1][size2]…[sizeN];

• Example:
• int y[4][5][3];

• Declares a 3-dimensional array with a depth of 4, 5 rows

and 3 columns.
• The are no limitation on the dimension of the arrays, but
the dimension more than two dimensional arrays are
rarely used because of the complexity and code
readability.
Arrays Sorting
// sorting array values into ascending if(a[i] > a[i + 1])
order {
#include <iostream> // put the a[i] in temporary variable
#define SIZE 10 hold...
int main() hold = a[i];
{ // put the a[i + 1] in a[i]
int a[SIZE] = {-4,6,3,-20,0,1,77,-2,42,- a[i] = a[i + 1];
10}; // put the hold in a[i + 1], one
int i, pass, hold; swapping is
cout<<"Data items in original // completed...and repeats for other
order“<<endl; elements...
// displaying the original array... a[i + 1] = hold;
for(i=0; i<=SIZE - 1; i++) }
cout<<a[i]<<“ "; cout<<endl<<“Data items in ascending
// ------do the order“<<endl;
sorting...ascending------------- // display the new ordered list...
// for every array elements do this... for(i=0; i <= (SIZE-1); i++)
for(pass = 1; pass <= (SIZE-1); pass++) cout<<a[i]<<“\t”;
// for every 2 array elements comparison cout<<endl;
do return 0;
// the comparison and swap... }
for(i = 0; i <= (SIZE-2); i++)
// set the condition...
• #include <iostream> • int temp=arr[j];
• int main() • arr[j]=arr[j-1];
• { • arr[j-1]=temp;
• int arr[5]; • }
• •
• cout<<"Enter 5 integer values: • cout<<"Max= “<<arr[4]<<“ “<<endl<<“Min
”<<endl; = “<<arr[0];
• int l; • cout<<endl;
• for(l=0;l<5;l++) { •
• cout<<"value“<<l<<“:”; • return 0;
• cin>>arr[l]; • }

• }
• //find the max value and min value
• int i,j,temp;
• //sort array to find max and
min values
• for(i=0;i<5;i++)
• for(j=4;j>i;j--)
• if(arr[j]<arr[j-1]) {
BUBBLE SORT
Section 5.2
 11

Bubble Sort
How Does the C Program for Bubble Sort Work?
• The program for bubble sort works by comparing and swapping adjacent
elements in an array. Let’s understand this in a step-by-step method:
• Suppose we want to sort an array, let’s name it arr, with n elements in
ascending order; this is how the bubble sort algorithm will work.

1. Starts from the first index: arr[0] and compares the first and second
element: arr[0] and arr[1]
2. If arr[0] is greater than arr[1], they are swapped
3. Similarly, if arr[1] is greater than arr[2], they are swapped
4. The above process continues until the last element arr[n-1]

• All four steps are repeated for each iteration. Upon completing each
iteration, the largest unsorted element is moved to the end of the array.
Finally, the program ends when no elements require swapping, giving us the
array in ascending order.
Sample Program
/#include <iostream> bubble sort: ";
int main(){ for(x = 0; x < num; x++){
int arr[50], num, x, y, temp; cout<< arr[x];
cout<<"Please Enter the Number of }
Elements you want in the array: "; return 0;
cin>>num; }
cout<<"Please Enter the Value of
Elements: ";
for(x = 0; x < num; x++)
cin>>arr[x];
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++)
{
if(arr[y] > arr[y + 1]){

temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
cout<<"Array after implementing
C Program for Bubble Sort Using Functions
#include <iostream> }

void bubbleSortExample(int arr[], int }

num){
}
int x, y, temp;
int main(){
for(x = 0; x < num - 1; x++){
int arr[50], n, x;
for(y = 0; y < num - x - 1; y++)
{ cout<<"Please Enter the Number of
Elements you want in the array: ";
if(arr[y] > arr[y + 1]){
cin>>n;
temp = arr[y];

arr[y] = arr[y + 1];

arr[y + 1] = temp;

}
C Program for Bubble Sort Using Functions
cout<<"Please Enter the Value of
Elements: ";

for(x = 0; x < n; x++)

cin>>arr[x];

bubbleSortExample(arr, n);

cout<<"Array after implementing

bubble sort: ";

for(x = 0; x < n; x++){

cout<< arr[x];

return 0;

}
INSERTION SORT
Section 5.3
 16

Insertion Sort
Insertion sort algorithm is a basic sorting algorithm that sequentially
sorts each item in the final sorted array or list. It is significantly low
on efficiency while working on comparatively larger data sets. While
other algorithms such as quicksort, heapsort, or merge sort have
time and again proven to be far more effective and efficient.
To sort an array in ascending order, you will follow the steps below:

1. Iterate through the array from arr[1] to arr[n].

2. Compare the current element (key) to one that came before it.
3. If the data at the current index is less than the data at the
previous index, you will compare it to the element before it.
4. You will shift bigger elements to the next index to make space for
swapped elements, and then you will iterate the same steps again
to sort the complete array.
How to Implement the Insertion Sort
Algorithm?
You will be provided with a one-
dimensional array of elements {6, 5, 4,
2, 3}. You have to write a code to sort
this array using the insertion sort
algorithm. The final array should come
out to be as {2, 3, 4, 5, 6}.
C Program for Insertion Sort
• k = i - 1;
• //A C++ program to sort an array using
insertion sort • // Move Ar[0..i-1] elements,

• #include <iostream> • //which are larger than the key,

• using namespace std; • //to one place over their present

location
• //A Function to sort an array using
insertion sort • while (k >= 0 && array[k] > key)

• void insertion_sort(int array[], int • {

size)
• array[k + 1] = array[k];
• {

• k = k - 1;
• int i, key, k;

• }
• for (i = 1; i < size; i++)

• array[k + 1] = key;
• {

• }
• key = array[i];
C Program for Insertion Sort
}
} {
// A function to print the array of size
n int arr[] = { 6, 5, 4, 2, 3 };

void print_array(int array[], int size) int size = sizeof(arr) / sizeof(arr[0]);

{ cout<<"Array before sorting:\n";

int i; print_array(arr, size);

for (i = 0; i < size; i++) insertion_sort(arr, size);

cout << array[i] << " "; cout<<"\nArray after sorting:\n";

cout << endl; print_array(arr, size);

} return 0;

/* Driver code */ }

int main()
LINEAR SEARCH
Section 3.2
 21

Linear Search
• In computer science, linear search or sequential
search is a method for finding an element within a list. It
sequentially checks each element of the list until a match
is found or the whole list has been searched.
• Makes at most n comparisons, where n is the length of
the list.
• Linear search is rarely practical because other search
algorithms and schemes, such as the binary search
algorithm allow significantly faster searching for all but
short lists.
Linear Search Approach
• Start from the leftmost element of arr[] and one by one
compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of elements, return -1.
 23

Linear Search Sample Program

#include <iostream> cin>>search;

int main() for (c = 0; c < n; c++)

{ {
int array[100], search, c, n; if (array[c] == search) /*
If required element is found */
cout<<"Enter number of elements {
in array\n"; cout<<search<<“ is present
cin>>n; at location”<< c+1<<endl;
break;
cout<<"Enter “<<n<<” }
integer(s)\n"; }
if (c == n)
for (c = 0; c < n; c++) cout<<search<<“ isn't present
cin>>array[c]; in the array.\n";

cout<<"Enter a number to return 0;

search\n"; }
 24

Linear search for multiple occurrences

#include <iostream> cin>>search;

int main() for (c = 0; c < n; c++) {

{ if (array[c] == search) {
int array[100], search, c, n, cout<<search<<" is
count = 0; present at location”<<c+1<<endl;
count++;
cout<<"Enter number of }
elements in array“<<endl; }
cin>>n; if (count == 0)
cout<<search<<" isn't
cout<<"Enter “<<n<< “ present in the array.“<<endl;
numbers“<<endl; else
cout<<search<<" is present
for (c = 0; c < n; c++) “<<count<<“ times in the array.
cin>>array[c]; “<<endl;

cout<<"Enter a number to return 0;

search:"; }
 25

C++ program for linear search using

function
#include <iostream>
if (position == -1)
long linear_search(long [], long, long); cout<<search<<" isn't present in
the array. “<<endl;
int main() else
{ cout<<search<<" is present at
long array[100], search, c, n, location “<<position+1;
position;
return 0;
cout<<"Input number of elements in }
array“<<endl;
cin>>n; long linear_search(long a[], long n, long
find) {
cout<<"Input “<<n<<“ numbers“<<endl; long c;

for (c = 0; c < n; c++) for (c = 0 ;c < n ; c++ ) {

cin>>array[c]; if (a[c] == find)
return c;
cout<<"Input a number to search: "; }
cin>>search;
return -1;
position = linear_search(array, n, }
BINARY SEARCH
Section 3.3
 27

Binary Search
• Search a sorted array by repeatedly dividing the search
interval in half. Begin with an interval covering the whole
array. If the value of the search key is less than the item in
the middle of the interval, narrow the interval to the lower
half. Otherwise narrow it to the upper half. Repeatedly
check until the value is found or the interval is empty.
 28

Example
1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie
in right half subarray after the mid element. So we recur for
right half.
4. Else (x is smaller) recur for the left half.
 29

Recursive implementation of Binary

Search
// C++ program to implement recursive Binary
Search // Else the element can only be present
#include <iostream> // in right subarray
return binarySearch(arr, mid + 1, r,
// A recursive binary search function. It x);
returns }
// location of x in given array arr[l..r] is // We reach here when element is not
present, // present in array
// otherwise -1 return -1;
int binarySearch(int arr[], int l, int r, int }
x)
{
int main(void)
if (r >= l) {
{
int mid = l + (r - l) / 2;
int arr[] = { 2, 3, 4, 10, 40 };
int n = 5;
// If the element is present at the
int x = 10;
middle
int result = binarySearch(arr, 0, n - 1,
// itself
x);
if (arr[mid] == x)
if(result == -1) cout<<"Element is not
return mid; present in array";
else
// If element is smaller than mid, then
// it can only be present in left cout<<"Element is present at index “<<
subarray result;
if (arr[mid] > x) return 0;
return binarySearch(arr, l, mid - }
 30

Iterative implementation of Binary

Search
// C++ program to implement iterative Binary else
Search r = m - 1;
#include <iostream> }
// if we reach here, then element was
// A iterative binary search function. It // not present
returns return -1;
// location of x in given array arr[l..r] if }
present,
// otherwise -1
int main(void)
int binarySearch(int arr[], int l, int r, int
{
x)
int arr[] = { 2, 3, 4, 10, 40 };
{
int n = 5;
while (l <= r) {
int x = 10;
int m = l + (r - l) / 2;
int result = binarySearch(arr, 0, n - 1,
x);
// Check if x is present at mid
if(result == -1) cout<<"Element is not
if (arr[m] == x) present in array");
return m; else
cout<<"Element is present at index “<< result;
// If x greater, ignore left half return 0;
if (arr[m] < x) }
l = m + 1;

// If x is smaller, ignore right half

 31

Drill
• Find the maximum element in an array using:
(a) Linear Search
(b) Binary Search
Drill 1
• Examples :
• Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}
• Output: 500

• Input: arr[] = {1, 3, 50, 10, 9, 7, 6}

• Output: 50

• Corner case (No decreasing part)

• Input: arr[] = {10, 20, 30, 40, 50}
• Output: 50

• Corner case (No increasing part)

• Input: arr[] = {120, 100, 80, 20, 0}
• Output: 120