Wikipedia

「奇偶転置ソート」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
編集の要約なし
49行目:
 
=== 動作例 ===
<insmath>下線\widehat{8,4}</insmath> のような表記は比較（と交換）されたデータの組を示す。
 
初期データ: <math>8 ,4 ,3 ,7 ,6 ,5 ,2 ,1</math>
 
{|class=wikitable
<ins>8 4</ins> <ins>3 7</ins> <ins>6 5</ins> <ins>2 1</ins><br />
!時間!!置換前の状態!!組!!置換個数!!置換後の状態
1回目のスキャン終了後:（組1/交換回数:3）<br />
|-
4 8 3 7 5 6 1 2
|style="text-align:right"|1
|<math>\widehat{8,4}, \widehat{3,7}, \widehat{6,5}, \widehat{2,1}</math>
|組1
|style="text-align:right"|3
|<math>4,8,3,7,5,6,1,2</math>
|-
|style="text-align:right"|2
|<math>4,\widehat{8,3},\widehat{7,5},\widehat{6,1},2</math>
|組2
|style="text-align:right"|3
|<math>4,3,8,5,7,1,6,2</math>
|-
|style="text-align:right"|3
|<math>\widehat{4,3},\widehat{8,5},\widehat{7,1},\widehat{6,2}</math>
|組1
|style="text-align:right"|4
|<math>3,4,5,8,1,7,2,6</math>
|-
|style="text-align:right"|4
|<math>3,\widehat{4,5},\widehat{8,1},\widehat{7,2},6</math>
|組2
|style="text-align:right"|2
|<math>3,4,5,1,8,2,7,6</math>
|-
|style="text-align:right"|5
|<math>\widehat{3,4},\widehat{5,1},\widehat{8,2},\widehat{7,6}</math>
|組1
|style="text-align:right"|3
|<math>3,4,1,5,2,8,6,7</math>
|-
|style="text-align:right"|6
|<math>3,\widehat{4,1},\widehat{5,2},\widehat{8,6},7</math>
|組2
|style="text-align:right"|3
|<math>3,1,4,2,5,6,8,7</math>
|-
|style="text-align:right"|7
|<math>\widehat{3,1}, \widehat{4,2}, \widehat{5,6}, \widehat{8,7}</math>
|組1
|style="text-align:right"|3
|<math>1,3,2,4,5,6,7,8</math>
|-
|style="text-align:right"|8
|<math>1,\widehat{3,2},\widehat{4,5},\widehat{6,7},8</math>
|組2
|style="text-align:right"|1
|<math>1,2,3,4,5,6,7,8</math>
|}
 
交換回数:<math>3+3+4+2+3+3+3+1=22（22</math>（[[バブルソート]]と同じ）▼
4 <ins>8 3</ins> <ins>7 5</ins> <ins>6 1</ins> 2<br />
2回目のスキャン終了後:（組2/交換回数:3）<br />
4 3 8 5 7 1 6 2
 
<ins>4 3</ins> <ins>8 5</ins> <ins>7 1</ins> <ins>6 2</ins><br />
3回目のスキャン終了後:（組1/交換回数:4）<br />
3 4 5 8 1 7 2 6
 
3 <ins>4 5</ins> <ins>8 1</ins> <ins>7 2</ins> 6<br />
4回目のスキャン終了後:（組2/交換回数:2）<br />
3 4 5 1 8 2 7 6
 
<ins>3 4</ins> <ins>5 1</ins> <ins>8 2</ins> <ins>7 6</ins><br />
5回目のスキャン終了後:（組1/交換回数:3）<br />
3 4 1 5 2 8 6 7
 
3 <ins>4 1</ins> <ins>5 2</ins> <ins>8 6</ins> 7<br />
6回目のスキャン終了後:（組2/交換回数:3）<br />
3 1 4 2 5 6 8 7
 
<ins>3 1</ins> <ins>4 2</ins> <ins>5 6</ins> <ins>8 7</ins><br />
7回目のスキャン終了後:（組1/交換回数:3）<br />
1 3 2 4 5 6 7 8
 
1 <ins>3 2</ins> <ins>4 5</ins> <ins>6 7</ins> 8<br />
8回目のスキャン終了後:（組2/交換回数:1）<br />
1 2 3 4 5 6 7 8
 
▲交換回数:3+3+4+2+3+3+3+1=22（[[バブルソート]]と同じ）
 
== 外部リンク ==
「https://ja.wikipedia.org/wiki/奇偶転置ソート」から取得