Bubble sort
#Bubble sort code#
#Bubble sort code#
Currently, our code iterates through the entire array each time. If you look back at our array visualization, the blue values in the array do not need to be iterated through because we have already sorted them. That’s it! We have built our bubble sort function! But…we can make it slightly better. Our function then returns the sorted array. If we have performed a swap, we know that our array was not sorted so we set our sorted flag to False: def bubbleSort(array): sorted = False while not sorted: sorted = True for i in range(len(array) - 1): if array > array: array, array = array, array sorted = False return arrayįinally, once our array is completely sorted, our flag will be true and we exit the while loop. Remember, we were checking if our current value is greater than the value to its right and swapping if that is the case. The reason is that we can’t look to the right of the last value in the array (there’s nothing there). Note that we are iterating until len(array) - 1. We then start our for loop to iterate through our array: def bubbleSort(array): sorted = False while not sorted: sorted = True for i in range(len(array) - 1): We are going to start our while loop and tentatively set our sorted flag to True. So while our array is not sorted, we need to sort it. Initially, we assume our input array is not sorted so we have a flag sorted set to False. We define our bubbleSort function and it takes in an array of integers. We are not allocating any extra memory to perform our sort so our space complexity is O(1). We still need to iterate through that array once to check that its sorted, our best case time complexity is O(n).Īs mentioned earlier, bubble sort performs its swaps in-place. In the best case, we’re given a sorted array to sort. More specifically, Bubble sort has a time complexity of O(n²) in the worst case. You might be thinking - that was extremely tedious. This means we are done! Time and Space Complexity 2 cannot be swapped with anything so our swaps are zero for this round.