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

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

Determine the types of java, Determine the types of JAVA Java has two p...

Determine the types of JAVA Java has two parts... 1. Core language -- variables, arrays, objects o Java Virtual Machine (JVM) runs the core language o Core language is

Algorithm for finding a key by binary search technique, Q. Write down an al...

Q. Write down an algorithm for finding a key from a sorted list using the binary search technique or method.

Create algorithm for similarities between documents, Here is a diagram show...

Here is a diagram showing similarities between documents; this is an actual set of physics lab assignments from a large university. Each node (square) in the graph is a doc

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.

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

Complexity of an algorithm, An algorithm is a sequence of steps to solve a ...

An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorithm depends upon following cons

Linear array, representation of linear array

representation of linear array

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