컴퓨터 科學 과 數學 에서 整列 알고리즘 ( sorting algorithm )이란 元素들을 番號順이나 事前 順序와 같이 일정한 順序대로 列擧하는 알고리즘이다. 效率的인 整列은 探索이나 倂合 알고리즘처럼 (整列된 리스트에서 바르게 動作하는) 다른 알고리즘을 最適化하는 데 重要하다. 또 整列 알고리즘은 데이터의 定規化 나 意味있는 結果物을 生成하는 데 有用히 쓰인다.

버블 整列 은 1956年 에 分析되었다. ^[1] 數없이 많은 論議를 거쳐왔지만, 쓸만한 새로운 整列 알고리즘들은 現在도 繼續 發明되고 있다(예를 들어, 라이브러리 整列 은 2004年 에 發表되었다). 整列 알고리즘은 다양한 核心 알고리즘 槪念 ? 漸近 表記法 , 分割 征服 알고리즘 , 資料 構造 , 最惡의 境遇 , 平均的인 境遇 , 最善의 境遇 等 ? 을 紹介하는 데 適當하기 때문에, 컴퓨터 科學 講義에서 入門 過程으로 流行하고 있다.

歷史 [ 編輯 ]

컴퓨팅의 始作부터 整列 알고리즘은 單純한 目標지만 效率的으로 實行하기 위해 相當한 硏究가 進行되어 왔다. 1951年 즈음 初期 整列 알고리즘 開發者들 가운데 에니악 과 유니朴 을 作業하였던 베티 홀버튼 (Betty Holberton)이 있었다. ^{[2] [3]} 거품 整列 이 1956年 秒에 分析되었다. ^[4] 比較 整列 알고리즘은 Ω( n log n ) 比較를 위한 重要한 要件이 있다. 計數 整列 等 比較에 基盤을 두지 않는 알고리즘은 더 나은 性能을 보일 수 있다. 漸近 最適 알고리즘(Asymptotically optimal algorithm)들은 20世紀 中旬부터 알려졌다. 有用하고 새로운 알고리즘들은 如前히 發明되고 있으며 그 中 現在 널리 쓰이는 팀소트 는 2002年으로 거슬러 올라가며 라이브러리 소트 는 2006年 처음 出版되었다.

整列 알고리즘은 컴퓨터 科學 紹介 授業에서 一般的이며 여기서 問題를 위한 豐富한 알고리즘들은 漸近 表記法 , 分割 征服 알고리즘 等의 다양한 核心 알고리즘 槪念, 그리고 힙 과 李瑱 트리 等의 資料 構造 , 確率的 알고리즘 , 最善, 最惡, 그리고 平均의 境遇 分析, 타임스페이스 트레이드오프 , 下限 및 上限 을 紹介한다.

分類 [ 編輯 ]

整列 알고리즘은 다음과 같은 基準으로 分類된다:

• 元素들의 크기 比較에 따른 計算 複雜度 ( 最善, 最惡, 平均 動作). 直列 整列 알고리즘의 境遇 最善 動作은 O( n  log  n ), 最善 動作 中 竝列 整列은 O(log ²   n ), 最惡 動作은 O( n ² )이다. ( 漸近 表記法 參考.) 直列 整列의 理想的인 動作은 O( n )이지만 平均 케이스에는 可能치 않다. 最適의 竝列 整列은 O(log  n )이다. 比較 基盤 整列 알고리즘 은 大部分의 入力에 對해 最小 Ω( n  log  n )個의 比較가 必要하다.
• 元素들의 交換 回數에 따른 計算 複雜度 .
• 메모리 使用量 (및 다른 컴퓨터 資源의 使用量). 特히 一部 整列 알고리즘들은 제자리 (in-place, 인플레이스)이다. 正確히 말해 제자리 整列은 整列되는 項目 外에 O(1)개의 메모리만 必要하며 O(log( n ))개의 追加的인 메모리를 人플레이스로 看做한다.
• 再歸. 一部 알고리즘들은 再歸性을 띄거나 再歸性을 띄지 않을 수 있으며 다른 알고리즘들은 그 둘의 特性을 지닐 수 있다. (예: 머지 소트)
• 安定性: 安定的인 整列 알고리즘들은 同一 키(예: 값)의 레코드의 相對的인 順序를 管理한다.
• 比較 整列 인지 아닌지의 與否. 比較 整列은 比較 演算子를 통해 2個의 要素만을 比較함으로써 데이터를 檢査한다.
• 一般的인 方式: 揷入, 交換, 選擇, 倂合 等. 交換 整列에는 거품 整列과 퀵소트가 있다. 選擇 整列에는 셰이커 소트와 힙소트가 있다.
• 알고리즘이 直列인지 整列인지의 與否. 이 討論의 나머지 部分은 거의 例外的으로 直列 알고리즘에 集中하며 直列 造作을 다룬다.
• 順應性: 入力을 미리 整理하는 일이 實行 時間에 影響을 미치는지의 與否. 이를 考慮事項에 넣는 알고리즘들은 順應的 이다.

安定性 [ 編輯 ]

安定 整列 알고리즘은 反復되는 要素를 入力 때와 同一한 順序로 整列시킨다. 특정한 類型의 데이터를 整列할 때 整列 順序 決定 時 데이터의 一部分만 檢査한다.

安定性은 몇 가지 理由로 重要하다. 例를 들어, 데이터가 學生 이름으로 于先 整列되면(일부의 境遇 웹 페이지에 動的으로) 데이터는 이제 어느 學級에 位置하는지에 따라 다시 整列된다. 學生들이 같은 學級에 있다고 假定한다면 이들의 이름 順序는 특정한 順序가 아니게 뒤섞이며 이는 성가신 問題일 수 있다. 整列 알고리즘이 安定的이면 學生 이름은 正常的인 順序에 位置할 수 있다.

알고리즘의 比較 [ 編輯 ]

아래 表에서 n 은 整列된 레코드의 數를 의미한다. "平均"과 "最惡" 熱은 各 키의 길이가 일정하고 모든 比較, 交換, 其他 必要한 組織이 일정한 時間에 遂行될 수 있다는 假定 下의 各 케이스別 時間 複雜度 를 나타낸다. "메모리"는 同一한 家庭에서 리스트 그 自體에서 使用되는 것 以上으로 必要한 補助 記憶空間의 量을 의미한다. 아래에 羅列된 實行 時間과 메모리 要件은 漸近 表記法 안에서 理解해야 하므로 로그 밑數(base of the logarithms)는 問題가 되지 않는다. log ² n 表記는 (log n ) ² 를 의미한다.

比較 整列 [ 編輯 ]

다음은 比較 整列 票이다. 比較 整列은 O ( n log n ) 보다 더 나은 性能을 낼 수 없다. ^[5]

比較 整列

이름	最善	平均	最惡	메모리	安定	方式
퀵 整列	${\displaystyle n\log n}$ variation is n	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$ on average, worst case space complexity is n ; Sedgewick variation is ${\displaystyle \log n}$ worst case.	一般的인 제자리 整列은 安定的이지 못하다. 安定板이 存在한다.	파티셔닝
合倂 整列	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n A hybrid block merge sort is O (1) mem.	예	合倂
제자리 合倂 整列	?	?	${\displaystyle n\log ^{2}n}$ 上壇 參考. 하이브리드의 境遇 ${\displaystyle n\log n}$	1	예	合倂
힙 整列	n 모든 키가 區別되는 境遇, ${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	아니오	選擇
揷入 整列	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	예	揷入
인트로소트	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	아니오	파티셔닝, 選擇
選擇 整列	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	아니오	選擇
팀소트	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	예	揷入, 合倂
큐브소트	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	예	揷入
셸 整列	${\displaystyle n\log n}$	Depends on gap sequence	Depends on gap sequence; best known is ${\displaystyle n^{1.25}}$	1	아니오	揷入
거품 整列	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	예	交換
李瑱 트리 整列	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$(balanced)	n	예	揷入
사이클 整列	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	아니오	揷入
라이브러리 소트	n	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	n	예	揷入
페이션스 소팅	n	?	${\displaystyle n\log n}$	n	아니오	揷入, 選擇
스무스소트	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	아니오	選擇
스트랜드 소트	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	n	예	選擇
토너먼트 整列	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n [6]	아니오	選擇
칵테일 整列	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	예	交換
빗질 整列	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	아니오	交換
그놈 整列	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	예	交換
言셔플 소트 [7]	n	kn	kn	In-place for linked lists. n * en:sizeof (link) for array. n+1 for array?	아니오	分散, 合倂
Franceschini's method [8]	?	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	예	?
블록 整列	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	예	揷入, 合倂
홀짝 整列	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	예	交換
커브 整列	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle \Omega (1)\cap {\mathcal {O}}(n)}$	예	揷入, 計數

比較가 아닌 整列 [ 編輯 ]

다음의 表는 精髓 整列 알고리즘들과 比較 整列 이 아닌 기타 整列 알고리즘들을 記述한다. 그러므로 Ω ( n log n ) 에 制限을 받지 않는다. 아래의 複雜度는 n 個의 項目이 整列될 것으로 看做되며 크기 k 의 키, 數字 크기 d , 整列될 數의 範圍 r 이 隨伴된다. 이 中 多數는 모든 項目들이 固有한 키 값을 지닐 수 있을 만큼 키의 크기가 充分히 크므로 n ≪ 2 ^k 에서 ≪는 "훨씬 더 작은"을 意味한다. 單位 原價 랜덤 接近 機械 모델에서 騎手 整列과 같은 ${\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}$의 實行 타임을 갖는 알고리즘들은 Θ( n log n ) 에 比例하는 時間이 所要되는데, 그 理由는 n 이 ${\displaystyle 2^{\frac {k}{d}}}$ 未滿으로 制限되고 整列 對象이 되는 相當數의 要素들이 메모리에 이들을 貯藏하기 爲해 더 큰 k 를 要求하기 때문이다. ^[9]

比較가 아닌 整列

이름	最善	平均	最惡	메모리	安定	n ≪ 2 k
비둘기집 整列	?	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	예	예
버킷 整列 (uniform keys)	?	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	예	아니요
버킷 整列 (integer keys)	?	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	예	예
計數 整列	?	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	예	예
LSD 期數 整列	?	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	예	아니요
MSD 期數 整列	?	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	예	아니요
MSD 期數 整列 (제자리)	?	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle 2^{d}}$	아니요	아니요
스프레드소트	n	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	아니요	아니요
버스트소트	?	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	아니요	아니요
플래시소트	n	${\displaystyle n+r}$	${\displaystyle n^{2}}$	n	아니요	아니요
포스트맨 整列	?	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	?	아니요

샘플소트 는 데이터를 여러 버킷으로 效率的으로 分配한 다음 여러 프로세서로 整列을 傳達시킴으로써 比較가 아닌 整列을 竝列化하기 위해 使用할 수 있으며, 서로 肝 버킷이 이미 整列되어 있으므로 合倂할 必要가 없다.

기타 [ 編輯 ]

一部 알고리즘들은 위에 論議된 것들에 비해 速度가 느린 便인데, 例를 들어 報告整列 과 같은 境遇 限度가 없는 實行 時間을 지니고 꼭두각시 整列 은 O ( n ^2.7 )의 實行 時間을 지닌다. 이 整列들은 알고리즘의 實行 時間이 어떻게 豫測되는지를 證明하기 위해 敎育用으로 記述되는 것이 普通이다. 다음의 表는 매우 낮은 性能 또는 特殊 하드웨어 要求事項으로 인해 傳統的인 소프트웨어 環境에서 實際 使用에는 實用的이지 못한 一部 整列 알고리즘들을 記述하고 있다.

이름	最善	平均	最惡	메모리	安定	比較
籌板 整列	n	S	S	${\displaystyle n^{2}}$	빈칸	아니요
單純 팬케이크 整列	?	n	n	${\displaystyle \log n}$	아니요	예
스파게티(폴) 整列	n	n	n	${\displaystyle n^{2}}$	예	폴링
整列網	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle n\log ^{2}n}$	다양함 (安定 整列網은 더 많은 比較가 要求된다)	예
바이토닉 整列	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle n\log ^{2}n}$	아니요	예
報告整列	n	${\displaystyle (n\times n!)}$	${\displaystyle \infty }$	1	아니요	예
꼭두각시 整列	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	n	아니요	예

種類 [ 編輯 ]

整列 알고리즘은 그 特徵에 따라 몇 가지로 分類할 수 있다.

比較 整列 [ 編輯 ]

比較 整列 은 元素들을 整列할 때 元素들의 順序에만 依存하는 알고리즘들을 일컫는다. 例를 들어 거품 整列 (bubble sort)은 比較하는 元素들이 數字거나, 文字列이거나, 甚至於는 複雜한 客體에 對해서도 順序가 決定되어 있다면 適用할 수 있다.

比較 整列 알고리즘들은 아무리 빨라도 最惡의 境遇 ${\displaystyle \Omega \left(n\log n\right)}$ 時間을 必要로 한다. 이는 이 알고리즘들을 決定 트리 의 形態로 記述할 수 있다는 點에서 證明할 수 있는데, ${\displaystyle n}$個의 元素들의 順列 은 ${\displaystyle n!}$가지로 이들을 잎 노드로 가지는 決定 트리의 깊이는 스털링 近似 에 따라 적어도 ${\displaystyle \lceil \log n!\rceil \approx n\log n}$이어야 하기 때문이다.

比較 整列이 아닌 알고리즘들은 이런 時間 複雜度의 制約이 없지만, 代身 다른 制約을 가질 수 있다. 例를 들어 期數 整列 은 事前順으로 表記하고 分離하기 쉬운 數字나 文字列에 對해서는 效果的이지만, 그렇지 않은 客體들에 對해서는 一般 比較 整列보다 느릴 수 있다.

제자리 整列 [ 編輯 ]

제자리 整列 은 元素들의 개에 비해서 充分히 無視할 만한 貯藏 空間만을 더 使用하는 整列 알고리즘들을 의미하며, 제자리 알고리즘 의 範圍에 包含된다. 例를 들어 揷入 整列 은 이미 주어진 元素들을 옮긴 뒤 適切한 位置에 元素를 揷入하는 演算을 反復하는데, 이 過程에서 元素들을 담는 空間 外에 追加로 使用될 수 있는 空間은 옮겨지는 元素가 貯藏되는 空間과 루프 變數 程度에 不過하다.

퀵 整列 은 제자리 알고리즘의 定義에 따라서 제자리 整列로 分類할 수도 있고 아닐 수도 있다. 퀵 整列은 再歸的으로 定義되기 때문에 스택 을 使用하게 되는데, 이 스택의 깊이는 ${\displaystyle n}$個의 元素에 對해 ${\displaystyle \Omega \left(\log n\right)}$에 比例하므로 全體 空間 複雜度 는 常數가 아니다. 하지만 實用的인 意味에서 퀵 整列은 相對的으로 작은 메모리만을 더 使用하기 때문에 흔히 제자리 整列로 記述된다.

온라인 整列 [ 編輯 ]

온라인 整列 은 모든 元素들이 처음부터 주어지지 않고 次例대로 들어 오는 境遇도 處理할 수 있는 整列 알고리즘을 의미하며, 온라인 알고리즘 에 該當된다. 代表的으로 合倂 整列 은 이미 整列된 여러 個의 部分 리스트를 管理하다가 매 元素가 들어 올 때마다 適切한 리스트에 追加하고 必要하면 리스트들을 合倂하는 式으로 온라인 整列로 만들 수 있다.

著名한 整列 알고리즘 [ 編輯 ]

整列 알고리즘의 數는 많지만 實用的인 具現體의 境遇 一部의 알고리즘들이 優位를 차지하고 있다. 작은 데이터 集合의 境遇 揷入 整列이 널리 使用되는 反面 큰 데이터 集合의 境遇 漸近敵으로 效率的인 整列이 使用되며 여기에는 主로 힙 整列, 合倂 整列, 퀵 整列이 있다. 效率的인 具現體들은 一般的으로 '整列 全般을 위한 漸進的으로 效率的인 알고리즘'을 '再歸 下限의 작은 리스트들을 爲한 揷入 整列'과 倂合한 하이브리드 알고리즘 을 使用한다. 相當한 튜닝을 거친 具現體들은 안드로이드, 자바, 파이썬에 쓰이는 팀소트 (合倂 整列, 揷入 整列, 追加 로직), 一部 C++ sort 具現體와 닷넷에 (여러 形態로) 쓰이는 인트로소트 (퀵整列과 힙 整列) 等 더 複雜한 種類를 使用한다.

固定 間隔의 數字와 같은 더 制限된 데이터의 境遇 計數 整列이나 期數 整列과 같은 分散 整列이 널리 쓰인다. 거품 整列과 같은 種類들은 實際로는 드물게 쓰이지만 敎育 및 理論 討論에서 흔히 볼 수 있다.

物理的으로 客體를 整列할 때(예: 論文, 테스트, 冊을 알파벳 巡으로 整理) 사람들은 작은 集合에 對해 直觀的으로 揷入 整列을 使用하는 것이 普通이다. 큰 集合의 境遇 사람들은 普通 이니셜 文字와 같은 最初 버킷을 使用하며 매우 큰 集合의 境遇 여러 버킷을 使用하는 것이 整列에 實用的이다. 이를테면 客體들을 바닥 위나 넓은 空間 위에 퍼트려놓는다든 方式으로 空間이 相對的으로 低廉한 境遇가 있는데, 이때 特히 客體를 먼 空間으로 움직이는 等의 造作에 對한 費用은 높아지게 되므로 參照의 地域性은 重要하다. 合倂 整列은 特히 두 손을 使用하는 等 物理的인 物體를 다루기 實用的인 反面 힙 整列이나 퀵 整列 等 다른 알고리즘들은 人間이 直接 使用하기에는 適切치 않다. 空間을 남기는 揷入 整列의 변종인 라이브러리 소트 等의 다른 알고리즘들 또한 物理的 利用에 實用的이다.

單純 整列 [ 編輯 ]

가장 單純한 整列 中 揷入 整列과 選擇 整列이 있으며 이 둘 모두 낮은 部下로 인해 작은 데이터에 效率的이지만 큰 데이터에는 效率的이지 않다. 揷入 整列은 大部分 整列된 데이터에 對해 比較를 덜 하고 性能이 좋은 理由로 一般的으로 選擇 整列보다 現實的으로 더 빠르기 때문에 選好되는 傾向이 있으나 選擇 整列은 쓰기를 덜 하므로 쓰기 性能에 制約이 있는 環境에 使用된다.

揷入 整列 [ 編輯 ]

揷入 整列 은 작은 리스트와 大部分 整列된 리스트에 相對的으로 效率的인 單純한 整列 알고리즘이며 더 複雜한 알고리즘의 一部分으로 使用되기도 한다. 리스트로부터 要素를 하나씩 取한 다음 마치 돈을 紙匣에 넣는 方式과 비슷하게 이들을 올바른 位置에, 새로 整列된 리스트에 揷入함으로써 動作한다. ^[10] 配列의 境遇 새 리스트와 남아있는 要素들은 配列 空間을 共有할 수 있으나 揷入의 境遇 잇따르는 모든 要素를 하나씩 移動해야 하므로 費用이 많이 든다. 셸소트 는 큰 리스트에 더 效率的인 揷入 整列의 變種이다.

選擇 整列 [ 編輯 ]

選擇 整列은 제자리 比較 整列 이다. 複雜度는 O ( n ² )이므로 큰 리스트에는 非效率的이며, 類似한 揷入 整列 보다 性能이 더 떨어지는 것이 一般的이다. 選擇 整列은 單純함이 特徵이며 특정한 狀況에서는 더 複雜한 알고리즘보다 性能上 優位가 있다.

이 알고리즘은 最小값을 찾고 값을 最初 位置와 바꿔친 다음 리스트의 나머지 部分에 對해 이 過程을 反復한다. ^[11] 交換 過程은 n 個를 넘지 않으므로 交換 費用이 많이 드는 狀況에서 有用하다.

效率的인 整列 [ 編輯 ]

實用的인 一般 整列 알고리즘들은 平均 時間 複雜度(및 一般的으로 最惡의 境遇의 複雜度) O( n log n )의 알고리즘에 基盤한 境遇가 大部分이며 그 中 가장 흔한 것이 힙 整列, 合倂 整列, 퀵 整列이다. 제各其 長短點이 있으며, 單純 合倂 整列의 具現體는 O( n ) 追加 空間을 使用하며 單純한 퀵 整列 具現體는 O( n ² ) 最惡의 境遇 複雜度를 使用하는 것이 가장 큰 特徵이다. 이 問題들은 더 複雜한 알고리즘의 費用으로 解決되거나 改善할 수 있다.

이 알고리즘들이 다양한 修正이 隨伴되는 實生活 데이터를 基準으로 랜덤 데이터에 漸近敵으로 效率的이다. 첫째로, 이 알고리즘들이 일으키는 簿하는 크기가 작은 데이터일수록 重大한 까닭에 하이브리드 알고리즘이 使用되기도 하며 데이터가 充分히 작으면 普通 揷入 整列로 轉換된다. 둘째로, 알고리즘은 이미 整列된 데이터나 거의 整列이 마무리된 데이터에 對해 性能이 떨어지는 境遇가 있기 때문에 이 알고리즘들은 實生活 데이터에 一般化되어 있으며 大略的인 알고리즘들에 依해 O( n ) 時間으로 整列이 可能하다. 끝으로, 이 알고리즘들은 不安定 整列에 屬할 수 있는데 整列 時 安定性은 바람직한 屬性으로 看做되기도 한다. 그러므로 팀소트 (合倂 整列 基盤) 또는 인트로소트 (퀵 整列 基盤으로, 必要 時 中間에 힙 整列로 變更됨)와 같은 더 複雜한 알고리즘들이 適用되기도 한다.

合倂 整列 [ 編輯 ]

힙 整列 [ 編輯 ]

퀵 整列 [ 編輯 ]

셸 소트 [ 編輯 ]

거품 整列 및 變種 [ 編輯 ]

버블 整列 [ 編輯 ]

빗질 整列 [ 編輯 ]

分散 整列 [ 編輯 ]

計數 整列 [ 編輯 ]

버킷 整列 [ 編輯 ]

期數 整列 [ 編輯 ]

같이 보기 [ 編輯 ]

• 檢索 알고리즘

參照 [ 編輯 ]

追加 文獻 [ 編輯 ]

• Knuth, Donald E. (1998), 《Sorting and Searching》, The Art of Computer Programming 3 2板, Boston: Addison-Wesley, ISBN   978-0201896855  

外部 링크 [ 編輯 ]

• Sorting Algorithm Animations - 웨이백 머신 (保管됨 3 3月 2015)
• Sequential and parallel sorting algorithms Archived 2012年 12月 13日 - 웨이백 머신 ? explanations and analyses of many sorting algorithms
• Dictionary of Algorithms, Data Structures, and Problems ? dictionary of algorithms, techniques, common functions, and problems
• Slightly Skeptical View on Sorting Algorithms ? Discusses several classic algorithms and promotes alternatives to the 퀵 整列 algorithm
• 15 Sorting Algorithms in 6 Minutes (Youtube) ? visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes
• A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements" ? which performed by en:Ford?Johnson algorithm
• Sorting Algorithms Used on Famous Paintings (Youtube) - Visualization of Sorting Algorithms on Many Famous Paintings.