As we see previously algorithm is well defined step by step finite number of procedures to solve a problem. To solve a problem means it doesn’t mean an instance or some instances of a certain problem.

An algorithm has to be **correct **to be solve the problem, the * correctness *of an algorithm is rewarded when the algorithm produces the correct expected output for all instances.

We have already using various types of algorithms

- Searching algorithms
- Sorting algorithms
- Inserting algorithms
- Deleting algorithm
- Updating algorithms

Each of these algorithm types have plenty of possible algorithms. Because a problem can be solved in many different ways. For example Sorting algorithm has many approaches like selection sort, Insertion sort, and bubble sort so on. Each of those algorithm have several advantages in certain scenarios. Which makes the particular algorithm **efficient **for that particular problem. To choose an algorithm we can do two types of analysis.

**Priori Analysis:**Theoretical analysis of an algorithm. Here efficiency of an algorithm is calculated theoretically by assuming computing power and all other physical factors have no effect on the implementation**Posterior Analysis:**Practical analysis of an algorithm. A particular algorithm is written in a programming language and implemented into the system and according to the performance statistic the efficiency is calculated.

This analysis basically checks two major complexity of an algorithm to measure its efficiency.

**Time**required for number of key operations**Space**(memory) require for the implementation and execution. Calculated by the sum of(variables, constants and program size) part space and__fixed__(memory allocation scheme, recursion stacks and etc.) part space.__variable__

**Practical – 02**

As we seen in lecture 02 there can be many ways to solve a particular problem. Which means there can be many types algorithm for particular problem. Previously we have seen an algorithm called insertion sort to sort given numbers.

There is another algorithm called **Selection sort**

1. Assume the first element as sorted (the smallest among given)

2. Then find if there is any other smallest (among the numbers except than first element) value than the first if exist then swap it with first element.

3. Then pick the second element of the list and find if there are any smallest value than that among the 3^{rd} – last element of the list. If exist again swap else move and take next element as smallest now and go on with the search.

**Task: Write a java program to sort a given array using Selection Sort.**

**SelectionSort.java**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class SelectionSort { public static void main(String [] args) { int [] num = {15,2,8,4,21,3,10,14}; int index = 0, value = 0; int n = 0, m = 1; while (n < num.length) { value = num[n]; m = n+1; while (m < num.length) { if (num[m] < value) { value = num[m]; index = m; } m++; } if (index != n) { num[index] = num[n]; num[n] = value; } n++; /*for (int i = 0; i < num.length; i++) { System.out.print(num[i]+", "); } System.out.println();*/ //To view each step of sort uncommand this } for (int i = 0; i < num.length; i++) { System.out.print(num[i]+", "); } } } |

**SelectionSort2.java**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
public class SelectionSort2 { public static void main(String [] args) { int [] num = {15,2,8,4,21,3,10,14}; int index = 0, value = 0; for (int i = 0; i < num.length; i++) { value = num[i]; for(int j = i+1; j < num.length; j++) { if (num[j] < value) { value = num[j]; index = j; } } if (index != i) { num[index] = num[i]; num[i] = value; } /*for (int k = 0; k < num.length; k++) { System.out.print(num[k]+", "); } System.out.println(); */ //To view each step of sort uncommand this } for (int i = 0; i < num.length; i++) { System.out.print(num[i]+", "); } } } |

**Mathanraj Sharma**

University of Jaffna