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

Create a function to show data structure, Given a number that is represente...

Given a number that is represented in your data structure, you will need a function that prints it out in base 215 in such a way that its contents can be checked for correctness. Y

Draw the process flow diagram, Draw the process flow diagram: Anand   ...

Draw the process flow diagram: Anand   Dairy (AD) sources 150,000 litres of milk daily from large number of local villagers .The milk is collected from 4:00 AM to 6:00 am and

Dqueue, how can i delete from deque while deletion is restricted from one e...

how can i delete from deque while deletion is restricted from one end

Give example of assertion and abstract data type, Give example of assertion...

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

Define threaded binary tree, Threaded Binary Tree:- By changing the NUL...

Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using

Row major representation, Row Major Representation In memory the primar...

Row Major Representation In memory the primary method of representing two-dimensional array is the row major representation. Under this representation, the primary row of the a

Algorithm for sorting a deck of cards, What is wrong with the following alg...

What is wrong with the following algorithm for sorting a deck of cards (considering the basic properties of algorithms)? I. Put the cards together into a pile II. For each ca

Java code and algorythem, Suppose that you want to develop a program that a...

Suppose that you want to develop a program that accepts a postfix expression and asks values for variables in the expression. Then you need to calculate the answer for the expressi

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