Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.                                                                                              

Ans.

Algorithm for the Selection Sort is as follows

SELECTION (A, N)

This algorithm sorts the given array A with N elements

1.  Repeat steps 2  & 3 for K = 1,2........N-1

2.  Call MIN (A,K, N, LOC)

3.  [Interchange A[K] and A[LOC].]

Set TEMP : = A[K], A[K]:=A[LOC] and A[LOC]: = TEMP, [END of Step 1 loop]

4.  EXIT

MIN (A, K, N, LOC)

An array A is in memory. This procedure finds the location LOC of the smallest element among A[K], A[K+1]...........A[N],

1.  Set MIN : =A[K] and LOC:=K [Initialize pointer]

2.  Repeat for J= K+1, K+2, .....N;

If MIN > A[J], then : set MIN: = A[J] and LOC:=J [End of loop]

3.  Return

The complexities of Selection sort are given below

 

Worst Case	Average Case	Best Case
O(n2)	O(n2)	O(n2)

 

So if the list is already sorted the it is the best case, then also the complexity of algorithm is O(n2). Therefore, there is no change in behaviors of selection sort if the list is already sorted.

Posted Date: 7/12/2012 8:46:41 AM | Location : United States

Ask an Expert

Related Discussions:- Algorithm for the selection sort, Assignment Help, Ask Question on Algorithm for the selection sort, Get Answer, Expert's Help, Algorithm for the selection sort Discussions

Write discussion on Algorithm for the selection sort
Your posts are moderated

Write your message here..

Related Questions

Explain b tree (binary tree), B Tree Unlike a binary-tree, every node o... B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

Demonstration of polynomial using linked list, Demonstration of Polynomial ... Demonstration of Polynomial using Linked List # include # include Struct link { Char sign; intcoef; int expo; struct link *next; }; Typedefstruct link

Stack, Explain in detail the algorithmic implementation of multiple stacks.... Explain in detail the algorithmic implementation of multiple stacks.

#, if two relations R and S are joined, then the non matching tuples of bot... if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Find the optimal control, 1. Use the Weierstrass condition, find the (Stron... 1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where

Queues, what is the difference between data type and abstract data type what is the difference between data type and abstract data type

Algorithm to add an element at the end of linked list, Write an algorithm t... Write an algorithm to add an element at the end of circular linked list.   Algorithm to Add the Element at the End of Circular Linked List. IINSENDCLL( INFO, LINK, START, A

What is assertions and abstract data types, Assertions and Abstract Data Ty... Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

A Booth''s, Draw a flowchart of a Booth''s multiplication algorithm and exp... Draw a flowchart of a Booth''s multiplication algorithm and explain it.

How do you find the complexity of an algorithm, How do you find the complex... How do you find the complexity of an algorithm?  Complexity of an algorithm is the measure of analysis of algorithm. Analyzing an algorithm means predicting the resources that