Bubble Sort using MATLAB | MATLAB Tutorial
- It is one of the simplest sorting algorithm.
- It is a comparison based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.
- The main advantage of Bubble Sort is the simplicity of the algorithm. Space complexity for Bubble Sort is O(1), because only single additional memory space is required for temp variable.
- Best-case Time Complexity will be O(n), it is when the list is already sorted.
We take an unsorted array for our example.
We compare first two elements to check which one is greater. Here we can see that 15 is greater than 11 hence we will swap those elements. If the adjacent element is larger than there is no need to swap.
Next, 15 and 6 are compared and as we can see that the 15 is greater than 6 we need to swap them.
Similarly, doing the further iterations.
At the end of each pass the greatest value in the observed array is placed into its correct position. In this example the element 15 is placed into its correct position.
Now we just perform sorting on the first four elements as we know that last element is already sorted.
As we can see the elements 11 and 15 are placed at their correct position hence no need to apply sorting on them. So we will now perform sorting on the remaining elements of the array.Pass-3:
- Hence Bubble sort requires n – 1 pass to sort an array of n elements.
- In each pass we have n – k comparisons, where n is the number of elements and k is the pass number.
- So, 1st pass requires n – 1 comparisons, kth pass requires n – k comparisons and the last pass requires 1 comparison.
</pre> function n = bubbleSort(A) n=length(A); % making (n-1) passes for j=1:1:n-1 % comparing each number with the next and swapping for i=1:1:n-1 if A(i)>A(i+1); % temp is a variable where the numbers are kept % temporarily for the switch temp=A(i); A(i)=A(i+1); A(i+1)=temp; end end end <pre>
i=1; k = 1:500:10000; val = zeros(1,length(j)); for j = 1:500:10000 %array size R = randn([1 j]); %generating array of size j containing random elements tic; %starting the timer P = bubbleSort(R);%calling the bubble sort function val(i) =toc; %stopping the timer and creating an array of time difference i=i+1; end plot(k,val); %plotting array size vs time taken for sorting using bubble sort algorithm grid on; xlabel('array length'); ylabel('Time Taken in seconds'); title('Analysis Plot'); legend('bubble Sort')
- As we can see that the time taken by the algorithm increases with the power of 2 with the increase in the size of the array. The above quadratic equation provides the best fit for the above plot which consists of term with degree 2.
- From this analysis we can say that the time complexity of the bubble sort is O (n2).
- This algorithm is not suitable for large data sets as its average and worst case time complexity is O (n2).
- Best Case: O (n)
- Average Case: O (n2)
- Worst Case: O (n2)