Algorithms with Python

Algorithms with Python

Algorithms with Python - Part 1

An algorithm, in layperson’s terms, is a sequence of instructions. They provide a step-by-step procedure to be followed by a computer, in order to solve a problem or make decisions. In this article, we will only be discussing the searching and sorting algorithms; albeit, there are more algorithms in the programming realm.

Searching algorithms are used to locate particular elements within a data structure. Linear search and binary search are two prevalent searching algorithms.

Linear or sequential search is the simplest searching algorithm. This is implemented by iterating through the elements of the data structure one at a time and comparing each element against the target search item. Therefore, the time complexity of the algorithm - O(nn) - depends on the number of elements, making it suitable for smaller and simpler programs.

Let’s implement a linear search algorithm to iterate over a list of cube numbers from 1 to 100 (cube_numbers). We have defined the linear_search function to take two parameters; the data structure (list) and the search item (target). Inside the function, we use a for loop to iterate over this list. Then, we check if the current element is equal to the target value using an if condition. Code outputs a message “85 is not in the list” implying that 85 is not a cube number.

def linear_search(list, target):
    for i in list:
        if i == target:
            return f"{target} is in the list"

    return f"{target} is not in the list"


cube_numbers = [1, 8, 27, 64]
target = 85
print(linear_search(cube_numbers, target))

Binary or logarithmic search is implemented by repeatedly halving the search range and comparing the target search item against the middle element. Therefore, binary search befits sorted data structures. Unlike linear search, binary search is effective for larger data structures since the time complexity is logarithmic - O(loglog nn) -.

Let’s implement a binary search algorithm to search through a list of square numbers. We have defined the binary_search function to take two parameters; the data structure (list) and the search item (target). Inside the function, we initialize two variables (left and right) with the indexes of the first and the last elements of the list. This is then used to find the index of the middle value (mid) inside the while loop. The while loop is used to iterate through the list until the search range is not empty.

If the mid element is equal to the target, function returns a success message. If the mid element is smaller than the target value, target value must be in the right half of the list. So, the left index is assigned to mid + 1, so that the search range is narrowed down to the right half of the current range.
Otherwise, if the mid element is larger than the target value, target value must be in the left half of the list. So, the right index is assigned to mid - 1, so that the search range is narrowed down to the left half of the current range.

Since the mid value was never equal to the target inside the while loop, this code outputs the message “81 is not a square number” inferring that 81 was not found in the list.

def binary_search(list, target):
    left, right = 0, len(list) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if list[mid] == target:
            return f"{target} is a square number"
        elif list[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return f"{target} is not a square number"
    
    
square_numbers = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
target = 81
print(binary_search(square_numbers, target))

Sort

We discussed in the binary search section, that in order to apply binary search the data structure must be sorted. However, binary search can be applied to an unsorted data structure by first sorting it before applying the searching algorithm. So, let’s try out a few sorting algorithms in this section.

  • Selection Sort

Selection sort is a simple sorting algorithm that works by selecting the smallest element from the unsorted portion of the data structure and swapping it into the correct position until the entire data structure is sorted.

Let’s implement a selection sort algorithm to sort an unsorted list of square numbers. We have defined the selection_sort function to take a data structure (list) as its parameter. Inside the function, we have assigned a constant variable (LEN) to store the length of the list. This will be used in the for loop to iterate through the list. We use a nested for loop to find the smallest element (list[min_index]) and swap it with the current element (list[i]).

Inside the outer loop, we initialize a variable (min_index) to the index of the current element (i), so that such element is the initial minimum. Inside the inner loop we compare each remaining element (list[j]) with current minimum (list[min_index]). If the element is smaller than the current minimum, current minimum index will be updated with the index of the new smallest element (j). After the inner loop completes, we swap the currently running outer loop element ( list[i]) with the minimum element ( list[min_index]).

The process repeats until the outer loop completes, resulting in a sorted list.

def selection_sort(list):
    LEN = len(list)

    for i in range(LEN):
        min_index = i
  
        for j in range(i + 1, LEN):
            if list[j] < list[min_index]:
                min_index = j
		
        list[i], list[min_index] = list[min_index], list[i]

    print(list)


selection_sort([100, 64, 81, 1, 25, 16, 4, 49, 9, 36])

  • Bubble Sort

Bubble sort is another simple algorithm that traverse through a data structure comparing adjacent elements and swapping them if they are out of order. At the end of each iteration the highest (or lowest for descending order) element will bubble its way up through the data structure.

Let’s implement a bubble sort algorithm to sort the same list from previous example. We have defined the bubble_sort function to take the list as its parameter. Unlike, selection sort, our LEN constant for bubble sort is len(list) - 1 since we don’t need to compare or swap the last element. We use a nested for loop to compare adjacent elements (list[j] and list[j + 1]) and swap them to correct place if needed.

Inside the outer loop, we initialize a variable swapped to False. This will be used to keep a track of swaps during each iteration. If a swap does not occur in a particular iteration, that means the list is sorted and the function execution can be stopped early. Inside the inner loop we compare each element (list[j]) with the next element (list[j + 1]). If the current element is larger than the next element, elements will be swapped.

The process repeats until the outer loop completes or outer loop breaks out due to no swap occurrences in the inner loop.

def bubble_sort(list):
    LEN = len(list) - 1

    for i in range(LEN):
        swapped = False

        for j in range(LEN - i):
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
                swapped = True

        if swapped == False:
            break

    print(list)


bubble_sort([100, 64, 81, 1, 25, 16, 4, 49, 9, 36])

  • Insertion Sort

Insertion sort is the last basic sorting algorithm we will be discussing in this article. Insertion sort works by building a sorted sub data structure towards the left of the data structure. This is done by comparing one element at a time and inserting it into its correct position within the already sorted part of the data structure.

Let’s implement an insertion sort algorithm to sort the same list of square numbers. We have defined the insertion_sort function to take the list as its parameter. Similar to selection sort, LEN constant for insertion sort is initialized to len(list). We use a nested for loop to compare each element with its previous elements (sorted part) and insert it in the correct place with those elements.

Outer for loop will start iteration from second element (index 1) since the first element is assumed to be already sorted. Inside the outer loop, we initialize a variable key to the element of current index (list[i]) and a variable j to the index of the previous element (i - 1). Then, we use a inner while loop to compare these two variables. If the key is smaller than the current element (list[j]) , it shifts the element to the right in order to make space to insert key to the correct place. The while loop continues until j becomes less than 0 or until key is no longer smaller than the current element (list[j]). After the while loop, key will be assigned to the correct position in the sorted part (list[j + 1]).

Then, the process repeats for the next element in the list. This keeps building the sorted part of the list from left to right until the entire list is sorted.

def insertion_sort(list):
    LEN = len(list)

    for i in range(1, LEN):
        key = list[i]
        j = i - 1

        while j >= 0 and key < list[j]:
            list[j + 1] = list[j]
            j -= 1
        
        list[j + 1] = key

    print(list)


insertion_sort([100, 64, 81, 1, 25, 16, 4, 49, 9, 36])

In this article we discussed linear search, binary search; and selection sort, bubble sort and insertion sort. In the next part of this article we will be discussing merge sort, quick sort and a comparison of these five sorting algorithms.

Comments

Post a Comment

Popular posts from this blog

Data Structures - Part 1

Data Structures - Part 1 Data Structures (Abstract Data Types) - Part 1 (Array) Data structures are specific methods of organizing and storing collections of data in a way that enables efficient access and manipulation. In a previous article , we discussed python specific data structures (built-in data types: list, tuple, set & dictionary) . In this series of articles, we will explore common abstract data types (ADTs) that are language-agnostic. These ADTs can be classified into two categories: linear and non- linear. Linear data structures; Array , Linked List , Stack , Queue Non-linear data structures; Tree , Hash Map , Graph 1. Array Arrays are one of the most fundamental data structures, designed to store collections of data (elements) of the same data type . These elements are stored in contiguous memory locations, allowing access to each element using its index. Arrays are prone to an exception if accessed with an index that exceeds the array’s boun...
Read more

OOP with Python - Part 2

OOP with Python - Part 2 OOP with Python - Part 2 We covered the basics of Object-Oriented Programming (OOP) , including Classes and Objects, Encapsulation, and Inheritance in OOP with Python - Part 1 . In this second part, we will discuss the remaining two key principles of OOP; Abstraction and Polymorphism . Abstraction Abstraction is the concept of hiding the complex implementation details of a system and exposing essential features of an object. This allows us to focus on what an object does but not how it is done. This can reduce programming complexity and enhance code maintainability. In Python, abstraction can be achieved using abstract classes and methods provided by the abc module. An abstract class is a class that cannot be instantiated and typically contains one or more abstract methods. An abstract method is a method that is declared but contains no implementation. Subclasses of the abstract class must provide implementations for all abstract m...
Read more

OOP with Python - Part 1

OOP with Python - Part 1 OOP with Python - Part 1 OOP ( Object Oriented Programming ) is a programming paradigm (a design style or an approach with its related design principles and techniques) which considers objects as the primary building block of a software program. In our previous articles, we were following a procedural approach where we were writing our code in a sequential manner. As compared to the procedural approach, OOP provides benefits like modularity, ease of maintenance, flexibility, scalability and reusability which makes it ideal for large scale real world projects. Python, being a general purpose language, supports both procedural and OOP paradigms. So, in this article let’s talk about the basics of OOP and how to implement them in Python. Class & Object An object is a real world entity with properties (aka attributes or data or members) and behaviors (aka methods or functions). For instance, a cat is an object. It has a name, color ...
Read more