Python Tutorial: Searching and Sorting Algorithms

Introduction

In this tutorial, we’ll explore two fundamental algorithms in computer science: searching and sorting. We’ll cover linear search and binary search for finding elements in a list, as well as bubble sort and quicksort for ordering lists.

1. Linear Search

Linear search is a straightforward algorithm that inspects each element in a list until it discovers the target value.

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

# Example usage:
my_list = [5, 3, 7, 2, 8]
target = 7
print("Linear Search Result:", linear_search(my_list, target))

2. Binary Search

Binary search is a more efficient algorithm that locates the position of a target value within a sorted array.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Example usage:
my_list = sorted([5, 3, 7, 2, 8])  # Note: Binary search requires a sorted list
target = 7
print("Binary Search Result:", binary_search(my_list, target))

Keep in mind that binary search can only be applied to a list that has already been sorted. It operates by repeatedly dividing the portion of the list that could contain the target value in half until it narrows down to the actual target.

3. Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        # Traverse through all array elements
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("Bubble Sorted Array:", my_list)

4. Quicksort

Quicksort is an efficient divide-and-conquer sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# Example usage:
my_list = [3, 6, 8, 10, 1, 2, 1]
print("Quicksort Sorted Array:", quicksort(my_list))

The power of Quicksort comes from the fact that it sorts 'in-place,' requiring minimal additional memory space. It is one of the most efficient sorting algorithms and is still a common choice for practical use.

Comprehensive Python Examples: Search and Sort Algorithms

Linear Search

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

# Example usage:
my_list = [5, 3, 7, 2, 8]
target = 7
print("Linear Search Result:", linear_search(my_list, target))

Binary Search

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Example usage:
my_list = sorted([5, 3, 7, 2, 8])
target = 7
print("Binary Search Result:", binary_search(my_list, target))

Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("Bubble Sorted Array:", my_list)

Quicksort

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# Example usage:
my_list = [3, 6, 8, 10, 1, 2, 1]
print("Quicksort Sorted Array:", quicksort(my_list))

These examples illustrate some of the fundamental algorithms used in computer science for searching and sorting data. They are foundational concepts that can be built upon for more complex data handling and analysis.