Selection Sort using MATLAB | MATLAB Tutorial

Selection Sort using MATLAB | MATLAB Tutorial

Selection Sort

  • 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.

 

Pseudo Code:
SELECTION-SORT (A)

  1. for j ← 1 to n-1
  2. smallest ← j
  3.  for i ← j + 1 to n
  4. if A[ i ] < A[ smallest ]
  5. smallest ← i
  6.   Exchange A[ j ] ↔ A[ smallest ]

 

Example:

We want to sort the following array:

  1. 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.

  1. The next smallest element in the array is 2 and it is exchanged at the 2nd position.

  1. 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.

  1. Element 5 is set to its correct sorted position.

5.

6.

  1. All the elements are sorted

Matlab Code:

Function:


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

Test Code:


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.

 

Simulation Results:

 

  • 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).

 

Time Complexity:

  • Worst Case Time Complexity: O (n2)
  • Best Case Time Complexity: O (n2)
  • Average Time Complexity: O (n2)
  • Space Complexity: O (1)


Anushi is pursuing graduation degree in Electronics & Communication from HBTI, Kanpur (Now HBTU). She has a keen interest towards Competitive Programming & loves to solve coding Challenges.