Revision as of 12:15, 9 January 2019 edit 194.254.61.42 (talk) →Space complexity: the previous content of the section was complete rubbish (both factually incorrect and with obviously invalid arguments in the lower bound claim). ← Previous edit		Revision as of 13:15, 17 December 2019 edit undo Frap (talk \| contribs) Extended confirmed users, File movers, Pending changes reviewers, Rollbackers 35,593 edits →Partial selection sort: MOS:ALGO Next edit →
Line 24: More generally, a partial selection sort yields a simple selection algorithm which takes O(''kn'') time. This is asymptotically inefficient, but can be sufficiently efficient if ''k'' is small, and is easy to implement. Concretely, we simply find the minimum value and move it to the beginning, repeating on the remaining list until we have accumulated ''k'' elements, and then return the ''k''th element. Here is partial selection sort-based algorithm: '''function''' select(list[1..n], k) '''for''' i '''from''' 1 '''to''' k minIndex = i minValue = list[i] '''for''' j '''from''' i+1 '''to''' n '''do''' '''if''' list[j] < minValue '''then''' minIndex = j minValue = list[j] swap list[i] and list[minIndex] '''return''' list[k] == Partition-based selection ==

Selection algorithm: Difference between revisions