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 time complexity, Time Complexity:- The time complexity of an algori...

Time Complexity:- The time complexity of an algorithm is the amount of time it requires to run to completion. Some of the reasons for studying time complexity are:- We may be in

Hashing and five popular hashing functions, Q. Explain the term hashing? Ex...

Q. Explain the term hashing? Explain any five well known hash functions.                         Ans: Hashing method provides us the direct access of record from the f

Explain linked list and its types, Data Structure and Algorithm 1. Exp...

Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

Write a program for linear search, In the book the following methods are pr...

In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

C++, 7. String manipulation 7.a Write a C Program using following strin...

7. String manipulation 7.a Write a C Program using following string manipulation functions a) strcpy b) strncpy c) strcmp d) strncmp e) strlen f) strcat

Algorithm for the selection sort, Q. Give the algorithm for the selection s...

Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.

Generic doubly linked list, Your objective is to write a generic doubly lin...

Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a

Define binary search technique, Binary search technique:-  This techniq...

Binary search technique:-  This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is separated into t

Explain dijkstra''s algorithm, Explain Dijkstra's algorithm Dijkstra's ...

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node

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