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
Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Double Linked List In a doubly linked list, also known as 2 way lists, each node is separated into 3 parts. The first part is called last pointer field. It has the address of t

Define about the inheritance hierarchy Languages Eiffel and D provide constructs in language for invariants and pre- and post conditions which are compiled into the code and ar

Spanning Trees: A spanning tree of a graph, G, refer to a set of |V|-1 edges which connect all vertices of the graph. There are different representations of a graph. They are f

sdsd.

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

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

Explain the Memory Function method The Memory Function method seeks to combine strengths of the top  down and bottom-up approaches  to  solving  problems  with  overlapping  su

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as