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
What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

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

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

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.

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.

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

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.

explain the prims''s algorithm with suitable example?

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 .

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