単語記事: ソート

編集  

ソート英:sort)とは、種類、仕方、方法などを意味する英単である。

またコンピューターとしては、「情報の並べ替え」を行うこと。この記事ではこれについて解説する。

概要

プログラミングにおいて、ソートとはバラバラデータを規則正しく並べ替えること。コンピュータで扱う代表的な問題なので、効率化のためにいろいろなアルゴリズムが開発されてきた。

並のプログラマーライブラリソート処理を投げていることが多いため、自前で実装しろといわれると中々思い出せず、分厚い参考書を引っり出すハメになる物。

種類

ニコニコ大百科に記事があるソートアルゴリズム名は太字。)

その他多数。ソートの調べ物をするときに「安定ソート」とか「均計算量」とかに気をつけると楽しい。

バブルソート

ソートアルゴリズムで必ず最初に習うもの。較回数、交換回数やたら多く、元の並び順によって較回数が変わるということもいので効率が悪い。

#include <stddef.h> /* size_t */ void bubble_sort(int *base, size_t nmemb) { size_t i; for (i = 0, nmemb--; i < nmemb; i++) { size_t j; for (j = nmemb; j > i; j--) { /* 後ろの方から始める */ if (base[j - 1] > base[j]) { /* 隣り合った要素を較し、前が大きければ交換。 */ int tmp; tmp = base[j - 1]; base[j - 1] = base[j]; base[j] = tmp; } /* これを繰り返して小さい物をどんどん前へ持って行く。 */ } /* この時点で一番前の要素が確定する。 */ } return; }

Rubyの配列のsortメソッド

このサイトを支えているRubyソートをするときはこんな感じになる。

array = array.sort

簡単ですね。これからプログラムを学ぶ人はRubyに入信しなさい。

関連動画

キャラクターの表示順序のためにバケットソートを利用している。アルゴリズムの解説付き。

関連項目

(様々なソートアルゴリズムの記事については、「種類」の節を参照)


【スポンサーリンク】

携帯版URL:
http://dic.nicomoba.jp/k/a/%E3%82%BD%E3%83%BC%E3%83%88
ページ番号: 736993 リビジョン番号: 2409676
読み:ソート
初版作成日: 08/11/24 08:36 ◆ 最終更新日: 16/09/25 11:40
編集内容についての説明/コメント: 「種類」の節で、記事が作成された「ティムソート」を追加しました。
記事編集 / 編集履歴を閲覧
このエントリーをはてなブックマークに追加

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

ソートについて語るスレ

5 : ななしのよっしん :2013/02/12(火) 23:06:54 ID: aaUmP0v04J
array.sort!だけで整列できるruby最強
6 : ななしのよっしん :2013/08/19(月) 05:03:07 ID: o8iS3Nid6Z
「数字が書かれた100枚のカード」を整列させて一つの山にするにはどうすればいいか?

選択ソート:最も大きい数字を探して、山の一番下にする。
      2番に大きい数字を探して、最も大きい数字の上に置く。
      3番に大きい数字を探して、2番に大きい数字の上に置く。以下繰り返し。

挿入ソート:整列されていないカードから適当に1枚取って、整列済みの山の正しい位置に入れる。

マージソート100個の「整列された1枚組の山」とみなす。
      あとは一つの山になるまで、「最も小さい山2つ」をまとめて整列させていく。

ボゴソート適当に拾い集めて整列されているか調べる。整列されていなかったらバラバラに。
7 : ななしのよっしん :2015/06/10(水) 03:04:38 ID: 4We22uEu77
何でボゴソートの記事があるんだよww
もっと先に作るべきものがあるだろ
8 : ななしのよっしん :2015/06/17(水) 13:23:45 ID: dso+IPYfIe
総統も相当ソートがお好きで
9 : ななしのよっしん :2015/06/17(水) 21:37:23 ID: hFnyHxmc7r
>>sm26445256
10 : ななしのよっしん :2015/09/20(日) 18:13:31 ID: g/k4kueuPO
々々々…並列計算が可世界ではボゴソートが最速のソートになるという与太話

どう頑っても一段の処理→二段の処理→三段の処理のような
処理の階層構造になるクイックソートなどのアルゴリズム
ボゴソートは一切処理間に依存関係が発生しないため
一発で解答を出せてしまうという
11 : ななしのよっしん :2016/01/05(火) 22:27:55 ID: SF2uKRxkrW
>>sm21994071
12 : ななしのよっしん :2016/04/21(木) 19:18:15 ID: NOFPuNZfIJ
最近スリープソートというすごいソートを知った
1.それぞれの要素分の時間だけ、同時にsleepする
2.sleepから覚めた要素から順に取り出す
3.一番大きい要素が覚めたら終了
4.ね、簡単でしょう?
13 : ななしのよっしん :2016/05/19(木) 18:26:59 ID: LmV6M2AKKg
ミラクルソート
1.要素が整列されているか確認する
2.整列されていれば終了、されていなければ最初に戻る

とか、
名無しソート
1.要素のありうるすべての並びをメモリ上に展開
2.整列しているものを見つける

なんてのがあるらしい。この手のものはいくらでもありそうだけど
14 : ななしのよっしん :2017/08/07(月) 06:54:16 ID: C1Tp7yBAat
並列性が重要ならバイトニックソート+マージソートがなかなかいい
PRAM上でO(log^2n)だよ
ハイパーキューブでもバイトニックソートは速いよ

PRAMでもっと高速なアルゴリズムはO(logn)で動くよ
較交換に基づくアルゴリズムでは理論上最速だよ
急上昇ワード
ニコニコニューストピックス
電ファミwiki
  JASRAC許諾番号: 9013388001Y45123
  NexTone許諾番号: ID000001829