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
State about the Bit String Carrier set of the Bit String ADT is the set of all finite sequences of bits, including empty strings of bits, which we denote λ. This set is {λ, 0

Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu

A telephone directory having n = 10 records and Name field as key. Let us assume that the names are stored in array 'm' i.e. m(0) to m(9) and the search has to be made for name "X"

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

This algorithm inputs number of hours of sunshine recorded every day for a week (7 days). Output is the highest value for hours of sunshine and average (mean) value for numbers of

Programming for hash table?

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

Program will demonstrate the insertion of an element at desired position /* Inserting an element into contiguous list (Linear Array) at particular position */ /* contiguous_

1. develop an algorithm which reads two decimal numbers x and y and determines and prints out wether x>y or y>x. the input values, x and y, are whole number > or equal to 0, which