Sorting Algorithms

This assignment focuses on implementing and measuring the performance of different sorting algorithms in MATLAB. The primary algorithms discussed are Selection sort and Bubble sort, both performed in ascending order. The time complexity of the algorithms is also analyzed.

Running head: SORTING ALGORITHMS
SORTING ALGORITHMS
Name of the Student
Name of the University
Author Note

1SORTING ALGORITHMS
Introduction:
In this particular assignment the objective is to implement different sorting algorithms in
MATLAB and measure their performances. Sorting is basically arranging a given dataset or
vector in either ascending or descending order. This can be performed by different ways or by
different algorithms. The algorithms are Selection sort, Bubble Sort, Insertion sort, Merge
sort, Quick sort, Heap sort, Counting sort, Radix sort, Bucket sort, Shell short, TimSort,
Comb Sort, Pigeonhole Sort, Cycle Sort, Cocktail Sort, Bitonic Sort, Pancake sorting, Gnome
Sort, Sleep Sort, Stooge Sort and more sorting techniques based on place of application are
being developed day by day. In this assignment the focus is on the primary two algorithms
which are Selection sort and Bubble sort which are implemented in MATLAB. Both sorting
are performed in ascending manner i.e. the display of the sorted data is in ascending order.
Selection sort Algorithm:
In this method first the minimum of the entire data row of size (n*1) and its position is
calculated. Then the minimum is swapped with the leftmost data point. Then this process is
repeated for data row of (n-1)*1 size i.e. process is continued with entire data except leaving
the leftmost data point. Finally, this iterative process ends with operation on the two right
most data points and data is sorted from left to right in ascending order.
MATLAB function for Selection sort:
function sorted = selectionsort(a)
%%%
% Performs sorting by Selection sorting algorithm on the given row vector.
% Input = User input array

2SORTING ALGORITHMS
% Output = Output array in ascending order
%%%
%a = [-5 1 4 -2 8 1 6 9 20 19]; % input vector of digits
sorted = a; % initializing sorted vector with a
for i=1:length(a)-1
[m,ipos] = min(sorted(i:length(a))); % extracting minimum and minimum index position
minipos = ipos + i-1; % adjusting minimum index position w.r.t vector A
%%% swapping betweeen found minimum and the number in ith position
%------
c = sorted(i); %
sorted(i) = sorted(minipos);
sorted(minipos) = c;
%------
end
end
Output with sample run:
a = [-5 1 4 -2 8 1 6 9 20 19];
>> sorted = selectionsort(a)
sorted =
-5 -2 1 1 4 6 8 9 19 20

3SORTING ALGORITHMS
Bubble Sort Algorithm:
function sorted = bubblesort(a)
% Performs sorting by Bubble sorting algorithm on the given row vector.
% Input = User input array
% Output = Output array in ascending order
sorted = a; % % initializing sorted vector with a
for j=1:length(sorted)-1 % passing length - 1 times to check all the digits are sorted
for i=1:length(sorted)-1 % as i+1 = length of array
if sorted(i) > sorted(i+1)
% swapping the minimum of two elements in the left
c = sorted(i+1);
sorted(i+1) = sorted(i);
sorted(i) = c;
end
end
end
Sample run with Output:
a = [-5 1 4 -2 8 1 6 9 20 19];
>> sorted = bubblesort(a)
sorted =

4SORTING ALGORITHMS
-5 -2 1 1 4 6 8 9 19 20
Time complexity testing MATLAB code:
%%% Measuring performance of two algorithms
for i=100:1:500 % performing sorting for size = 100 to 500 in steps of 1
a = randi([-100 100],1,i); % creating random vector with increasing length in every step
g = @() selectionsort(a); % calling selection sort function
f = @() bubblesort(a); % calling bubble sort function
ts(i) = timeit(g); % computing time to run the algorithm with specified length of array
tb(i) = timeit(f);
end
%%% Displaying performance of both algorithm in single graph
n = 100:1:500;
ts = nonzeros(ts)';
tb = nonzeros(tb)';
plot(n,ts,n,tb)
grid on

5SORTING ALGORITHMS
xlabel('Number of terms in vector')
ylabel('Algorithm Sorting time in secs')
title('Time complexity graph')
legend('Selection sort algorithm','Bubble sort algorithm')
Output:
100 150 200 250 300 350 400 450 500
Number of terms in vector
0
0.5
1
1.5
2
2.5
Algorithm Sorting time in secs
10-3 Time complexity graph
Selection sort algorithm
Bubble sort algorithm
Hence, it can be seen from the time complexity curve that the Bubble sort algorithm require
less time or more efficient that selection sort for small n or number of data points and it is
less efficient than selection sort in case of large n or number of data points.

6SORTING ALGORITHMS