Bubble sort is a comparison-based sorting algorithm where adjacent elements of the array are compared repeatedly, and they are swapped if they are not in order.
Bubble sort runs on an array of N elements for (N-1) times to be exact, it sorts for (N-1) times of passes to sort the array. Ex: If an array has 4 elements, it can be sorted by (4–1=3) passes.
By comparing (N-1) elements in (N-1) passes, one element of array is placed in the correct position. On completion of the first pass in ascending order sort, the first maximum (or) the greatest number in the array is found, and it is placed at (N-1) index. Similarly the second maximum element is found after completion of 2nd pass at index (N-2). And on completion of third pass, the third maximum element is found and it is located at (N-3) index. Thus it goes on for (N-1) passes.
Example:
Let us understand this with an example. Consider an array arr={15,16,6,8,5}. Here N=5 because this array length is 5. On performing bubble sort on this array, the number of passes would be (N-1) = 5–1 = 4.
In each pass, traverse through all elements of array and compare it with its next element in the array. If the next element is less than current element, swap these two elements.
1st iteration:
2nd iteration: Again the comparison is done from index 0 till N-2.
3rd iteration: Again the comparison is done from index 0 till N-2.
4th iteration: Again the comparison is done from index 0 till N-2.
Now 4 iterations have been done on this array and swapped with wrong placements in array for an array of size N=5. Thus by (N-1) iterations, an array of size N can be sorted.
Code snippet of bubble sort:
Time complexity: O(N²) for best, average and worst case complexity.
Space complexity: O(1) because no extra data structure is used. Only a single memory space is required when swapping.
Sorting in-place: Yes, because no extra space or data structure is used. Swapping is done within the cells of same array.
Advantages of Bubble sort:
Easy to understand
Few lines of code
Disadvantages of Bubble sort:
- Requires more time
Bubble sort is a basic sorting algorithm to know. There are other time efficient sorting algorithms like insertion sort, merge sort, quick sort. etc.
Thanks for reading!