SORTING ALGORITHMS
INTRODUCTION
Two sorting algorithms are studied in this paper: bubble sort and quicksort. Bubble sort is a comparison-type algorithm. It compares the elements of the array two at a time. It starts comparing from left to right of the array elements. The element with the greater value is placed on the right, and then compared to the next element. This is done until the largest element is placed at the end of the array. At this point, the largest sorted element is considered sorted, while the rest of the elements are unsorted. The algorithm is repeated for the remaining unsorted elements until only one (or the least-valued) element is left. The array is already sorted when this is reached.
Quicksort is a type of sorting algorithm that uses partitioning method in which each partition is independently sorted until all created partitions are sorted out. Quicksort uses the divide-and-conquer principle in order to work on smaller parts of the whole array first until the smaller parts combined would comprise the sorted whole array. A partitioning element, also called a pivot, is used to signify the partitions being created. The array elements will be sorted such that each element greater than the pivot is placed on the right of the pivot, while each element less than the pivot is placed on the left of the pivot. This sorting is done recursively until the partitions would contain single elements. Effectively, this algorithm is faster than sorting the whole array with brute force because the sorting method is applied to smaller parts at a time.
The Bubble sort algorithm guarantees an average implementation time proportional to the value N2, where N is the number of items in the array to be sorted. The Quicksort algorithm guarantees an average implementation time proportional to the value of NlogN. Thus, it is expected that the quicksort algorithm runs faster than the Bubble sort algorithm.
For simplicity, the arrays to be sorted are numerical arrays and the target output is an array in ascending order.
These two algorithms are designed, implemented, and tested in MATLAB. The design process is discussed in the DESIGN section. The RESULTS section shows the performance of the algorithms in terms of correctness or accuracy of the outputs, and execution time. The DISCUSSION section assesses the performance of the algorithms.
DESIGN
The algorithms will be implemented in MATLAB as user-defined functions. The bubblesort algorithm is embedded in the bubblesort() function; the quicksort algorithm is embedded in the quicksort() function. These functions accept a vector as input parameter; the output is a vector containing the sorted elements in ascending order.
The vector input for the algorithms will be randomly-generated. It would contain whole numbers (using the built-in function randi) for easier evaluation of the accuracy of the output results. The algorithms are tested for vectors of varying lengths. The tic and toc functions are used to measure the execution times of the algorithms. Then, using an additional for-loop, the average execution times are computed by running the algorithms 1000 times and then finding the average.
BUBBLESORT DESIGN
The Bubble sort algorithm is implemented by comparing two array elements at a time, starting from the leftmost elements. A for loop is used to traverse the array of elements. If the left element is greater than the right, the two elements are swapped; otherwise, no action is done. This set of actions is done using an if-statement; the swapping action is done using a buffer variable. Then, the array index is incremented to the next element. By the end of a single bubblesort function run, the element with the highest value is placed at the end of the array. Then, the remaining elements to the left of the highest value are bubblesorted until all the elements are sorted; this happens when the unsorted subarray has only 1 element. The bubblesort function is called again to sort the remaining unsorted elements.
QUICKSORT DESIGN
The Quicksort algorithm is implemented by assigning the first element of the array as the pivot. Then, the remaining array is scanned from left to right (using index i) and from right to left (using index j), subsequently. These scans are implemented using while loops. When the left-to-right scan detects an element greater than the pivot and/or the right-to-left scan detects an element less than the pivot, the two elements from which the two scans stopped are swapped; swapping is done by using an buffer variable. This scan and swap process is executed until the two scans meet (i = j). Then, the pivot is placed in the middle of these two subarrays, ensuring that the subarray to the left is less than the pivot and the subarray to the right is greater than the pivot. This whole process is done recursively on the subarrays until the subarray size reaches 1 element (using an if-statement to check if vector size is greater than 1). The final run of the quicksort function outputs the array in ascending order.
RESULTSBoth the Bubble Sort and the Quicksort algorithm successfully sorted the elements of the random arrays inputted into them. A sample run of the program with N = 10 shows the following results:
Original Array
x =
20 15 7 12 3 19 18 17 6 12
Bubble Sort Algorithm Result
bx =
3 6 7 12 12 15 17 18 19 20
Elapsed time is 0.000636 seconds.
Quick Sort Algorithm Result
qx =
3 6 7 12 12 15 17 18 19 20
Elapsed time is 0.000469 seconds.
As expected, the Quicksort algorithm has a faster execution time compared to the Bubble Sort algorithm. This is observed in all the test runs done for various array lengths. The average execution times for array size of N = 10 are:
tbubblesort=0.11533 ms, tquicksort=0.10438 msDISCUSSIONThe two algorithms yielded accurate results in terms of arranging the array elements properly in ascending order. Thus, the two algorithms appropriately satisfy their function as sorting algorithms. Although the quicksort function has more lines of code than the bubblesort function (45 > 19), the Quick sort algorithm runs significantly faster than the Bubble Sort algorithm. The Quick Sort algorithm is faster by a little more than 10%. This observation shows that lesser lines of code do not necessarily mean faster execution time.
The more critical factor that affects the execution time is how many times the function is being called on the average. Given the same input size, the bubblesort function is guaranteed to be called more often than the quicksort function simply because of the structure of the algorithms. The Quick sort algorithm divides the input into partitions and implements sorting on smaller partitions; the Bubble sort algorithm works on the whole input every time. Therefore, the Quick sort algorithm is the faster algorithm.
REFERENCES
Sedgewick, R & Wayne, K 2014, Quicksort, viewed 25 April 2016, <http://algs4.cs.princeton.edu/23quicksort/>.
1994, Bubble Sort, viewed 25 April 2016, <http://www-ee.eng.hawaii.edu/~tep/EE160/Book/chap10/subsection2.1.2.2.html>.
APPENDIX
clear
clc
% Main program
N = 10;
x = randi(20, 1, N)
% Quicksort
tic
qx = quicksort(x)
toc
% Mergesort
tic
mx = mergesort(x)
toc
% Test Average Time
t_bubble = zeros(1,1000);
t_quick = zeros(1,1000);
for i = 1:1000
x = randi(20, 1, N);
% Bubble Sort Algorithm
tic;
bx = bubblesort(x);
t_bubble(i) = toc;
% Quicksort Algorithm
tic;
qx = quicksort(x);
t_quick(i) = toc;
end
% Average times
mean(t_bubble)
mean(t_quick)
bubblesort.m
% This contains the Bubble sort Algorithm
function x = bubblesort(x)
n = length(x);
if n == 1
return
end
buffer = [];
for i = 1:n-1
if x(i) > x(i+1)
% Swap the Elements
buffer = x(i+1);
x(i+1) = x(i);
x(i) = buffer;
end
end
% The last element is considered sorted.
% Bubble Sort the unsorted elements
x = [bubblesort(x(1:n-1)) x(n)];
end
quicksort.m
% This contains the Quicksort Algorithm
function x = quicksort(x)
l = length(x);
if l == 1
return
end
% Let the first element be the partitioning element
a = x(1);
i = 2; j = l;
buffer = [];
while i < j
% Scan Left to Right
while x(i) < a && i < j
i = i+1;
end
% Scan Right to Left
while x(j) >= a && j > i
j = j-1;
end
% Swap Elements
if i < j
buffer = x(i);
x(i) = x(j);
x(j) = buffer;
end
end
% Place Pivot on the middle of the Vector
if x(i) < a
buffer = x(i);
x(i) = a;
x(1) = buffer;
elseif x(i) > a
buffer = x(i-1);
x(i-1) = a;
x(1) = buffer;
i = i-1;
end
% If subarray length is greater than 1, quicksort the subarray
if i > 1
x(1:i-1) = quicksort(x(1:i-1));
end
if i < l
x(i+1:l) = quicksort(x(i+1:l));
end
end
