# Introduction to Algorithms in MATLAB | MATLAB Tutorial

**by** Ratnesh Shah

**Algorithm:**

- An algorithm is any well-deﬁned computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
- An algorithm is thus a sequence of computational steps that transform the input into the output. We can also view an algorithm as a tool for solving a well-speciﬁed computational problem.

**Analyzing Algorithms:**

- Analyzing an algorithm has come to mean predicting the resources that the algorithm requires.
- Resources such as
**memory, communication bandwidth, or computer hardware**are of primary concern, but most often it is**computational time**that we want to measure. - Generally, by analyzing several algorithms for a problem, we can identify a most efﬁcient one.

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed.

Time Taken by an algorithm is measured in terms of Big-O Notation.

The longest running time for any input which provides an upper bound on the running time is known as worst case running time.

**Big-O Notation:**

- When solving a computer science problem there will usually be more than just one solution. These solutions will often be in the form of different algorithms, and you will generally want to compare the algorithms to see which one is more efficient.
- Big O analysis gives us some basis for measuring the efficiency of an algorithm.
- We use big-O notation to asymptotically bind the growth of a running time to within constant factors above and below.

Img1:Big-O Notation

**Example: Cost Times**

i=1; c1 1

sum=0; c2 1

while(i<=n){ c3 n+1

j=1; c4 n

while(j<=n){ c5 n*(n+1)

sum= sum+i; c6 n*n

j=j+1; c7 n*n

}

i=i+1; c8 n

}

**Total cost: c1 + c2 + (n+1)*c3 + n*c4 + n*(n+1)*c5 + n*n*c6 + n*n*c7 + n*c8**

The highest growth rate is the one with the largest exponent as a function of n which is n^{2} which provides an upper bound on the running time.

Thus, the time required for this algorithm is proportional to n^{2}.

**What is sorting Algorithm?**

- Sorting means to arrange data in a definite format.
- Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.
- With the help of data searching can be optimized to a very high level, if data is stored in a sorted manner.
- Sorting is also used to represent data in more readable formats.
- There are large number of sorting algorithms.

- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Shell Sort
- Radix Sort
- Quick Sort

- In the coming tutorials we are going to analyse some of these algorithms using MATLAB and compare them.

## Terminologies:

**In-Place Sorting:**

Sorting algorithms may require some additional space for comparison and storage for few variables or data elements.

But these In-place sorting type of algorithms do not require any extra space and sorting is said to happen in-place, like in the array itself.

Bubble sort is an example of insertion sorting.

**Not In-Place Sorting:**

Some sorting algorithms, the program requires space which is more than or equal to the elements being sorted.

Sorting which uses equal or more space is called not-in-place sorting.

Merge-sort is an example of not-in-place sorting.

**Increasing Order:**

A sequence of values is said to be in increasing order, if the successive element is greater than the previous one.

For example, 2, 3, 7, 8, 9 are in increasing order, as every next element is greater than the previous element.

## Applications of Sorting Algorithm:

Following are some of the examples of sorting in real-life scenarios −

**Telephone Directory **− the telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily.

Img2: Telephone Directory

**Dictionary** − the dictionary stores words in an alphabetical order so that searching of any word becomes easy.

Img3: Dictionary Search