Sorting and Searching Algorithms in Python

Sorting and Searching Algorithms in Python 🔍

In the world of software development, search and sorting algorithms play a fundamental role. These techniques allow us to organize and obtain data in a very efficient way, which is essential to optimize the performance of applications. In this article, we will look at some examples of algorithms in Python, both sorting algorithms and search algorithms.

What are Sorting Algorithms? 📊🔄

In computer science, sorting algorithms are crucial for the optimization of a task. They allow data to be organized so that it can be accessed and used more efficiently. A sorting algorithm allows us to rearrange a list of elements or nodes in a specific order, for example in ascending or descending order depending on the occasion. In the following we will see examples of two of the best known sorting algorithms in programming, the Bubble Sort algorithm (Bubble Sort), and the Insertion Sort algorithm (Insertion Sort).

Bubble Sort

The bubble sort algorithm is one of the simplest but least efficient algorithms. It works by comparing pairs of elements and swapping them if they are in the wrong order, this process is done over and over again until the list is sorted correctly.

1def bubble_sort(list):
2    length = len(list)
3    for i in range(length):
4        for j in range(0, (length-i) - 1):
5
6
7            if list[j] > list[j + 1]:
8                auxiliar = list[j + 1]
9                list[j + 1] = list[j]
10                list[j] = auxiliar
11    return list
12
13unordered_list = [3, 6, 7, 8, 3, 45, 23, 0, 16, 26, 6, 7, 50]
14ordered_list = bubble_sort(unordered_list)
15print(ordered_list) # output: [0, 3, 3, 6, 6, 7, 7, 8, 16, 23, 26, 45, 50]

In this example, making use of the loop structure for we go through the list of unordered numbers twice, then with the help of a conditional if we ask if the current number is greater than the next number if so we invert the position of the numbers, the function will do this same process again and again until the numbers are perfectly ordered, finally we return the ordered list. This algorithm has a time complexity of O(n^2) (Check this link to know more about complexity and optimization of algorithms which makes it useful for sorting small lists, but very inefficient for sorting larger lists.

Pros and Cons of Bubble Sort:

Pros:

• Simplicity: The bubble algorithm is easy to understand and implement, which makes it a good choice for introducing ordering concepts in programming.
• Simple deployment: Requires little amount of code and does not involve complex data structures.

Cons:

• Slow for large lists: Due to its quadratic complexity the bubble algorithm becomes slow in practice for lists of considerable size.
• Does not consider partial order: Unlike other algorithms, the bubble algorithm performs the same number of comparisons and swaps regardless of whether the list is already largely sorted.

Insertion Sort

The insertion sort algorithm is a simple but efficient algorithm. It works by dividing the list into two parts, an ordered part and an unordered part. As the unordered list is traversed, elements are inserted in the correct position in the ordered part. Next, we will see an example of code:

1def insertion_sort(list):
2    for i in range(1, len(list)):
3        actual = list[i]
4        index = i
5
6        """
7        This loop interchanges the two position numbers, as long as the previous number is larger than the current number.
8        """
9
10        while index > 0 and list[index - 1] > actual:
11            list[index] = list[index - 1]
12            index = index - 1
13        list[index] = actual
14
15    return list
16
17unordered_list = [39, 45, 32, 4, 2, 85, 43, 7, 18, 16, 5, 67, 32]
18ordered_list = insertion_sort(unordered_list)
19print(ordered_list) # output: [2, 4, 5, 7, 16, 18, 32, 32, 39, 43, 45, 67, 85]

In this example, the second element of the list is taken and with the help of a while loop, we swap the current number with the previous number as long as the previous number is larger than the current number, this process is done again and again until the list is completely sorted. The insertion sort algorithm has a time complexity of O(n) in the best case and O(n^2) in the worst case where n is the number of elements in the list.

Pros and Cons of Insertion Sort

Pros:

• Low overhead: Requires fewer comparisons and moves than algorithms such as bubble sort, which makes it more efficient in terms of item exchanges.
• Simplicity: insertion sort is one of the simplest sorting algorithms to implement and understand. This makes it suitable for teaching basic sorting concepts.

Cons:

• Inefficiency in large lists: As the list size increases, the performance of insertion sort decreases. Its quadratic complexity of O(n^2) in the worst case makes it inefficient for large lists.
• Non-scalable: Like other quadratic complexity algorithms, insertion sort is not scalable for large lists, as its execution time increases considerably with the size of the list.

What are Search Algorithms? 📊🔍

Search algorithms are methods that allow us to find the location of a specific element within a list of elements. Depending on the list, you will need to use one algorithm or another; for example, if the list has ordered elements, you can use a binary search algorithm, but if the list contains the elements in an unordered way this algorithm will not work. To search for an element in an unordered list you must use a linear search algorithm. These algorithms are two of the most relevant and well-known in programming, we will now see examples of these two algorithms.

Linear Search

Linear search algorithms, also known as sequential search, involve going through a list of items one by one until a specific item is found. This algorithm is very simple to implement in code but can be very inefficient depending on the length of the list and the location of the item. Below we will see a brief code example in Python.

1def linear_search(list, objective):
2 
3    for i in range(len(list)):
4        if list[i] == objective:
5            return i
6         
7    return -1
8
9
10list = [1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 15, 20, 27, 34, 39, 50]
11objective_number = 39
12result = linear_search(list, objective_number)
13
14if result != -1:
15    print(fThe number {objective_number} is located at position: {result}")
16else:
17    print(f"The number {objective_number} is NOT in the list")

code output:

1The Number 39 is located at position: 14

In this code example, we need to search for the number 39, to search for it in a linear way we simply run through the list with the help of a for loop structure, and then we ask if the current element is equal to the element we are looking for, if so, we return the index of the element and end the loop; but if the loop ends and no element is returned it means that the number we are looking for is not in the list so we return -1. This algorithm can be useful for traversing small lists or unordered lists but it is not efficient for traversing very long lists.

Pros and Cons of the Linear Search Algorithm

Pros:

• Simplicity: Linear search is one of the simplest and easiest search algorithms to implement. It only requires iterating through the list of items one by one until the target is found.
• flexibility: The linear search can be applied to any type of list, regardless of whether it is sorted or not.

Cons:

• Inefficiency in large lists: The main disadvantage of linear search is its inefficiency in large lists. Because it compares each item one by one, its execution time grows linearly with the size of the list.
• Not suitable for ordered lists: Although it can work on unordered lists, linear search is not efficient for ordered lists. In such cases, more efficient search algorithms, such as binary search, are preferable.

Binary Search

The binary search algorithm is a very efficient algorithm that applies only to ordered lists. It works by repeatedly dividing the list into two halves and comparing the target element with the middle element, this significantly reduces the number of comparisons needed.

Next, we will see a small example of binary search with Python.

1def binary_search(list, objective, start, end ):
2    if start > end:
3        return -1
4
5    center = (start + end) // 2
6    if list[center] == objeotive:
7        return center
8    elif list[center] < objeotive:
9        return binary_search(list, objective, center + 1, end)
10    else:
11        return binary_search(list, objective, start, center - 1)
12       
13# Example of use
14list = [1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 15, 20, 27, 34, 39, 50]
15objective = 27
16start_search = 0
17end_search = len(list) - 1
18
19result = binary_search(list, objective_number, start_search, end_search)
20
21if result != -1:
22    print(f"The number {objective_number} is in position: {result}.")
23else:
24    print(f"The number {objective_number} is NOT in the list")

code output:

1The number 27 is in position: 12.

In this example, we make use of a binary search algorithm to find the number 27 in a list of sorted elements, in order to find the element we are looking for, we can make use of a recursive function, in this function, the base case would be if the number in the list at position center is equal to the number we are looking for, we return the value of the variable center. This would be the index of the number, otherwise, we divide the list in two halves and make the recursive call until we find the number we are looking for, but if the number is not found in the list we return -1.

Pros and Cons of the Binary Search Algorithm

Pros:

• Efficiency of ordered lists: The main advantage of binary search is its efficiency on ordered lists. Its execution time is O(log n), which means that it decreases rapidly as the list size increases.
• Fewer comparisons: Compared to linear search, binary search performs fewer comparisons on average, making it faster to find the target.

Cons:

• Requires a sorted list: Binary search is only applicable to sorted lists. If the list is not sorted, an additional operation must be performed to sort the list before using binary search.
• Higher deployment complexity: Compared to linear search, binary search is more complex to implement due to its recursive nature.

Conclusion

In the programming world, sorting and searching algorithms are fundamental for data manipulation. Sorting algorithms allow us to organize data sets in ascending or descending order while searching algorithms allow us to locate information faster depending on the situation.

I hope this article has been useful for you to understand how search and sort algorithms work, remember to practice these algorithms as they are essential in the field of programming. You can check the 4Geeks Blog to learn more interesting content. Have fun in your learning process! 😉👍