Insertion Sort Using Logical Operators
So i have stumbled across the following insertion sort algorithm for Matlab which works as it should:
function sorted = insertion_sort(array)
% Insertion sort in ascending order
% @input - Array to be sorted
% @output - Sorted Array
% Usage:
% input_array = [ 9 8 7 6 5 4 3 2 1 0];
% output_array = insertion_sort(input_array);
if(size(array,1)>1) error('Input must be a 1xN vector');
end
if(isempty(array)) error('Input should not be empty');
end
disp(['Array to be sorted: ' num2str(array)]);
n = length(array);
for i = 2:n d = i; while((d > 1) && (array(d) < array(d-1))) temp = array(d); array(d) = array(d-1); array(d-1) = temp; d = d-1; end
end
sorted = array;
disp(['Sorted Array: ' num2str(array)]);
end( taken from )
My question is; how would one go about using logical vectors and operators to achieve the same algorithm? I feel as this would make the program more efficient as it would eliminate the while loop, whilst also being more elegant.
$\endgroup$1 Answer
$\begingroup$Do you understand what insertion sorting is doing?
It is making sure each item at place $i$, for each $i$ from $2$ to $n$ (the length of the array), is inserted into properly-ordered place in the previously sorted list before it, and all items greater than it are moved forwards, by swapping places one-by-one down the list as needed.
The two loops are necessary to implement this search and swap algorithm.
The while loop is moving the $i$ iterator from second to last place in the array. In each step through the while-loop, the for-loop is moving the $d$ iterator from $i$ down towards the start of the array: swapping items at places $d$ and $d-1$ if they are out of order, but breaking out of the for-loop if they are in order.
$\endgroup$
