3.1 Searching: Concept of Searching

Searching

Searching is the process of finding some particular element in the list. If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

There are two popular search methods that are widely used in order to search some items into the list. However, the choice of the algorithm depends upon the arrangement of the list.

●      Linear Search

●      Binary Search

Linear search

Linear search, often known as sequential search, is the most basic search technique. In this type of search, we simply go through the entire list and match each element to the item whose position has to be discovered. If a match is found, the algorithm returns the item's location; otherwise, NULL is returned.

Binary search

Binary search is a search technique that performs well on sorted lists. As a result, in order to use the binary search strategy to find an element in a list, we must first confirm that the list is sorted.

The divide and conquer strategy is used in binary search, in which the list is divided into two halves and the item is compared to the list's middle element.

3.2 Sequential search

A linear or sequential relationship exists when data objects are stored in a collection, such as a list. Each data item is kept in a certain location in relation to the others. These relative positions are the index values of the various items in Python lists. We can access these index values in order because their values are ordered. Our initial searching strategy, the sequential search, is born out of this procedure.

This is how the search works, as shown in the diagram. We just advance from item to item in the list, following the underlying sequential ordering, until we either find what we're looking for or run out of options. If we run out of items, we have discovered that the item we were searching for was not present.

Fig 1: Sequential search

Algorithm

Time complexity

Best case - O(1)

Average case - O(n)

Worst case - O(n)

Space complexity

Worst case - O(1)

3.3 Index Sequential Search

Indexed sequential search is another strategy for improving search efficiency for a sorted file. However, it necessitates a larger quantity of memory space. In addition to the sorted file, an index table is kept aside. Each index table element has a key Kindex and a link to the record in the field that matches the kindex. The index elements, as well as the file elements, must be sorted on the file.

When using this method, an index file is first constructed, which contains a specific group or division of the desired record. Once the index is obtained, partial indexing takes less time because it is situated in a specific group.

The advantage of the indexed sequential method is that even though all entries in the file must be read, items in the table can be inspected sequentially, and the search time for specific items is decreased. Rather than searching the large table, a sequential search is done on the smaller index. After finding the index point, the search is moved to the record table itself.

The easiest way to delete entries from an indexed sequential table is to mark them as deleted. Deleted items are disregarded when searching sequentially. From the original table, the item is removed.

Insertion into an indexed sequential table can be challenging since there may be no space between two table entries, resulting in a significant number of components being shifted.

Characteristics of indexed sequential search

Fig 2: Indexed sequential search

Key takeaway

3.4 Binary Search

Binary Search

Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an element into some list by using binary search technique, we must ensure that the list is sorted.

Binary search follows a divide and conquer approach in which the list is divided into two halves and the item is compared with the middle element of the list. If the match is found then, the location of the middle element is returned; otherwise, we search into either of the halves depending upon the result produced through the match.

Binary search algorithm is given below.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

●      Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = - 1

●      Step 2: Repeat Steps 3 and 4 while BEG <=END

●      Step 3: SET MID = (BEG + END)/2

●      Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]

●      Step 5: IF POS = -1
PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
[END OF IF]

●      Step 6: EXIT

Complexity

Example

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.

In 1st step :

In Second step:

In third step:

Fig 3 - Example

3.5 Concept of Hashing & Collision resolution Techniques used in Hashing

●      Hashing is the process of mapping a large amount of data item to a smaller table with the help of hashing function.

●      Hashing is also known as the Hashing Algorithm or Message Digest Function.

●      It is a technique to convert a range of key values into a range of indexes of an array.

●      It is used to facilitate the next level searching method when compared with the linear or binary search.

●      Hashing allows the user to update and retrieve any data entry in a constant time O(1).

●      Constant time O(1) means the operation does not depend on the size of the data.

●      Hashing is used with a database to enable items to be retrieved more quickly.

●      It is used in the encryption and decryption of digital signatures.

Hash Function

●      A fixed process converts a key to a hash key is known as a Hash Function.

●      This function takes a key and maps it to a value of a certain length which is called a Hash value or Hash.

●      Hash value represents the original string of characters, but it is normally smaller than the original.

●      It transfers the digital signature and then both hash value and signature are sent to the receiver. Receiver uses the same hash function to generate the hash value and then compares it to that received with the message.

●      If the hash values are the same, the message is transmitted without errors.

Hash Table

●      Hash table or hash map is a data structure used to store key-value pairs.

●      It is a collection of items stored to make it easy to find them later.

●      It uses a hash function to compute an index into an array of buckets or slots from which the desired value can be found.

●      It is an array of list where each list is known as bucket.

●      It contains value based on the key.

●      Hash tables are used to implement the map interface and extend the Dictionary class.

●      Hash tables are synchronized and contain only unique elements.

●      The above figure shows the hash table with the size of n = 10. Each position of the hash table is called a Slot. In the above hash table, there are n slots in the table, names = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Slot 0, slot 1, slot 2 and so on. Hash tables contain no items, so every slot is empty.

●      As we know, the mapping between an item and the slot where the item belongs in the hash table is called the hash function. The hash function takes any item in the collection and returns an integer in the range of slot names between 0 to n-1.

●      Suppose we have integer items {26, 70, 18, 31, 54, 93}. One common method of determining a hash key is the division method of hashing and the formula is:

Hash Key = Key Value % Number of Slots in the Table

●      Division method or reminder method takes an item and divides it by the table size and returns the remainder as its hash value.

●      After computing the hash values, we can insert each item into the hash table at the designated position as shown in the above figure. In the hash table, 6 of the 10 slots are occupied; it is referred to as the load factor and denoted by, λ = No. Of items / table size. For example , λ = 6/10.

●      It is easy to search for an item using the hash function where it computes the slot name for the item and then checks the hash table to see if it is present.

●      Constant amount of time O(1) is required to compute the hash value and index of the hash table at that location.

Collision Resolution Techniques

Collision in hashing

Collision resolution techniques

There are two types of collision resolution techniques.

Separate chaining

In this technique, a linked list is created from the slot in which collision has occurred, after which the new key is inserted into the linked list. This linked list of slots looks like a chain, so it is called separate chaining. It is used more when we do not know how many keys to insert or delete.

Time complexity

Advantages of separate chaining

Disadvantages of separate chaining

Open addressing

Open addressing is a collision-resolution method that is used to control the collision in the hashing table. There is no key stored outside of the hash table. Therefore, the size of the hash table is always greater than or equal to the number of keys. It is also called closed hashing.

The following techniques are used in open addressing:

Linear probing

In this, when the collision occurs, we perform a linear probe for the next slot, and this probing is performed until an empty slot is found. In linear probing, the worst time to search for an element is O(table size). The linear probing gives the best performance of the cache but its problem is clustering. The main advantage of this technique is that it can be easily calculated.

Disadvantages of linear probing

Quadratic probing

In this, when the collision occurs, we probe for i2th slot in ith iteration, and this probing is performed until an empty slot is found. The cache performance in quadratic probing is lower than the linear probing. Quadratic probing also reduces the problem of clustering.

Double hashing

In this, you use another hash function, and probe for (i * hash 2(x)) in the ith iteration. It takes longer to determine two hash functions. The double probing gives the very poor cache performance, but there is no clustering problem in it.

Hashing with Chaining in Data Structure

In this section we will see what is hashing with chaining. Chaining is one collision resolution technique. We cannot avoid collision, but we can try to reduce the collision, and try to store multiple elements for the same hash value.

This technique assumes that our hash function h(x) ranges from 0 to 6. So for more than 7 elements, there must be some elements that will be placed inside the same room. For that we will create a list to store them accordingly. In each time we will add at the beginning of the list to perform insertion in O(1) time

Let us see the following example to get a better idea. If we have some elements like {15, 47, 23, 34, 85, 97, 65, 89, 70}. And our hash function is h(x) = x mod 7.

The hash values will be

The Hashing with chaining will be like −

Key takeaway

3.6 Sorting: Insertion Sort

Insertion style is a decrease & conquer technique application. It is a sort based on comparison in which the sorted array is constructed on one entry at a time.

Insertion sorting is a very basic process for sorting numbers in an ascending or descending order. The gradual method is accompanied by this method. It can be contrasted with the method of sorting cards at the time of playing a game.

The numbers that are needed to be sorted are known as keys. Here is the insertion sort method algorithm.

Algorithm:

Algorithm: Insertion-Sort (A)

For j = 2 to A.length  

Key = A[j] 

// Insert A[j] into the sorted sequence A[1.. j - 1] 

i = j - 1 

While i > 0 and A[i] > key 

A[i + 1] = A[i] 

i = i -1 

A[i + 1] = key 

Analysis:

This algorithm's run time is very dependent on the input given.

If the numbers given are sorted, this algorithm runs in O(n) time. If the numbers given are in reverse order, the algorithm runs in O(n2) time.

Example:

Using insertion sort to sort the following list of elements:

89, 45, 68, 90, 29, 34, 17

89  |45  68  90  29  34  17

45  89  |68  90  29  34  17

45  68  89  |90  29  34  17

45  68  89  90  |29  34  17

29  45  68  89  90  |34  17

29  34  45  68  89  90  |17

17  29  34  45  68  89  90

Application:

In the following instances, the insertion sort algorithm is used:

●   When only a few elements are in the list.

●   When there are few elements for sorting.

Advantages:

●      Left to right scan

●      Right to left scan

●      Binary insertion sort

2.  Effective on a small list of components, on a nearly sorted list.

3.  In the best example, running time is linear.

4.  This algorithm is stable.

5.  Is the on-the-spot algorithm

Key takeaways

3.7 Selection Sort

In the selection sort, the smallest value among the array's unsorted items is chosen in each pass and inserted into the proper spot.

To begin, locate the array's smallest element and set it in the first position. Then locate the array's second smallest element and set it in the second spot. The procedure is repeated till the sorted array is obtained.

The n-1 pass of the selection sort algorithm is used to sort the array of n entries.

●      The smallest element of the array, as well as its index pos, must be identified in the first run. Swap A[0] and A[pos] after that. As a result of sorting A[0], we now have n -1 elements to sort.

●      The location pos of the smallest element in the sub-array A[n-1] is obtained in the second pas. Swap A[1] and A[pos] after that. After sorting A[0] and A[1], we're left with n-2 unsorted elements.

●      The position pos of the smaller element between A[n-1] and A[n-2] must be found in the n-1st pass. Swap A[pos] and A[n-1] after that.

As a result, the items A[0], A[1], A[2],...., A[n-1] are sorted using the procedure described above.

Example

Consider the following six-element array. Using selection sort, sort the array's elements.

A = {10, 2, 3, 90, 43, 56}.

Sorted A = {2, 3, 10, 43, 56, 90}

Algorithm

SELECTION SORT(ARR, N)

SMALLEST (ARR, K, N, POS)

Key takeaway

3.8 Bubble Sort

Compare and swap adjacent elements of the list if they are out of order. After repeating the procedure, we end up 'bubbling up' the largest element to the last place on the list by doing it repeatedly.

Algorithm

BubbleSort(A[0..n - 1])

//The algorithm sorts array A[0..n - 1] by bubble sort

//Input: An array A[0..n - 1] of orderable elements

//Output: Array A[0..n - 1] sorted in ascending order

For i=0 to n - 2 do

For j=0 to n - 2 - i do

If A[j + 1]<A[j ]

Swap A[j ] and A[j + 1

Example :

89  ↔️ 45 68 90 29 34 17

45 89 ↔️ 68 90 29 34 17

45 68 89 ↔️ 90 ↔️ 29 34 17

45 68 89 29 90 ↔️ 34 17

45 68 89 29 34 90 ↔️ 17

45 68 89 29 34 17    |90

45 ↔️ 68 ↔️ 89 ↔️ 29 34 17    |90

45 68 29 89 ↔️ 34 17 |90

45 68 29 34 89 ↔️ 17 |90

45 68 29 34 17 |89 90

Explanation: The first 2 bubble style passes are mentioned as 89, 45, 68, 90, 29, 34, 17. After a swap of two elements is completed, a new line is seen. The elements to the right of the vertical bar are in their final position and are not taken into account in the algorithm's subsequent iterations.

Performance analysis of bubble sort algorithm:

Clearly, there are n times of the outer loop. In this analysis, the only difficulty is in the inner loop. If we think of a single time the inner loop loops, by remembering that it can never loop more than n times, we can get a clear bound. Since the outer loop can complete n times with the inner loop, the comparison should not take place more than O(n2) times.

For all arrays of size n, the number of key comparisons for the bubble sort version given above is the same.

It depends on the feedback for the number of key swaps. It's the same as the number of primary comparisons, for the worst case of declining arrays.

Observation: If no trades are made by going through the list, the list is sorted and we can stop the algorithm.

While the new version runs on certain inputs faster, in the worst and average situations, it is still in O(n2). The type of bubble is not very useful for a large input set. How easy it is to code the type of bubble.

Basic Message from Brute Force Method

A first use of the brute-force method often results in an algorithm that can be strengthened with a small amount of effort. Compare successive elements of a given list with a given search key until either a match is found (successful search) or the list is exhausted without finding a match (unsuccessful search).

Key takeaway

3.9 Quick Sort

Quick sort is the most efficient method of sorting .It uses the divide and conquer strategy to sort the elements. In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions. For this we choose a pivot element and arrange all elements such that all the elements in the left part are less than the pivot and all those in the right part are greater than it.

Algorithm to implement Quick Sort is as follows.

Consider array A of size n to be sorted. p is the pivot element. Index positions of the first and last element of array A are denoted by ‘first’ and ‘last’.

Algorithm

PARTITION (ARR, BEG, END, LOC)

QUICK_SORT (ARR, BEG, END)

Key takeaway

3.10 Merge Sort

Merge Sort

Merge Sort is based on a divide and conquer strategy. It divides the unsorted list into n sublists such that each sublist contains one element. Each sublist is then sorted and merged until there is only one sublist.

Step 1 : Divide the list into sublists such that each sublist contains only one element.

Step 2 : Sort each sublist and Merge them.

Step 3 : Repeat Step 2 till the entire list is sorted.

Example : Apply Merge Sort on array A= {85,24,63,45,17,31,96,50}

Step1 : A contains 8 elements. First we divide the list into two sublists such that each sublist contains 4 elements. Then we divide each sublist of 4 elements into sublist of two elements each. Finally every sublist contains only one element.

Fig. 4: Example

Step 2 : Now we start from the bottom. Compare 1st and 2nd element. Sort and merge them. Apply this for all bottom elements.

Thus we got 4 sublists as follows

Step 3 : Repeat this sorting and merging until the entire list is sorted. The above four sublists are sorted and merged to form 2 sublists.

Finally, the above 2 sublists are again sorted and merged in one sublist.

We will see one more example on merge sort.

Example : Apply merge Sort on array A={10,5,7,6,1,4,8,3,2,9,12,11}

Step 1 :

Fig 5: Merge sort

Algorithm for Merge Sort:

Let    x = no. Of elements in array A

y = no. Of elements in array B

C = sorted array with no. Of elements n

n = x+y

Following algorithm merges a sorted x element array A and sorted y element array B into a sorted array C, with n = x + y elements. We must always keep track of the locations of the smallest element of A and the smallest element of B which have not yet been placed in C. Let LA and LB denote these locations, respectively. Also, let LC denote the location in C to be filled. Thus, initially, we set

LA : = 1,

LB : = 1 and

LC : = 1.

At each step , we compare A[LA] and B[LB] and assign the smaller element to C[LC].

Then 

LC:= LC + 1,

LA: = LA + 1, if a new element has come from A .

LB: = LB + 1, if a new element has come from B.

Furthermore, if LA> x, then the remaining elements of B are assigned to C; 

LB >y, then the remaining elements of A are assigned to C.

Thus the algorithm becomes

MERGING ( A, x, B, y, C)

1. [Initialize ] Set LA : = 1 , LB := 1 AND LC : = 1

2. [Compare] Repeat while LA <= x and LB <= y

If A[LA] < B[LB] , then

(a) [Assign element from A to C ] set C[LC] = A[LA]

(b) [Update pointers ] Set LC := LC +1 and LA = LA+1

Else

(a) [Assign element from B to C] Set C[LC] = B[LB]

(b) [Update Pointers] Set LC := LC +1 and LB = LB +1

[End of loop]

3. [Assign remaining elements to C]

If LA > x , then

Repeat for K= 0 ,1,2,........,y–LB

Set C[LC+K] = B[LB+K]

[End of loop]

Else

Repeat for K = 0,1,2,......,x–LA

Set C[LC+K] = A[LA+K]

[End of loop]

4. Exit

Key takeaway

3.11 Heap Sort and Radix Sort

Heap Sort is one of the best in-place sorting strategies with no worst-case quadratic runtime. Heap sort requires the creation of a Heap data structure from the specified array and then the use of the Heap to sort the array.

You should be wondering how it can help to sort the array by converting an array of numbers into a heap data structure. To understand this, let's begin by knowing what a heap is.

Heap is a unique tree-based data structure that meets the following special heap characteristics:

2.     Heap property : Every node is either greater or equal to, or less than, or equal to, each of its children. If the parent nodes are larger than their child nodes, the heap is called Max-Heap, and the heap is called Min-Heap if the parent nodes are smaller than their child nodes.

The Heap sorting algorithm is split into two basic components:

●  Creating an unsorted list/array heap.

● By repeatedly removing the largest/smallest element from the heap, and inserting it into the array, a sorted array is then created.

Complexity analysis of heap sort

Time complexity :

●   Worst case : O(n*log n)

●   Best case : O(n*log n)

●   Average case : O(n*log n)

Space complexity : O(1)

Key takeaway :

Radix Sort

Radix sort sorts the elements in the same way that the students' names are sorted alphabetically. Because there are 26 alphabets in English, there are 26 radix in that situation. The names are classified in the first pass according to the ascending order of the first letter of the names.

The names are classified in the second pass according to the ascending order of the second letter. The same procedure is repeated until the sorted list of names is discovered. The names generated in each run are stored in the bucket. The number of passes is determined by the maximum letter length of the name.

When it comes to integers, radix sort arranges the numbers by their digits. From LSB to MSB, the comparisons are done between the digits of the number. The number of passes is determined by the number of digits in the longest number.

Example

Consider the array below, which has a length of 6. Radix sort is used to sort the array.

A = {10, 2, 901, 803, 1024}

Pass 1: (Sort the list according to the digits at 0's place)

10, 901, 2, 803, 1024.

Pass 2: (Sort the list according to the digits at 10's place)

02, 10, 901, 803, 1024

Pass 3: (Sort the list according to the digits at 100's place)

02, 10, 1024, 803, 901.

Pass 4: (Sort the list according to the digits at 1000's place)

02, 10, 803, 901, 1024

As a result, the sorted list obtained in step 4 is ordered using radix sort.

Algorithm

Time complexity

Best case : Ω(n+k)

Average case : θ(nk)

Worst case : O(nk)

Space complexity : O(n+k) ( worst case)

Key takeaway

References: