Data structure
UNIT – 3
ABHAY KUMAR SINGH 3/11/23 SEARCHING & SORTING
Searching Algorithm of Binary Search
Searching Algorithms are designed to check for an element BS(arr, l,r,ele)
or retrieve an element from any data structure where it is 1. if l>r then return -1 stop
stored. 2. mid=l+(r-l)/2
There are two searching techniques : 3. if arr[mid]==ele then return mid stop
a. Linear search (sequen al) b. Binary search 4. if arr[mid ] < ele then return BS(arr,mid+1,r,ele) //for left array
5. if arr[mid ] > ele then return BS(arr,l,mid-1,ele) //for right array
Linear Search
Explana on:
It is the simplest searching algorithm If ele== mid, then return mid.Else, compare the element to
Each element read one by one sequen ally and compared be searched with m.
with the desired elements is known as linear search . If ele > mid, compare x with the middle element of the
It is widely used to search an element from the unordered list elements on the right side of mid. This is done by
Worst-case me complexity of linear search is O(n) setting l to l = mid + 1.
The space complexity of linear search is O(1). Else, compare ele with the middle element of the elements
on the left side of mid. This is done by setting r to r = mid-1
Hashing
It is a process of mapping keys, and values into the hash table
by using a hash func on.
It is done for faster access to elements.
we transform large key to small key using hash func on
In Hashing, Using the hash func on, we can calculate the
Algorithm of Linear Search address at which the value can be stored.
Linear_search(Array, ele, n)
Each element is assigned a key. By using that key we can
1. for i = 0 to n-1 then check access the element in O(1) me.
2. if (Array[i] = ele ) then return i In a hash table , we have number of fixed slots to store the
3. enfor value .
4. return -1 Hash Key = Key Value % Number of Slots in the Table
Explana on: Examples of Hashing in Data Structure:
First, we have to traverse the array elements using a for loop. In schools, roll number to retrieve information about
In each itera on, compare the search element with the that student.
current array element, and - A library has an infinite number of books. The librarian
If the element matches, then return the index of the assigns a unique number to each book. This unique
corresponding array element. number helps in identifying the position of the books on
If the element does not match, then move to the next the bookshelf.
element.
If there is no match or the search element is not present in Hash function and their types
the given array, return -1.
The hash function is used to arbitrary size of data to fixed-
Binary Search sized data.
It is search technique that works efficiently on sorted lists. hash = hashfunction(key)
we must ensure that the list is sorted.
Binary search follows the divide and conquer approach a. Division method :
Array divided into two parts and compared with middle
The hash func on H is defined by :
index of the element of the array
If the middle elements matched with the desired element H(k) = k (mod m) or H(k) = k (mod m) + 1
then we return the index of the element Here k (mod m) denotes the remainder when k is divided
Time complexity of the algo is O(logn) by m.
Example: k=53 , m=10 then h(53)=53mod10 =3
b. Midsquare method :
The hash func on H is : H(k) = h(k*k)=l
l is obtained by dele ng digits from both end of k2.
Example : k=60
therefore k=3600
then remove digits from both end we get h(k) =60
c. Folding method : Op onally, maintain the linked list in sorted order, with each
element containing the whole record including the key.
The key k is par oned into a number of parts, k1, ... ,kr,
To insert, find the hash value with a hash func on, and insert
Then the parts are added together H(k) = k1 + k2 + ....+ kr
the element into the linked list.
Now truncate the address upto the digit based on the
size of hash table. For searching, find the hash key in the hash table, then
search the element in the corresponding linked list.
Example : k = 12345
k1 = 12, k2 = 34, k3 = 5 Dele on involves a search opera on and then dele ng the
s = k1 + k2 + k3= 12 + 34 + 5= 51 element from the linked list.
Hash Collision Garbge collection
hash collision or hash clash is when two pieces of data in a Garbage collec on in hashing reclaims memory/resources
hash table share the same hash value from deleted elements that are no longer in use
It enhances hash table efficiency. Typically automa c, it's
Collision resolution technique managed by the data structure or language run me.
Mechanisms vary by language/implementa on.
We have two method to resolve this collision in our hashing .
these are following below : Insertion sort
1. Open addressing 2.seperate chaining
This is an in-place comparison-based sor ng algorithm.
1.Open addressing Here, a sub-list is maintained which is always sorted.
The array is searched sequen ally and unsorted items are
Open addressing stores all elements in the hash table itself. moved and inserted into the sorted sub-list (in the same
It systema cally checks table slots when searching for an array).
element. average and worst case complexity are of Ο(n2)
In open addressing, the load factor (λ) cannot exceed 1.
Load Factor (λ) = Number of Elements Stored / Total Number
of Slots
Probing is the process of examining hash table loca ons.
Linear Probing
it systema cally checks the next slot in a linear manner
un l an empty slot is found.
This process con nues un l the desired element is
located
method of linear probing uses the hash func on
h(k,i)= (k %m + i) mod m , where m is size of table
Quadra c Probing
it checks slots in a quadra c sequence (e.g., slot + 1, slot
+ 4, slot + 9, and so on) un l an empty slot is found.
This con nues un l the desired element is located or the
table is en rely probed.
method of Quadra c probing uses the hash func on Algorithm of Insertion sort
h(k,i)= (k %m + i^2) mod m
Double Probing 1. for j =2 to length[A]
it uses a second hash func on to calculate step size for 2. set key = A[j] and i=j-1
probing, providing a different sequence of slots to check. 3. while i > 0 and A[i] > key then
This con nues un l an empty slot is found or the desired 4. A[i + 1] = A[i]
element is located. 5. i=i–1
method of Quadra c probing uses the hash func on 6. endwhile
H1(k) = k%N and H2(k) = P - (k%P) 7. A[i + 1] = key
H(k, i) = (H1(k) + i*H2(k))%N 8. endfor
Where p is the prime Number less than k Bubble sort
Bubble sort is the simplest sor ng algorithm that works by
2. Seperate chaining
repeatedly
Maintain chains of elements with the same hash address. swapping the adjacent element if they are in wrong order.
Use an array of pointers as the hash table. It is very efficient in large sor ng jobs. For n data items, this
Size of the hash table can be the number of records. method requires n(n – 1)/2 comparisons.
Each pointer points to a linked list where elements with the Worst-case me complexity of algo is O(n^2).
same hash address are stored.
Similarly repeat step un l we get sorted array
It is based on the Divide and Conquer algorithm
Picks an element as a pivot and par ons the given array
Placing the pivot in its correct posi on in the sorted array.
Algorithm of Bubble sort
Then these two sub-arrays are sorted separately.
bubblesort(Arr, n ):
Algorithm of quick sort
1. for i=1 to n-1:
2. for j=1 to n-i : 1. partition(arr,l,r):
3. if arr[j]>arr[j+1] then swap(arr[j],arr[j+1]) 2. pivot=arr[r]
4. endfor 3. for j=l upto r :
5. endfor 4. check arr[j] < pivot then
Selection sort 5. do swap(arr[l],arr[j]) and l++
6. endfor
In this sor ng , we find the smallest element in the given and
7. swap(arr[l],arr[r])
moves it final posi on of the array .
8. return l
We then reduce the effec ve size of the array by one
element and repeat the process on the smaller sub-array.
The process stops when the effec ve size of the array 1. QUICKSORT (array A, l, r):
2. if (l < r) :
becomes 1
3. p = partition(A, l, r)
Worst Time complexity of algorithm is O(n^2). 4. QUICKSORT (A, l, p - 1)
5. QUICKSORT (A, p + 1, r)
6. endif
complexity of quick sort :
Best TC: O(nlogn) SC: O(1)
Average TC : O(nlogn)
Worst TC: O(n^2)
Merge sort
Algorithm of Selection sort Merge sort is a sor ng algorithm that uses the idea of divide
and conquer.
1. Selection-Sort (A,n) : This algorithm divides the array into two subarray , sorts
2. for j = 1 to n – 1: them separately and then merges them.
3. sm = j
4. for i = j + 1 to n:
5. if A [i] < A[sm] then sm = i
6. Swap (A[j], A[sm])
Quick sort
complexity of merge sort :
Best TC: O(nlogn) SC: O(n)
Average TC : O(nlogn)
Worst TC: O(nlogn)
Algorithm of merge sort It finds largest element and puts it at the end of array, then
second largest item is found and this process is repeated for
1. mergesort(arr, l, r) all other elements. Heapsort is non-stable sor ng
2. if l < r
3. set mid = l+(r-l)/2
The general approach of heap sort is as follows :
4. mergesort(arr, l, mid) From the given array, build the ini al max heap.
5. mergesort(arr, mid + 1, r) Interchange the root (maximum) element with the last
6. MERGE (arr, l, mid, r) element.
7. endif
Use repe ve downward opera on from root node to
8. END mergesort
rebuild the
heap of size one less than the star ng.
1. void merge(int a[], int l, int m, int r): Repeat step (a) and (b) un l there are no more elements.
2. set n1 = m - l + 1, n2 = r - m
3. initialize Left[n1], Right[n2]; Algorithm of Heapsort sort
4. // copy the left data in left array BuildHeap(arr)
5. for i=0 upto n1 : 1. for i = length(arr)/2-1 to 0
6. Left[i] = a[l + i] 2. Heapify(arr,i)
7. // copy the right data in right array
8. for j=0 upto n2 : Heapify(A,i,n):
9. Right[j] = a[m + 1 + j] 1. Initializes l=2*i+1 , r=2*i+2, largest =i
2. if l < n and A[l] > A[i] then largest=l
10. set i = 0, j = 0 ,k = l
3. if r <n and A[r] > A [largest] then largest = r
11. while (i < n1 && j < n2) :
4. if largest != i :
12. if(Left[i] <= Right[j]) :
5. swap(A[i],A[largest])
13. a[k] = Left[i++]
6. Heapify(A,largest)
14. else :
15. a[k] = Right[j++]
16. k++; HeapSort(A) :
1. BuildHeap(A)
17. while (i<n1) : 2. for j = length [A] down to 1
18. a[k++] = Left[i++]; 3. swap(A[1] , A[j])
19. while (j<n2) : 4. Heapify (A, 0,j)
20. a[k++] = Right[j++]; complexity of Heap sort :
Heap sort Best TC: O(nlogn) SC: O(1)
Average TC : O(nlogn) Worst TC: O(nlogn)
Radix sort
Radix sort is the linear sor ng algorithm that is used for
integers. It is stable sor ng .
In which,according to digit sor ng is performed that is
started from the right to le digit.
Example : we have 7 elements in array to sort the array using
radix technique.
Arr=[329,457, 657, 839, 436, 720, 355]
Algorithm of Radix sort
radixSort(arr)
1. max = largest element in arr
2. d = number of digits in max
3. Now, create d buckets of size 0 - 9
4. for i -> 0 to d
5. sort the arr elements using counting sort
complexity of Radix sort :
Best TC: O(n+k) SC: O(n)
Average TC : O(nk) Worst TC: O(nk
