__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

*on iTunes and how I implemented it on MATLAB*

**MITOpenCourseWare**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 |

- A For loop is created by assigning variable
from 2 to n; This is because, if you look at line 3, we are going to assign variable*j***i**with**j**- 1*.*This in turn results in a value of 1 assigned to i. - 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. - I've covered this at 1. so I'll skip it here.
- Here, a While loop is created to check if
> 0 ( this is needed since arrays do not start with 0 in MATLAB) and if A[*i**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. - In this line, we assign A[
+1] with A[*i*] so that we can swap the smaller value at the*i***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. - 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 - Here, we replace value in the previous position with the value in
*key*. A[1] = 2 - 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) |

- 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. - Here, I defined the temporary variable as
*temp*. - Skipping this line since nothing changed
- Here, I used the scalar logical operator
*&&*to replace*and* - 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.

Using the

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!

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

## No comments:

## Post a Comment