Algorithm for the selection sort, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Algorithm for the selection sort

Explain expert system, 1. What is an expert system and where are they need...

1. What is an expert system and where are they needed? 2. What are the major issues involved in building an expert system?

A binary tree in which levels except possibly the last, A binary tree in wh...

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

Explain about the preconditions assertion, Preconditions assertion A ...

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

Homework, Write a recursive function the computes the number of digits in a...

Write a recursive function the computes the number of digits in a positive integer n. For example if n = 6598, the function should return 4. Find a variant expression and a thresho

Darw a flowchart to input 3 numbers, This algorithm inputs 3 numbers, every...

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

Doubly linked list, How does operations like insertion, deletion occur?

How does operations like insertion, deletion occur?

State about the simple types - built-in types, State about the Simple types...

State about the Simple types - Built-In Types Values of the carrier set are atomic, that is, they can't be divided into parts. Common illustrations of simple types are inte

Storing a sparse matrix in memory, Explain an efficient method of storing a...

Explain an efficient method of storing a sparse matrix in memory. Write a module to find the transpose of the sparse matrix stored in this way. A matrix which contains number o

Minimum cost spanning trees, A spanning tree of any graph is only a subgrap...

A spanning tree of any graph is only a subgraph that keeps all the vertices and is a tree (having no cycle). A graph might have many spanning trees. Figure: A Graph

Explain about hidden-surface, Explain about Hidden-surface Hidden-line...

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

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd