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
Q. Construct a binary tree whose nodes in inorder and preorder are written as follows: Inorder : 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 Preorder: 20, 15, 10

In this section, we will discuss about Sequential file organization. Sequential files have data records stored in a particular sequence. A sequentially organized file might be stor

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

HLS Colour Model  This model has the double-cone representation shown in Figure 3.40. The three colour parameters in this model are called hue (H), lightness (L), and Saturati

Searching is the procedure of looking for something. Searching a list containing 100000 elements is not the similar as searching a list containing 10 elements. We discussed two sea

Objectives The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code. Background An arbitrary BST i

Given is the structure of an AVL tree: struct avl { struct node *left; int info; int bf; struct node *right; }; 2) A multiway tree of n order is an ord

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

Best Case: If the list is sorted already then A[i] T (n) = c1n + c2 (n -1) + c3(n -1) + c4 (n -1)  = O (n), which indicates that the time complexity is linear. Worst Case: