Algorithm continues…

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.

correct_algorithm_is_good_solution

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.

  1. 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
  2. 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 fixed (variables, constants and program size) part space and variable (memory allocation scheme, recursion stacks and etc.) part space.

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)

sorting_elements

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.

swapping_elements

3. Then pick the second element of the list and find if there are any smallest value than that among the 3rd – 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

SelectionSort2.java

Mathanraj Sharma
University of Jaffna

Add Comment