Unit - V -Data Structure - Searching, Sorting & Hashing

 

UNIT- V - Data Structure

Searching

Searching in a data structure is the process of finding a specific element within a collection of items. The two primary methods are linear search (for unsorted data) and binary search (for sorted data).

 1. Linear Search

Linear search, also known as sequential search, checks each element in a data structure one by one, from start to finish, until the target is found. It is simple to implement and works on both sorted and unsorted lists, but is inefficient for large datasets due to a time complexity of O(n). 

 How it works:

1.      Start the program.

2.      Read the number of elements and store them in a list.

3.      Read the element to be searched.

4.      Compare the search element with each element of the list one by one.

5.      If a match is found, display the position.

6.      If no match is found after checking all elements, display “Element not found”.

7.      Stop the program.

 

# Linear Search Program

 L = []

n = int(input("Enter number of elements: "))

 for i in range(n):

    L.append(int(input("Enter element: ")))

 

key = int(input("Enter element to search: "))

 

found = False

for i in range(n):

    if L[i] == key:

        print("Element found at position", i+1)

        found = True

        break

 if not found:

    print("Element not found")

2. Binary Search

Binary search is an efficient algorithm for finding an element's position within a sorted array by repeatedly dividing the search interval in half. It operates on the principle of a divide and conquer strategy and has a time complexity of O(log n), making it significantly faster than a linear search for large datasets. 

 How Binary Search Works

The core idea is to maintain a search space defined by a low index (start of the space) and a high index (end of the space). 

 

1.      Start the program.

2.      Read n elements and store them in a list.

3.      Sort the list.

4.      Read the search element (key).

5.      Set low = 0 and high = n - 1.

6.      Find mid = (low + high) // 2.

7.      If list[mid] == key, display position and stop.

8.      If key < list[mid], set high = mid - 1.

9.      Else set low = mid + 1.

10.  Repeat steps 6–9 until low > high.

11.  If not found, display “Element not found”.

12.  Stop.

 

# Binary Search Program

 L = []

n = int(input("Enter number of elements: "))

 

for i in range(n):

    L.append(int(input("Enter element: ")))

 

L.sort()   # Binary search works only on sorted list

print("Sorted list:", L)

 

key = int(input("Enter element to search: "))

 

low = 0

high = n - 1

found = False

 

while low <= high:

    mid = (low + high) // 2

 

    if L[mid] == key:

        print("Element found at position", mid+1)

        found = True

        break

    elif key < L[mid]:

        high = mid - 1

    else:

        low = mid + 1

 

if not found:

    print("Element not found")

SORTING

Sorting is linear ordering of list of items. Different types of sorting are

1. Bubble Sort

2. Insertion sort

3. Shell sort

4. Selection  sort

 

BUBBLE SORT

Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.  If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on. This process will be repeated for n-1 times.(n- total elements)

 

# Bubble Sort Program

n = int(input("Enter number of elements: "))

arr = []

 

for i in range(n):

    arr.append(int(input("Enter element: ")))

 

# Bubble Sort Logic

for i in range(n-1):

    for j in range(n-1-i):

        if arr[j] > arr[j+1]:

            arr[j], arr[j+1] = arr[j+1], arr[j]

 

print("Sorted list:", arr)

 

SELECTION SORT

  The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place. After the second pass, the next largest is in place. This process continues and requires n”1n”1passes to sort n items, since the final item must be in place after the (n”1)(n”1) last pass. 

# Selection Sort Program

n = int(input("Enter number of elements: "))

arr = []

 

for i in range(n):

    arr.append(int(input("Enter element: ")))

 

# Selection Sort Logic

for i in range(n-1):

    min_index = i

    for j in range(i+1, n):

        if arr[j] < arr[min_index]:

            min_index = j

    arr[i], arr[min_index] = arr[min_index], arr[i]

 

print("Sorted list:", arr)

 

INSERTION SORT

1. It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort.

2. It has one of the simplest implementation

3. It is efficient for smaller data sets, but very inefficient for larger lists.

4. Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

5. It is better than Selection Sort and Bubble Sort algorithms.

6. Its space complexity is less, like Bubble Sorting, insertion sort also requires a single additional memory space.

7. It is Stable, as it does not change the relative order of elements with equal keys

# Insertion Sort Program

n = int(input("Enter number of elements: "))

arr = []

 

for i in range(n):

    arr.append(int(input("Enter element: ")))

 

# Insertion Sort Logic

for i in range(1, n):

    key = arr[i]

    j = i - 1

 

    while j >= 0 and arr[j] > key:

        arr[j + 1] = arr[j]

        j -= 1

 

    arr[j + 1] = key

 

print("Sorted list:", arr)

 

RADIX SORT

Radix Sort is a linear sorting algorithm (for fixed length digit counts) that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys. 

·         It repeatedly distributes the elements into buckets based on each digit's value. This is different from other algorithms like Merge Sort or Quick Sort where we compare elements directly.

·         By repeatedly sorting the elements by their significant digits, from the least significant to the most significant, it achieves the final sorted order.

·         We use a stable algorithm like Counting Sort to sort the individual digits so that the overall algorithm remains stable.

To perform radix sort on the array [170, 45, 75, 90, 802, 24, 2, 66], we follow these steps:

Step 1: Find the largest element, which is 802. It has three digits, so we will iterate three times.

Step 2: Sort the elements based on the unit place digits (X=0).

Step 3: Sort the elements based on the tens place digits.

Step 4: Sort the elements based on the hundreds place digits.

Step 5: The array is now sorted in ascending order.

# Radix Sort Program

 def counting_sort(arr, exp):

    n = len(arr)

    output = [0] * n

    count = [0] * 10

 

    for i in range(n):

        index = (arr[i] // exp) % 10

        count[index] += 1

 

    for i in range(1, 10):

        count[i] += count[i - 1]

 

    i = n - 1

    while i >= 0:

        index = (arr[i] // exp) % 10

        output[count[index] - 1] = arr[i]

        count[index] -= 1

        i -= 1

 

    for i in range(n):

        arr[i] = output[i]

 

def radix_sort(arr):

    max_num = max(arr)

    exp = 1

    while max_num // exp > 0:

        counting_sort(arr, exp)

        exp *= 10

 

# Main Program

n = int(input("Enter number of elements: "))

arr = []

 

for i in range(n):

    arr.append(int(input("Enter element: ")))

 

radix_sort(arr)

print("Sorted list:", arr)