SEARCHING

Searching is a process of looking for an item in a data structure to determine if the item is present
or not. The search is said to be successful if the item is found, otherwise, it is unsuccessful. The
items to be searched are normally represented in the data structures using keys.

There are two main types of search algorithms: Sequential search and binary search.
Sequential search algorithm
 The items are arranged in a list
 The items in the list can be ordered or unordered
 The search starts from the first item in the list, then visits each item sequentially until the
item being looked for is found or not found
 If the item is found then search is said to be successful
 If the item is not found then search is said to be unsuccessful
 If the items are unordered then the search must continue until the end the list to determine
if the search is unsuccessful
 If the items are ordered then the algorithm will be able to determine at any given point if
the item being looked for can be found in the remaining range in the list. If the item is
greater than the remaining range then the search continues otherwise, the search is
unsuccessful
 Ordered sequential search is more efficient than unordered sequential search
 Sequential search is the search algorithm that can be used with unordered list of items

Binary Search Algorithm

 In order to use Binary search, the items in the list must be sorted.
 Binary search uses divide and conquer mechanism to conduct the search process
Given an array of items sorted in increasing order and an item being searched, find the position
of the item in the array:
Binary search works as follows
1. Divide the number of items into two and takes the middle index
2. Check if the item in the middle index is the same as the item being searched.
3. If it is, then return the middle index.
4. Otherwise, determine if it is in the upper or lower half.
5. Repeat on this half to find in which quarter it is.
6. Repeat until either the item is found or there are no values left.

Example: Binary Search

search for 64
[0] [1] [2] [3] [4] [5] [6] [7] [8]
11 18 19 22 24 35 37 64 68 Find middle
11 18 19 22 24 35 37 64 68 Find half
11 18 19 22 24 35 37 64 68 Find middle
11 18 19 22 24 35 37 64 68 Find half
11 18 19 22 24 35 37 64 68 Find middle
Found

Example: Binary Search

search for 20
[0] [1] [2] [3] [4] [5] [6] [7] [8]
11 18 19 22 24 35 37 64 68 Find middle
11 18 19 22 24 35 37 64 68 Find half
11 18 19 22 24 35 37 64 68 Find middle
11 18 19 22 24 35 37 64 68 Find half
11 18 19 22 24 35 37 64 68 Find middle
11 18 19 22 24 35 37 64 68 Find half
11 18 19 22 24 35 37 64 68 Find middle
Not found

Pseudo-code for Binary Search

Algorithm BinarySearch(key, k, low, high)
if low > high then
return NO_SUCH_KEY
else
mid (low+high) / 2
if k = key(mid) then
return key(mid)
else if k < key(mid) then
return BinarySearch(key, k, low, mid-1)
else
return BinarySearch(key, k, mid+1, high)

Binary Search Implementation

public class BinarySearch
{
public static final int NOT_FOUND = -1;

public static int search(int[] arr, int searchValue)

{
int left = 0;
int right = [Link] - 1;
return binarySearch(arr, searchValue, left, right);
 }

private static int binarySearch(int[] arr, int searchValue, int left, int right)
{
if (right < left)
{
return NOT_FOUND;
}

int mid = (left + right)/2;

if (searchValue > arr[mid])
{
return binarySearch(arr, searchValue, mid + 1, right);
}
else if (searchValue < arr[mid])
{
return binarySearch(arr, searchValue, left, mid - 1);
}
else
{
return mid;
}
}
}

Sorting
 Sorting is the process of arranging data items in a data structure in either ascending or
descending pattern in order facilitate faster referencing and manipulation of data
 The aim of sorting algorithms is to put unordered information in an ordered form.
The following are some of the sorting algorithms:
 Selection Sort
 Bubble Sort
 Insertion Sort
 Merge Sort
 Quick Sort
 Heap sort

Selection Sort
  The list is divided into two sublists, sorted and unsorted, which are divided by an
imaginary wall.
 We find the smallest element from the unsorted sublist and swap it with the element at
the beginning of the unsorted data.
 After each selection and swapping, the imaginary wall between the two sublists move one
element ahead, increasing the number of sorted elements and decreasing the number of
unsorted ones.
 Each time we move one element from the unsorted sublist to the sorted sublist, we say
that we have completed a sort pass.
 A list of n elements requires n-1 passes to completely rearrange the data.

23 78 45 8 32 56 Original List

8 78 45 23 32 After pass 1
56

8 23 45 78 32 56 After pass 2

8 23 32 78 45 56 After pass 3

8 23 32 45 78 56 After pass 4

8 23 32 45 56 78 After pass 5

/* Sorts by selecting smallest element in unsorted portion of array and exchanging it with
element at the beginning of the unsorted list. Pre list must contain at least one item, last contains
index to last element in list, Post list is rearranged from smallest to largest
*/
void selectionSort(int list[], int last)
{
int current, walker, smallest, tempData;
for (current = 0; current <= last; current ++)
{
smallest = current;
for (walker=current+1; walker <= last; walker++)
if(list[walker] < list[smallest])
smallest = walker;
// Smallest selected; swap with current element
tempData = list[current];
list[current] = list[smallest];
list[smallest] = tempData;
 }
}

Complexity Analysis of Selection Sort

Time Complexity: O(n2) ,as there are two nested loops:

 One loop to select an element of Array one by one = O(n)

 Another loop to compare that element with every other Array element = O(n)

 Therefore overall complexity = O(n) * O(n) = O(n*n) = O(n2)

Advantages of Selection Sort

 Easy to understand and implement, making it ideal for teaching basic sorting concepts.

 Requires only a constant O(1) extra memory space.

 It requires less number of swaps (or memory writes) compared to many other standard
algorithms. Only cycle sort beats it in terms of memory writes. Therefore it can be simple
algorithm choice when memory writes are costly.

Disadvantages of the Selection Sort

 Selection sort has a time complexity of O(n^2) makes it slower compared to algorithms
like Quick Sort or Merge Sort.

 Does not maintain the relative order of equal elements.

 Does not preserve the relative order of items with equal keys which means it is not stable.

Bubble Sort Algorithm

 The list is divided into two sublists: sorted and unsorted.
 The smallest element is bubbled from the unsorted list and moved to the sorted sublist.
 After that, the wall moves one element ahead, increasing the number of sorted elements
and decreasing the number of unsorted ones.
 Each time an element moves from the unsorted part to the sorted part one sort pass is
completed.
  Given a list of n elements, bubble sort requires up to n-1 passes to sort the data.
 Bubble sort was originally written to “bubble up” the highest element in the list. From an
efficiency point of view it makes no difference whether the high element is bubbled or
the low element is bubbled.

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent
elements, if necessary. When no exchanges are required, the file is sorted.

We assume list is an array of n elements. We further assume that swap function swaps the values
of the given array elements.

Step 1 − Check if the first element in the input array is greater than the next element in the array.

Step 2 − If it is greater, swap the two elements; otherwise move the pointer forward in the array.

Step 3 − Repeat Step 2 until we reach the end of the array.

Step 4 − Check if the elements are sorted; if not, repeat the same process (Step 1 to Step 3) from
the last element of the array to the first.

Step 5 − The final output achieved is the sorted array.

Example

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it
short and precise.

Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33
with 27.
We find that 27 is smaller than 33 and these two values must be swapped.

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted. We swap these values. We find
that we have reached the end of the array. After one iteration, the array should look like this −

To be precise, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sort learns that an array is completely sorted.
Now we should look into some practical aspects of bubble sort.

23 78 45 8 32 56 Original List

8 23 32
78 78
45 45
32 56 After pass
After pass 2
56 1
8 23 32 45 78 56 After pass 3
8 23 32 45 56 78 After pass 4
Bubble Sort Algorithm
/* Sorts list using bubble sort. Adjacent elements are compared and exchanged until list is
completely ordered. Pre list must contain at least one item, last contains index to last element in
list, Post list is rearranged from smallest to largest
*/
void bubbleSort(int list[], int last)
{
int current, walker, temp;
for (current = 0; current <= last; current++)
{
for (walker=last; walker > current; walker--)
if(list[walker] < list[walker - 1])
{
temp = list[walker];
list[walker] = list[walker – 1];
list[walker-1] = temp;
}
}
 return;
}

void bubbleSort (int a[ ] , int size)

{
int i, j, temp;
for ( i = 0; i < size; i++ ) /* controls passes through the list */
{
for ( j = 0; j < size - 1; j++ ) /* performs adjacent comparisons */
{
if ( a[ j ] > a[ j+1 ] ) /* determines if a swap should occur */
{
temp = a[ j ]; /* swap is performed */
a[ j ] = a[ j + 1 ];
a[ j+1 ] = temp;
}
}
}
}

Time Complexity: O(n2)

Auxiliary Space: O(1)

Advantages of Bubble Sort:

 Bubble sort is easy to understand and implement.

 It does not require any additional memory space.

 It is a stable sorting algorithm, meaning that elements with the same key value maintain
their relative order in the sorted output.

Disadvantages of Bubble Sort:

 Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.

 Bubble sort is a comparison-based sorting algorithm, which means that it requires a

comparison operator to determine the relative order of elements in the input data set. It
can limit the efficiency of the algorithm in certain cases.

Insertion Sort
  Most common sorting technique used by card players.
 Again, the list is divided into two parts: sorted and unsorted.
 In each pass, the first element of the unsorted part is picked up, transferred to the sorted
sublist, and inserted at the appropriate place.
 A list of n elements will take at most n-1 passes to sort the data.

23 78 45 8 32 Original
56
23 78 45 8 32 List
After pass
56
23 45 78 8 32 1After pass
56
8 23 45 78 32 2After pass
856 23 32 45 78 3
After pass
856 23 32 45 56 4
After pass
78 5
Insertion Sort Algorithm
/* With each pass, first element in unsorted sublist is inserted into sorted sublist.
Pre list must contain at least one item, last contains index to last element in list, Post list has been
rearranged
*/

void insertionSort(int list[], int last)

{
int current, located, temp, walker;
for (current = 1; current <= last; current++)
{
located = 0;
temp = list[current];
for (walker=current-1; walker >= 0 && !located;)
{
if(temp < list[walker])
{
list[walker + 1]= list[walker];
walker--;
}
Else
{
located = 1;
list[walker + 1] = temp;
}
}
}
return;
}
Time Complexity of Insertion Sort

 Best case: O(n) , If the list is already sorted, where n is the number of elements in the
list.

 Average case: O(n 2 ) , If the list is randomly ordered

 Worst case: O(n 2 ) , If the list is in reverse order

Advantages of Insertion Sort:

 Simple and easy to implement.

 Stable sorting algorithm.

 Efficient for small lists and nearly sorted lists.

 Space-efficient as it is an in-place algorithm.

 Adoptive. the number of inversions is directly proportional to number of swaps. For

example, no swapping happens for a sorted array and it takes O(n) time only.

Disadvantages of Insertion Sort:

 Inefficient for large lists.

 Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most cases.

MERGE SORT
Merge sort is a sorting technique based on divide and conquer technique. With worst-case time
complexity being Ο(n log n), it is one of the most respected algorithms.

Merge sort first divides the array into equal halves and then combines them in a sorted manner.

How merge sort works

To understand merge sort, we take an unsorted array as depicted below −

We know that merge sort first divides the whole array iteratively into equal halves unless the
atomic values are achieved. We see here that an array of 8 items is divided into two arrays of size
4.

This does not change the sequence of appearance of items in the original. Now we divide these
two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more be divided.

Now, we combine them in exactly same manner they were broken down. Please note the color
codes given to these lists.

We first compare the element for each list and then combine them into another list in sorted
manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the target
list of 2 values we put 10 first, followed by 27. We change the order 19 and 35. 42 and 44 are
placed sequentially.

In next iteration of combining phase, we compare lists of two data values, and merge them into a
list of foud data values placing all in sorted order.

After final merging, the list should look like this −

Now we should learn some programming aspects of merge sorting.

Algorithm

Merge sort keeps on dividing the list into equal halves until it can no more be divided. By
definition, if it is only one element in the list, it is sorted. Then merge sort combines smaller
sorted lists keeping the new list sorted too.

Step 1 − if it is only one element in the list it is already sorted, return.

Step 2 − divide the list recursively into two halves until it can no more be
divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocode

We shall now see the pseudocodes for merge-sort functions. As our algorithms points out two
main functions − divide & merge.

Merge sort works with recursion and we shall see our implementation in the same way

Merge Sort
Sort by merging two already-sorted sequences, itemsA and itemsB of length lenA
and lenB, respectively, into a new sequence, itemsC

Set the indices posA, posB, posC to 0

while (posA < lenA) and (posB < lenB) do
if (itemsA[posA] < itemsB[posB])
{
itemsC[posC] = itemsA[posA];
posA = posA + 1;
}
else
{
itemsC[posC] = itemsB[posB];
posB = posB + 1;
}
posC = posC + 1;
if (posA < lenA-1)
{
append all the remaining elements of itemsA to itemsC;
}
else if (posB < lenB-1)
{
append all the remaining elements of itemsB to itemsC;
}
Merge Example

Merge Sort
 If an input sequence has size > 1, divide it into left and right halves
 Use Merge Sort to sort the halves
 Merge the two sorted halves.
 To sort each half, create its copy and make a recursive call to Merge Sort.
 To merge, use the two half-size sequences returned by the recursive calls
Complexity Analysis of Merge Sort:

 Time Complexity:

o Best Case: O(n log n), When the array is already sorted or nearly sorted.

o Average Case: O(n log n), When the array is randomly ordered.

o Worst Case: O(n log n), When the array is sorted in reverse order.

 Auxiliary Space: O(n), Additional space is required for the temporary array used during
merging.

Heapsort
 Use a property of the heap that the largest element is at the root.
 Given n elements, turn them into a heap of size n (implementable using an array of size
n).
 For p = n, …, 2 do the following:
 Exchange the element at position 0 (the root) and the element at position p.
 Enforce the heap property starting from position 0.
 (In the next round p is decremented, so the above achieves the removal of the root.)

Initialization of heap and extraction of an element Extraction of the next two elements
Quick sort
 We’ll assume that the elements are in an array.
 Select an element, called pivot, from the array and reorder the array so that:
 Those smaller than the pivot come first (in any order)
 Those larger than the pivot comes last
 Recursively sort the two subparts using Quicksort and then join them.

Idealized Split in Quicksort

Quick Sort Code
void quickSort(int[] a, int x, int y)
{
int pivotIndex;
if ((y – x) > 0)
{
pivotIndex = partionList(a, x, y);
quickSort(a, x, pivotIndex – 1);
quickSort(a, pivotIndex+1, y);
}
}

int partionList(int[] a, int x, int y)

{
… // partitions list and returns index of pivot
}

static int partitionList(int[] a, int x, int y)

{
int left = x+1;
int right = y;
int pivot = a[x];
while (true)
{
while (a[left] <= pivot && left < right)
left++;
while (a[right] > pivot)
right--;
if (left >= right) break;
swap(a, left, right);
}
swap(a, x, right);
return right;
}

Testing the Sort Algorithms

Need to use a variety of test cases
 Small and large arrays
 Arrays in random order
 Arrays that are already sorted
 Arrays with duplicate values
 Compare performance on each type of array