Selection Sort using MATLAB | MATLAB Tutorial
- It is conceptually the simplest sorting algorithm.
- This algorithm finds the smallest element in the array and exchanges it with the element in the first position, then finds the second smallest element and exchange it with the element in the second position, and iteratively performs this operation until the complete array is sorted.
- for j ← 1 to n-1
- smallest ← j
- for i ← j + 1 to n
- if A[ i ] < A[ smallest ]
- smallest ← i
- Exchange A[ j ] ↔ A[ smallest ]
We want to sort the following array:
- The smallest element in the array is 1. So it is allocated to the 1st position in the array. The element at 1st place is exchanged at the place where 1 is located.
After each iteration exactly one element of the array is allocated to its correct sorted position.
- The next smallest element in the array is 2 and it is exchanged at the 2nd position.
- The next smallest element in the array is 4. As we can see that is already present at the correct sorted position so no exchanging would take place.
- Element 5 is set to its correct sorted position.
- All the elements are sorted
function list = selectionSort(list) listSize = numel(list); for i = (1:listSize-1) minElem = list(i); minIndex = i; for j = (i:listSize) if list(j) minElem = list(j); minIndex = j; end end if i ~= minIndex list([minIndex i]) = list([i minIndex]); end end end
i=1; k = 1:100:10000; val = zeros(1,length(j)); for j = 1:100:10000; %array size R = randn([1 j]); %generating array of size j containing random elements tic; P = selectionSort(R);%calling the selection 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 selection sort algorithm grid on; xlabel('array length'); ylabel('Time Taken in seconds'); title('Analysis Plot'); legend('Selection Sort')
- We want to perform time complexity analysis for this algorithm. For this we run this algorithm for array of different sizes and measure the time required for each of these sizes and then plot the result of array size vs. time taken.
- We obtain the above results which clearly shows that as the size of the array increases the time taken by the algorithm to perform sorting also increases which is quite intuitive.
- Now, we try to perform curve fitting operation on the above result to know what kind of relation is there between the array size and the time taken by the algorithm to perform sorting.
- As it can be observed from the above results that the equation of the curve which fits is quadratic in nature. This the time complexity of the selection sorting can be inferred as O (n2).
- Worst Case Time Complexity: O (n2)
- Best Case Time Complexity: O (n2)
- Average Time Complexity: O (n2)
- Space Complexity: O (1)