DAA SIMULATOR

Introduction

·       Used programming language: Java

·       Algorithms:

o    Insertion sort algorithm

o   Selection sort algorithm

·       Insertion sort

            

     One of the simplest methods to sort an array is an insertion sort. An example of an insertion sort occurs in everyday life while playing cards. To sort the cards in your hand you extract a card, shift the remaining cards, and then insert the extracted card in the correct place. This process is repeated until all the cards are in the correct sequence. Following are some of the important characteristics of Insertion Sort.

1.      It has one of the simplest implementation

2.      It is efficient for smaller data sets, but very inefficient for larger lists.

3.      Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

4.      It is better than Selection Sort and Bubble Sort algorithms

Insertion Sort Algorithm

·       Analyzing Insertion Sort

·         Best Case ƒ If A is sorted: O(n) comparisons

·         Worst Case ƒ If A is reversed sorted: O(n2) comparisons

·         Average Case ƒ If A is randomly sorted: O(n2) comparisons

·    Selection Sort

             The idea of selection sort is rather simple: we repeatedly find the next largest (or smallest) element in the array and move it to its final position in the sorted array. Assume that  wish to sort the array in increasing order, i.e. the smallest element at the beginning of the array and the largest element at the end. We begin by selecting the largest element and moving it to the highest index position. We can do this by swapping the element at the highest index and the largest element. We then reduce the effective size of the array by one element and repeat the process on the smaller (sub) array.

·       Analyzing Selection Sort

Worst Case Time Complexity: O (n2)

Best Case Time Complexity: O (n2)

Average Time Complexity: O (n2)