Many sorting algorithms have been created to date, each of which solves a very common problem – sorting data. Bubble sorting is one of the simplest, but also the least efficient, algorithms that are used to sort small arrays.
Sorting Algorithms in Interviews
Sorting algorithms are quite numerous, and you can hardly meet a programmer who can write an implementation of at least half of them from memory. In fact, programmers simply google the necessary implementation. Of course, they have an idea of how they work, because they have looked at several algorithms at one time, such as bubble sorting.
and other programming languages have built-in functions that do sorting quickly and efficiently. Interviews ask about sorting algorithms, but this does not mean that the future employee is required to write their implementation or come up with his or her own. The employer requires the following from a specialist:
- Be able to classify sorting algorithms.
- Know the advantages and disadvantages of popular algorithms to understand when each is better to use.
- Understand what the complexity of an algorithm is and how to use it to determine if it is suitable for a given problem.
Bubble sorting is mostly used in training projects. In real practice, it is replaced by more efficient algorithms, but bubble sorting is the basis of some of them. Ingeneral, the bubble sorting algorithm is as follows:
- Compare the current element with the next.
- If the next element is smaller/higher than the current one, swap them.
- If the array is sorted, finish the algorithm, otherwise go to step 1.
The algorithm uses two loops: a main loop and a nested one. As a result of one pass of the nested loop, the largest element is placed at the end of the array, and the smallest one is moved one position closer to the beginning. The outer loop in the worst case makes N (number of elements) – 1 passes, i.e. the inner loop is executed N-1 times. Thus, each pass makes a series of element swaps, so that the largest element moves to the end of the array before the element that moved there in the last iteration. The process takes place until the array is sorted.
The algorithm’s complexity allows us to give it an estimate of the execution time, that is, it determines its efficiency. The complexity can be expressed in different ways, but most often the asymptotic complexity is used, which determines its efficiency when the input data tends to infinity. The exact execution time of the algorithm is not considered, because it depends too many factors: processor power, type of array data, programming language used.
The bubble sorting algorithm has a complexity of
n is the number of array elements. From the formula, you can see that the complexity of bubble sorting is quadratic to the number of elements to be sorted. This means that it is inefficient when dealing with large arrays of data. You should understand that the asymptotic function cannot be used to accurately calculate the algorithm’s running time. For example, the sequence “6 5 4 3 2 1” is given. To sort it, you will have to make the maximum number of passes. This case is called the worst case. If the sequence “3 1 2 4 5” is given, the number of passes will be minimal, so the sorting will go much faster. If you are given an array that is already sorted, the sorting algorithm does not need to make any passes at all. This is called the best case.
It is better to put bubble sorting into a separate function. The function code will look like this:
def bSort(array): # determine the length of the array length = len(array) #Internal loop, number of passes N-1 for i in range(length): #Internal loop, N-i-1 passes for j in range(0, length-i-1): #Swap the elements if array[j] > array[j+1]: temp = array[j] array[j] = array[j+1] array[j+1] = temp
You can swap values of neighboring elements in one line using plural assignment, then code will look like this
array[j], array[j+1] = array[j+1], array[j]
Multiple assignment is one of the useful features of Python that allows you to avoid introducing an extra variable to swap values of two or more variables. To demonstrate how the bubble sort function works, let’s create a list to be sorted:
a = [3, 1, 6, 4]
Sort it using our function and display it:
bSort(a) print(a) # print [1, 3, 4, 6]
The bubble method is much less efficient than other algorithms, but it has a simple and straightforward implementation, so it is often used for training purposes. In addition, bubble sorting can be used to handle small data sets. In fact, instead of writing sorting algorithms themselves, Python programmers use standard language functions and methods such as
sort(). These functions are fine-tuned and work quickly and efficiently. Knowing the specifics of sorting algorithms, their complexity, and implementation principles in general terms will be useful to any programmer who wants to interview and become a Python developer.