Searching and sorting are fundamental operations in computer science and play a crucial role in various algorithms and applications. In Python, these operations are implemented using different techniques, each with its own advantages and use cases. In this guide, we will explore the workings of various searching and sorting algorithms in Python, including

1. Binary search
2. Linear search
3. Bubble sort
4. Insertion sort
5. heap sort
6. Merge sort.

Understanding these algorithms in depth will not only improve your problem-solving skills but also help you write more efficient and optimized Python code.

Binary Search in Python

Imagine you have a bookshelf full of books, and you’re looking for a specific book. If the books are arranged in alphabetical order, you might start by looking at the book in the middle. If the book you’re looking for comes after the one in the middle, you’d then focus on the half of the shelf that comes after the middle book. You keep dividing the remaining books in half and narrowing down your search until you find the book you’re looking for.

Binary search in Python works in a similar way. It’s like flipping through a dictionary to find a word. Instead of starting at the beginning and flipping through each page, you open the book roughly in the middle and see if the word you’re looking for comes before or after that page. Based on that, you eliminate half of the remaining pages and continue this process until you find the word.

In programming, binary search is used to find a specific element in a sorted list efficiently. It starts by comparing the target value to the middle element of the list. If the target value is less than the middle element, the search continues in the lower half of the list. If the target value is greater, the search continues in the upper half. This process is repeated until the target value is found or the list is empty.

Let’s check out the code for binary search in Python

Assume we have a sorted list of elements, and we are looking for the index position of 45.

[12, 24, 32, 39, 45, 50, 54]

compare the n(which is 45 in our case) with the middle element of the elements on the left side of the mid and set high to high = mid-1.

Repeat until the number that we are searching for is found.

Now, let us implement this in the form of coding

# Iterative Binary Search Function method Python Implementation  
# It returns index of n in given list1 if present,   
# else returns -1   
def binary_search(list1, n):  
    low = 0  
    high = len(list1) - 1  
    mid = 0  
  
    while low <= high:  
        # for get integer result   
        mid = (high + low) // 2  
  
        # Check if n is present at mid   
        if list1[mid] < n:  
            low = mid + 1  
  
        # If n is greater, compare to the right of mid   
        elif list1[mid] > n:  
            high = mid - 1  
  
        # If n is smaller, compared to the left of mid  
        else:  
            return mid  
  
            # element was not present in the list, return -1  
    return -1  
  
  
# Initial list1  
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 45  
  
# Function call   
result = binary_search(list1, n)  
  
if result != -1:  
    print("Element is present at index", str(result))  
else:  
    print("Element is not present in list1")  

Output:

Element is present at index 4

Explanation:

1. Initialize variables low, high, and mid:
   • low is set to 0, representing the lowest index of the list.
   • high is set to the length of the list minus 1, representing the highest index of the list.
   • mid is initially set to 0 (this will be updated during the search).
2. The while loop continues until low is less than or equal to high.
3. Inside the loop, mid is calculated as the floor division of the sum of high and low by 2, which gives the index of the middle element.
4. If the element at the middle index (list1[mid]) is less than the target value n, the low pointer is moved to mid + 1, effectively discarding the left half of the list.
5. If list1[mid] is greater than n, the high pointer is moved to mid - 1, discarding the right half of the list.
6. If list1[mid] is equal to n, the function returns mid, indicating that the element was found at index mid.
7. If the loop exits without finding the element (low becomes greater than high), the function returns -1, indicating that the element is not present in the list.
8. Finally, the function is called with a sample list list1 and a target value n = 45. If the result is not -1, it prints the index where the element is found; otherwise, it prints that the element is not present in the list.

Another way for binary search is recursive binary search

# Python program for recursive binary search.  
# Returns index position of n in list1 if present, otherwise -1  
def binary_search(list1, low, high, n):   
  
   # Check base case for the recursive function  
   if low <= high:  
  
      mid = (low + high) // 2  
  
      # If element is available at the middle itself then return the its index  
      if list1[mid] == n:   
         return mid   
  
      # If the element is smaller than mid value, then search moves  
      # left sublist1  
      elif list1[mid] > n:   
         return binary_search(list1, low, mid - 1, n)   
  
      # Else the search moves to the right sublist1  
      else:   
         return binary_search(list1, mid + 1, high, n)   
  
   else:   
      # Element is not available in the list1  
      return -1  
  
# Test list1ay   
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 32  
  
# Function call   
res = binary_search(list1, 0, len(list1)-1, n)   
  
if res != -1:   
   print("Element is present at index", str(res))  
else:   
   print("Element is not present in list1")  

Output:

1. We calculate the middle number as in the last program.
2. We have used the if statement to proceed with the binary search.
3. If the middle value equal to the number that we are looking for, the middle value is returned.
4. If the middle value is less than the value, we are looking then our recursive function binary_search() again and increase the mid value by one and assign to low.
5. If the middle value is greater than the value we are looking then our recursive function binary_search() again and decrease the mid value by one and assign it to low.
6. In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the binary_search() function.

This is because we can’t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.

Linear Search in Python

Once upon a time, there was a librarian named Smita who had a huge collection of books. One day, a young reader named Rishab came to the library looking for a specific book. However, Rishab didn’t know where to find it.

Seeing Rishab’s dilemma, Sam decided to help. Sam explained that they could use a method called “linear search” to find the book. Sam explained that linear search is like looking for a name in a phone book. You start at the beginning and check each name until you find the one you’re looking for.

Smita and Rishab started at the first bookshelf and checked each book, one by one, until they found the book Rishab was looking for. It took some time, but they eventually found it.

Rishab was amazed by how simple and effective linear search was. Sam explained that while linear search is straightforward, it can take longer if there are a lot of items to search through. However, for smaller collections, like the library’s bookshelves, it works just fine.

From then on, Rishab knew that whenever they needed to find something in a list, they could use linear search to do it step by step, just like flipping through a phone book.

Let’s say we want to find element 7 in the below list

Linear Search Algorithm

LinearSearch(list, key)  
  for each item in the list  
    if item == value  
      return its index position  
   return -1 

1. LinearSearch(list, key): This is a function named LinearSearch that takes two arguments: list (the list to search through) and key (the value to search for).
2. for each item in the list: This line initiates a loop that iterates over each item in the given list.
3. if item == value: For each item in the list, it checks if the item is equal to the key value we’re searching for.
4. return its index position: If the item is found to be equal to the key, the function returns the index position of that item in the list.
5. return -1: If the loop completes without finding the key in the list, the function returns -1 to indicate that the key was not found in the list.

In simpler terms, the function goes through each item in the list one by one. If it finds an item that matches the key, it returns the index position of that item. If no match is found after checking all items, it returns -1 to indicate that the key is not in the list.

Full Program:

def linear_Search(list1, n, key):  
  
    # Searching list1 sequentially  
    for i in range(0, n):  
        if (list1[i] == key):  
            return i  
    return -1  
  
  
list1 = [1 ,3, 5, 4, 7, 9]  
key = 7  
  
n = len(list1)  
res = linear_Search(list1, n, key)  
if(res == -1):  
    print("Element not found")  
else:  
    print("Element found at index: ", res)  

Output:

Element found at index:  4

The linear search algorithm is ideal for smaller lists (less than 100 elements) because it examines each element to find the desired number. However, for larger lists, such as one with 10,000 elements where the desired element is at the end, this method can be time-consuming as it compares each element sequentially.

For faster results with larger lists, the binary search algorithm is more suitable.

Bubble Sorting in Python

Imagine you have a row of numbers written on a whiteboard from left to right. Bubble sort is like a teacher who wants to arrange these numbers in ascending order.

The teacher starts from the left and compares the first two numbers. If the left number is larger than the right number, the teacher swaps them. Then, the teacher moves one step to the right and compares the next pair of numbers. This process continues until the teacher reaches the end of the row.

But the teacher doesn’t stop there. She repeats this process multiple times, each time starting from the left and moving to the right. Each time she goes through the row, the largest unsorted number “bubbles up” to its correct position at the end of the row.

After several passes through the row, all the numbers are sorted in ascending order, and the teacher can proudly say that she has used bubble sort to arrange the numbers.

Let us start by taking an example

We are creating a list of elements, which stores the integer numbers

list1 = [5, 3, 8, 6, 7, 2]

Here the algorithm sort the elements –

First iteration

[5, 3, 8, 6, 7, 2]

It compares the first two elements and here 5>3 then swap with each other. Now we get new list is –

[3, 5, 8, 6, 7, 2]

In second comparison, 5 < 8 then swapping happen –

[3, 5, 8, 6, 7, 2]

In third comparison, 8>6 then swap –

[3, 5, 6, 8, 7, 2]

In fourth comparison, 8>7 then swap –

[3, 5, 6, 7, 8, 2]

In fifth comparison, 8>2 then swap-

[3, 5, 6, 7, 2, 8]

Here the first iteration is complete and we get the largest element at the end. Now we need to the len(list1) – 1

Second Iteration

[3, 5, 6, 7, 2, 8] – > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place

[3, 5, 6, 7, 2, 8] – > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place

[3, 5, 6, 7, 2, 8] – > [3, 5, 6, 7, 2, 8] here, 6<7 then no swap taken place

[3, 5, 6, 7, 2, 8] – > [3, 5, 6, 2, 7, 8] here 7>2 then swap their position. Now

[3, 5, 6, 2, 7, 8] – > [3, 5, 6, 2, 7, 8] here 7<8 then no swap taken place.

and so on…

Python code for Bubble Sort

# Creating a bubble sort function  
def bubble_sort(list1):  
    # Outer loop for traverse the entire list  
    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):  
                temp = list1[j]  
                list1[j] = list1[j+1]  
                list1[j+1] = temp  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort function  
print("The sorted list is: ", bubble_sort(list1))  

Output:

Without using a temp variable

We can also swap the elements without using the temp variable. Python has a very unique syntax. We can use the following lines of code.

Example –

def bubble_sort(list1):  
    # Outer loop for traverse the entire list  
    for i in range(0,len(list1)-1):  
        for j in range(len(list1)-1):  
            if(list1[j]>list1[j+1]):   
                # here we are not using temp variable  
                list1[j],list1[j+1] = list1[j+1], list1[j]  
    return list1  
  
list1 = [5, 3, 8, 6, 7, 2]  
print("The unsorted list is: ", list1)  
# Calling the bubble sort function  
print("The sorted list is: ", bubble_sort(list1))  

Output:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

Insertion Sorting in Python

Insertion sort is a more efficient sorting algorithm compared to bubble sort. It’s like sorting a deck of cards by picking up one card at a time and placing it in its correct position in your hand. While playing cards, most people prefer sorting them in ascending order to quickly see their hands.

Insertion sort is straightforward and easy to implement, making it a common choice for introductory programming lessons. It’s an in-place and stable algorithm, which means it doesn’t require extra space and maintains the relative order of equal elements.

However, insertion sort can be slow for large datasets because it uses nested loops to sort the elements. There are more efficient algorithms available for sorting larger datasets.

Here’s how the insertion sort algorithm works:

1. Start with the second element (index 1) of the array.
2. Compare this element with the one before it (element at index 0). If the second element is smaller, swap them.
3. Move to the third element (index 2) and compare it with the elements before it, moving backward, until it’s in the correct position.
4. Repeat this process for each element in the array.

Here’s an example to demonstrate insertion sort:

Consider an array: [5, 2, 4, 6, 1, 3]

1. Start with the second element (2). Compare it with the first element (5). Since 2 is smaller, swap them. Array becomes: [2, 5, 4, 6, 1, 3]
2. Move to the third element (4). Compare it with the elements before it (5 and 2) and insert it in its correct position. Array becomes: [2, 4, 5, 6, 1, 3]
3. Continue this process for the remaining elements until the array is sorted: [1, 2, 3, 4, 5, 6]

The array is now sorted using the insertion sort algorithm.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print("Sorted array is:", arr)

Output:

Insertion sort is a simple and inefficient algorithm that has many advantages, but there are more efficient algorithms are available.

Heap Sorting in Python

Heap sort is a sorting algorithm that sorts a list by first converting it into a binary heap. A binary heap is a complete binary tree where each node has a value greater than or equal to its children (max heap) or less than or equal to its children (min heap).

Here’s how heap sort works in layman’s terms:

1. Heapify: Convert the input list into a binary heap. This involves rearranging the elements in the list so that they satisfy the heap property (either max heap or min heap).
2. Sort: Extract elements from the heap one by one. Since the root of the heap will always be the maximum (or minimum) element, remove the root, swap it with the last element in the heap, and then heapify the reduced heap.
3. Repeat step 2 until the heap is empty. The extracted elements form a sorted list.

Here’s an example to illustrate heap sort:

Consider the input list: [4, 10, 3, 5, 1]

1. Heapify: Convert the list into a max heap: [10, 5, 3, 4, 1]
2. Sort: Extract elements from the heap one by one:
   • Extract 10 (the maximum element), swap it with 1 (the last element), and heapify the reduced heap: [5, 4, 3, 1, 10]
   • Extract 5, swap it with 1, and heapify: [4, 1, 3, 5, 10]
   • Extract 4, swap it with 3, and heapify: [3, 1, 4, 5, 10]
   • Extract 3, swap it with 1, and heapify: [1, 3, 4, 5, 10]
   • Extract 1, swap it with 1 (itself), and heapify: [1, 3, 4, 5, 10]
   The sorted list is [1, 3, 4, 5, 10].

Here’s the Python code for heap sort:

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1
    right = 2 * i + 2

    # Check if left child of root exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child of root exists and is greater than root
    if right < n and arr[right] > arr[largest]:
        largest = right

    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Build a maxheap
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap
        heapify(arr, i, 0)

# Example usage
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("Sorted array is:", arr)

Explanation for Above:

1. heapify function: This function is used to maintain the heap property (either max heap or min heap) of a subtree rooted at index i in the list arr.
   • It takes three arguments: the list arr, the size of the heap n, and the index i of the root of the subtree.
   • It first assumes that the root (i) is the largest (or smallest) element.
   • It then compares the root with its left and right child (if they exist) and updates the index of the largest (or smallest) element accordingly.
   • If the largest (or smallest) element is not the root, it swaps the root with the largest (or smallest) element and recursively calls heapify on the affected subtree.
2. heap_sort function: This function performs the heap sort algorithm on the input list arr.
   • It first builds a max heap from the input list by calling heapify on all non-leaf nodes in reverse order (from the last non-leaf node to the root).
   • It then repeatedly extracts the maximum element from the heap (which is always the root of the max heap), swaps it with the last element in the heap, and reduces the size of the heap by 1.
   • After each extraction, it calls heapify on the reduced heap to maintain the heap property.
   • The sorted elements are placed at the end of the list, resulting in a sorted list in ascending order.
3. Example usage:
   • The example usage at the end of the code demonstrates sorting an input list [4, 10, 3, 5, 1] using the heap_sort function.
   • The sorted array is printed as the output, which should be [1, 3, 4, 5, 10].

Overall, heap sort is an efficient sorting algorithm with a time complexity of O(n log n) for both best and worst cases, where n is the number of elements in the input list.

Merge Sorting in Python

Merge sort is a divide-and-conquer algorithm that works as follows:

1. Divide: The input list is divided into two halves.
2. Conquer: Each half is recursively sorted.
3. Combine: The sorted halves are merged to produce a single sorted list.

Here’s a step-by-step explanation of how it works with an example:

1. Divide: Suppose we have an unsorted list [38, 27, 43, 3, 9, 82, 10]. We divide it into two halves: [38, 27, 43, 3] and [9, 82, 10].
2. Conquer: We recursively sort each half. After sorting, the two halves become [3, 27, 38, 43] and [9, 10, 82].
3. Combine: Finally, we merge the two sorted halves into a single sorted list. We compare the first elements of each half (3 and 9) and choose the smaller one (3) to be the first element of the merged list. We continue this process until all elements are merged, resulting in [3, 9, 10, 27, 38, 43, 82], which is the sorted list.

Here’s the Python implementation of merge sort:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0

    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    result.extend(left[left_idx:])
    result.extend(right[right_idx:])

    return result

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

In this implementation, the merge_sort function recursively divides the input list into halves until each sublist has only one element. Then, the merge function merges two sorted sublists into a single sorted list. This process continues until the entire list is sorted.

Difference between Binary Search and Linear Search

Feature	Binary Search	Linear Search
Search Speed	O(log n)	O(n)
Suitable For	Sorted arrays	Unsorted arrays
Iterative/Recursive	Both	Recursive only
Algorithm	Divide and conquer	Sequential
Performance	Faster for large datasets	Slower for large datasets
Memory Usage	Requires less memory due to iterative approach	Uses more memory due to recursive approach
Implementation	More complex due to divide and conquer method	Simple due to sequential checking

Feature	Bubble Sort	Insertion Sort	Merge Sort
Time Complexity	O(n^2)	O(n^2)	O(n log n)
Space Complexity	O(1)	O(1)	O(n)
Stability	Stable	Stable	Stable
Best Case	O(n)	O(n)	O(n log n)
Worst Case	O(n^2)	O(n^2)	O(n log n)
Average Case	O(n^2)	O(n^2)	O(n log n)
Adaptive	Yes	Yes	No
In-Place	Yes	Yes	No (requires extra space)
Suitable For	Small datasets	Small datasets	Large datasets
Comparison	Compares adjacent elements and swaps if needed	Compares and inserts elements in correct position	Divides list into two halves and merges them
Performance	Slow for large datasets	Slow for large datasets	Faster for large datasets

In conclusion, understanding how searching and sorting work in Python can greatly enhance your ability to manage and process data effectively. Whether you’re looking for a specific piece of information in a large dataset or trying to organize data for easier analysis, knowing the inner workings of algorithms like binary search, linear search, bubble sort, insertion sort, heap sort, and merge sort can be incredibly valuable. These algorithms offer different trade-offs in terms of speed, complexity, and suitability for different types of data. By delving into the details of these algorithms, you can gain a deeper understanding of how Python handles data manipulation, which can be applied to a wide range of real-world problems in fields like data science, software development, and more.