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.
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).
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.
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.
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 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.
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.
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! 😉👍