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

Merge sort , What is the best-case number of comparisons performed by merge... What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

How to construct binary tree, Q. A Binary tree comprises 9 nodes. The preor... Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D

Write functions for both addition and subtraction, You will write functions... You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

Linked list, create aset of ten numbers.then you must divide it into two s... create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

Hashing and collisions during hashing, Q. What do you understand by the te... Q. What do you understand by the term Hashing?  How do the collisions occur during hashing?  Explain the different techniques or methods for resolving the collision.

What is complexity, Complexity is the rate at which the needed storage or c... Complexity is the rate at which the needed storage or consumed time rise as a function of the problem size. The absolute growth based on the machine utilized to execute the program

Use of asymptotic notation in the study of algorithm, Q. What is the need o... Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Graph, explain the prims''s algorithm with suitable example? explain the prims''s algorithm with suitable example?

Linked list implementation of a queue, The fundamental element of linked li... The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

Graph traversal, 1) Which graph traversal uses a queue to hold vertices whi... 1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a