KC Tech

Sorting In one of the previous posts, we have discussed ' Binary search ' in some detail. One of the requirements to run a Binary Search is that the data in our Array is sorted. In this blog, let's take a look at different ways to sort the lists and find the best way to sort the list. 1. Bubble sort Figure [1] Bubble Sort Here's the code for bubble sorting a simple array: def bubble_sort(array):     n = len(array)     for i in range(n):         already_sorted = True         for j in range(n-i-1):             if array[j] > array[j+1]:                 array[j], array[j+1] = array[j+1], array[j]             already_sorted = False         if already_sorted:             break     return array print(bubble_sort([2,3,9,8,7,1])) Since the bubble sort algorithm has 2 for loops, it has a time complexity of O(n^2). Figure [2] Time Complexities Graph Based off the graph in Figure 2, we can see that the sorting algorithm has a less desirable time complexity. 2. Insertion sort Fig

Binary Search Figure [1] Binary Seach Algorithm applied to a descending order list Let's say we have an ascending-order sorted list of numbers as given below: number_list = [6, 12, 24, 39, 42, 43, 45, 89] Say we were tasked with finding whether a particular element was in the list or not, the simplest way that would occur to us is to use a 'for' loop.  target = 39 for num in number_list:   if num == target:     print(f"{num} is in number_list.") This works but say, we have a huge list of about a million or even a billion values, what would be the worst-case time complexity of such an operation? It could be that the target is the last item in the list, which results in the time complexity being O(n). So, let's think about a better way of solving this problem. Now, we know that the list is ascending-order sorted which means if we check a random number in the list and the number is bigger than our target , we can be sure that our target if it is in, will be to th