Publication

Smoothsort revisited

Bron, C. & Hesselink, W. H., 13-Sep-1991, In : Information Processing Letters. 39, 5, p. 269-276 8 p.

Research output: Contribution to journalArticleAcademicpeer-review

APA

Bron, C., & Hesselink, W. H. (1991). Smoothsort revisited. Information Processing Letters, 39(5), 269-276.

Author

Bron, Coenraad ; Hesselink, Wim H. / Smoothsort revisited. In: Information Processing Letters. 1991 ; Vol. 39, No. 5. pp. 269-276.

Harvard

Bron, C & Hesselink, WH 1991, 'Smoothsort revisited', Information Processing Letters, vol. 39, no. 5, pp. 269-276.

Standard

Smoothsort revisited. / Bron, Coenraad; Hesselink, Wim H.

In: Information Processing Letters, Vol. 39, No. 5, 13.09.1991, p. 269-276.

Research output: Contribution to journalArticleAcademicpeer-review

Vancouver

Bron C, Hesselink WH. Smoothsort revisited. Information Processing Letters. 1991 Sep 13;39(5):269-276.


BibTeX

@article{df00d8298a2b4457a9ebf44ece4a7b79,
title = "Smoothsort revisited",
abstract = "A renewed analysis of Dijkstra's array sorting algorithm Smoothsort showed that the removal of a complexity improved the performance. The resulting algorithm has a worst-case behaviour of order N.log N. In the average case, it has more or less the same speed as heapsort. For arrays that are initially almost sorted, it is much faster than heapsort and can compete with quicksort. The correctness is argued by means of invariants. The performance is measured in terms of comparisons and exchanges, both in the analysis of worst-case behaviour and in the experimental data.",
keywords = "ANALYSIS OF ALGORITHMS, DESIGN OF ALGORITHMS, PERFORMANCE EVALUATION, SORTING",
author = "Coenraad Bron and Hesselink, {Wim H.}",
note = "Relation: https://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen. Research Institute for Mathematics and Computing Science (IWI)",
year = "1991",
month = "9",
day = "13",
language = "English",
volume = "39",
pages = "269--276",
journal = "Information Processing Letters",
issn = "0020-0190",
number = "5",

}

RIS

TY - JOUR

T1 - Smoothsort revisited

AU - Bron, Coenraad

AU - Hesselink, Wim H.

N1 - Relation: https://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen. Research Institute for Mathematics and Computing Science (IWI)

PY - 1991/9/13

Y1 - 1991/9/13

N2 - A renewed analysis of Dijkstra's array sorting algorithm Smoothsort showed that the removal of a complexity improved the performance. The resulting algorithm has a worst-case behaviour of order N.log N. In the average case, it has more or less the same speed as heapsort. For arrays that are initially almost sorted, it is much faster than heapsort and can compete with quicksort. The correctness is argued by means of invariants. The performance is measured in terms of comparisons and exchanges, both in the analysis of worst-case behaviour and in the experimental data.

AB - A renewed analysis of Dijkstra's array sorting algorithm Smoothsort showed that the removal of a complexity improved the performance. The resulting algorithm has a worst-case behaviour of order N.log N. In the average case, it has more or less the same speed as heapsort. For arrays that are initially almost sorted, it is much faster than heapsort and can compete with quicksort. The correctness is argued by means of invariants. The performance is measured in terms of comparisons and exchanges, both in the analysis of worst-case behaviour and in the experimental data.

KW - ANALYSIS OF ALGORITHMS

KW - DESIGN OF ALGORITHMS

KW - PERFORMANCE EVALUATION

KW - SORTING

M3 - Article

VL - 39

SP - 269

EP - 276

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -

ID: 6298822