MATLAB: Array sort

Introduction:

Under certain circumstances, we might need to arrange values that we collect into a certain arrangement. This is known as sorting. Sorting not only identifies the important values but it also allows these values to be arranged according to priority.

Recognizing this importance, I'd like to discuss on a sorting algorithm which I came across while viewing the Introduction to Algorithms course by MITOpenCourseWare on iTunes and how I implemented it on MATLAB

Figure I. Pseudo code for insertion sort

The first thing we need now is a set of inputs to analyze the pseudo code. Let's do this by using the following code.

x = [5 2 3 9 1 8 6]

Line-by-line analysis:

Using the values of x above to analyze, I'm going to break down the code into individual lines

Figure 1. Line-by-line analysis

1. A For loop is created by assigning variable j from 2 to n; This is because, if you look at line 3, we are going to assign variable i with j - 1. This in turn results in a value of 1 assigned to i.
2. For each iteration, assign a temporary variable ( key  used here) with the value of A[j]. On the first iteration, when j = 2, we see that A[2] = 2.
3. I've covered this at 1. so I'll skip it here.
4. Here, a While loop is created to check if i > 0 ( this is needed since arrays do not start with 0 in MATLAB) and if A[i] > key. Using our example in 2, When j = 2 , i = 1, which is > 0 while A[1] = 5 which is > key (key = 2). So the While loop returns a true and its instructions inside are executed.
5. In this line, we assign A[i+1] with A[i] so that we can swap the smaller value at the current position with the larger value at the previous position. Since, i =  1, A[i] = 5, and i + 1 = 2, A[i + 1] = 2, then, A[i + 1] = A[i] gives A[2] = 5.
6. This operation is important to ensure that we reset the value of i as we want to replace the value in the previous position. Using the example again, current value of i = 2 , the previous position is i =  1 (see where we're going?) so i - 1 gives i = 1
7. Here, we replace value in the previous position with the value in key. A[1] = 2
8. Finally, after the 1st iteration, we will get x = [2 5 3 9 1 8 6].

MATLAB code implementation:

Figure 2. MATLAB code (left), pseudo code (right)

Analyzing each line again, I've replaced the pseudo code with its corresponding MATLAB commands.

1. Here, instead of using n, i used length(x) (where x is my input to process). This will allow me to determine the total number of iterations required based on the size of the input.
2. Here, I defined the temporary variable as temp.
3. Skipping this line since nothing changed
4. Here, I used the scalar logical operator && to replace and
5. Skipping ines 5, 6 and 7 since they are all pretty self explanatory.

In summary, after understanding the pseudo code, creating it using a certain coding language is much easier since the idea is already there.

Time consumption:

Using the tic and toc functions in MATLAB, I can determine the time taken for the algorithm to sort through a certain array. Below are some examples.

For x = [5 2 3 9 1 8 6], it takes 0.011524 seconds
For x = [9 8 7 6 5 4 3 2 1], it takes 0.001560 seconds
For x = [12 9 3 15 8 2 1 100 21 0], it takes 0.007123 seconds

Using x = 0 + rand(1,50)*1000; to generate a [1x50] array of values ranging from 0 to 1000 and then running the algorithm, it takes only 0.004517 seconds to sort the array into a perfect order!

Figure 3. Sorting a random [1x50] array.