Algorithm for the selection sort, Data Structure & Algorithms

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







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
Related Questions
If a node in a BST has two children, then its inorder predecessor has No right child

give some examples of least cost branch and bound method..

Q. Describe the term hashing. Explain any two usually used hash functions. Explain one method of collision resolution.

Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref

W h at are the different ways by which we can represent graph?  Represent the graph drawn below using those ways.     T he d iff e r e nt w a y s by

In the amortized analysis, the time needed to perform a set of operations is the average of all operations performed. Amortized analysis considers as a long sequence of operations

the deference between insertion,selection and bubble sort

A LGORITHM (Deletion of an element from the linked list) Step 1  Begin Step 2  if the list is empty, then element cannot be deleted Step 3  else, if the element to be del

#What is the pointer