请输入您要查询的字词:

 

单词 SelectionSort
释义

selection sort


The Problem

See the Sorting Problem.

The Algorithm

Suppose L={x1,x2,,xn} is the initial list of unsorted elements.The selection sortMathworldPlanetmath algorithmMathworldPlanetmath sorts this list in n steps. At each step i, find the largestelement L[j] such that j<n-i+1, and swap it with the element at L[n-i+1].So, for the first step, find the largest value in the list and swap it with the last element in the list.For the second step, find the largest value in the list up to (but not including) the last element, and swap itwith the next to last element. This is continued for n-1 steps. Thus the selection sort algorithm is avery simple, in-place sorting algorithm.

Pseudocode

Algorithm Selection_Sort(L, n)
Input: A list L of n elements
Output: The list L in sorted order

begin
         for in downto 2 do

begin

tempL[i]

max1

for j2 to i do

if L[j]>L[max] then

maxj

L[i]L[max]

L[max]temp

end
end

Analysis

The selection sort algorithm has the same runtime for any set of n elements, no matterwhat the values or order of those elements are. Finding the maximum element of a list ofi elements requires i-1 comparisons. Thus T(n), the number of comparisons required tosort a list of n elements with the selection sort, can be found:

T(n)=i=2n(i-1)
=i=1ni-n-2
=(n2-n-4)2
=𝒪(n2)

However, the number of data movements is the number of swaps required, which is n-1. Thisalgorithm is very similar to the insertion sort algorithm. It requires fewer data movements,but requires more comparisons.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 5:00:58