対称整列法：攪乱要因dに対しO（n* log （d））時間の整列法

• Item type: SIG Technical Reports(1)
• 公開日: 1992-07-17
• タイトル: 対称整列法：攪乱要因dに対しO（n* log （d））時間の整列法
• タイトル / 言語: en
• タイトル: SYMMETRIC SORT: AN O (n* log (d) ) SORT WHERE d IS A DISOBDERING FACTOR
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学理工学部 情報学科
• 著者所属: 早稲田大学理工学部 情報学科
• 著者所属: 早稲田大学理工学部 情報学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science School of Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science School of Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science School of Science and Engineering, Waseda University
• 著者名: 二村, 良彦; 二村, 夏彦; 筧, 捷彦
• 著者名(英): Oshihiko, Futamura; Natuhiko, Futamura; Katuhiko, Kakehi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 実際的に高速な整列法を提案する。まず数列がどの程度非整列であるかを明確にするために数列の攪乱要因dと呼ぶ新しい概念を導入する．それは「両隣の要素よりも大きい要素（攪乱要素）の個数」である。次に0≦d≦（?）/2かつ長さnの全数列についてのdの平均値は（?）/3であることを示し，対称ヒープを利用した新しい整列法（対称ソート）が与えられた数列の長さnのみならずその攪乱要因dにも明白に依存する平均O（*log（））かつ最悪O（*）時間の整列法であることを証明する（ただしd=0およびd=1のときは例外的に最悪O（）時間で整列できる）。最後にQUICKソートおよびリストマージソートとの比較実験および計算量の理論的検討結果を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A new sorting algorithm called symmetric sort and running fast in practical uses is described. The disordering factor d of a sequence is introduced to evaluate the disorderedness of the sequence. The d is the number of elements which are greater than both their left and right elements. Then, 0≦d≦(n-1) and the fact that the average value of d is (n-2)/3 are shown. It is proved that the symmetric sort runs in O(n*log(d)) average and O(n*d) worst case time on a sequence with length n and disordering factor d>1. For d=o or d=1, the sort runs in O(n) worst case time. Finally, results of theoretical and experimental comparison between the performances of QUICK sort, list-merge sort and symmetric sort are presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1992, 号 58(1992-AL-028), p. 59-67, 発行日 1992-07-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会