Python Algorithms: Sorting, Searching, and Knapsack

Selection Sort

The Selection Sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.

array = [45, 2, 23, 76, 7]

for i in range(0, len(array) - 1):
    smallest = array[i]
    pos = i
    for j in range(i + 1, len(array)):
        if array[j] < smallest:
            smallest = array[j]
            pos = j
    array[pos] = array[i]
    array[i] = smallest

print(array)

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time, which is much less efficient on large lists than more advanced algorithms.

array = [35, 7, 18, 30]

for i in range(1, len(array)):
    testPosition = i - 1
    while True:
        if testPosition == -1:
            break
        elif array[testPosition] > array[testPosition + 1]:
            temp = array[testPosition]
            array[testPosition] = array[testPosition + 1]
            array[testPosition + 1] = temp
            testPosition -= 1
        else:
            break

print(array)

Merge Sort

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array is:", arr)

Binary Search

Binary Search is a search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

array = [3, 4, 5, 10, 12, 45, 67, 78, 99, 108, 232]
value = int(input("Enter the value to be found: "))

def search(array, start, end, value):
    if end - start <= 1:
        if value == array[start]:
            return start
        if value == array[end]:
            return end
        return -1

    mid = int((start + end) / 2)
    if array[mid] == value:
        return mid
    elif array[mid] > value:
        end = mid - 1
    else:
        start = mid + 1
    return search(array, start, end, value)

index = search(array, 0, len(array) - 1, value)
if index != -1:
    print(f"The element is found at index {index}")
else:
    print("Element not found")

Fractional Knapsack Problem

The Fractional Knapsack problem involves filling a knapsack with items to maximize the total profit, where items can be broken into smaller pieces.

class Item:
    def __init__(self, profit, weight):
        self.profit = profit
        self.weight = weight

def fractionalKnapsack(W, arr):
    arr.sort(key=lambda x: (x.profit / x.weight), reverse=True)
    finalvalue = 0.0
    for item in arr:
        if item.weight <= W:
            W -= item.weight
            finalvalue += item.profit
        else:
            finalvalue += item.profit * W / item.weight
            break
    return finalvalue

if __name__ == "__main__":
    W = 50
    arr = [Item(60, 10), Item(100, 20), Item(120, 30)]
    max_val = fractionalKnapsack(W, arr)
    print(max_val)