回答編集履歴
1
回答がまったくの見当違いだったため、ご指摘をしてくださった方々の意見も取り入れた回答としての修正を行う
test
CHANGED
|
@@ -1,26 +1,30 @@
|
|
|
1
|
-
バブルソート等を用いてソートしたいってことですよね？
|
|
1
|
+
~~バブルソート等を用いてソートしたいってことですよね？かなり厳しいかと。一応できなくはないですが、リスト構造の良さを捨ててしまっていますよそれ。そもそも配列構造(C++でいえばstd::vectorも含む)とリスト構造の違いを理解していればありえないと思うのですが…細かい説明は省きますが、配列構造はその名の通り、配列です。なのでランダムアクセスは得意ですが、最後尾や先端とかに新しくデータを追加したり削除したりとかが苦手です。どうしても一時的に別の配列を用意してそこにコピーして削除するものは削除し、追加するなら追加する…という処理を加えてすげ替える。でもリスト構造はあの有名なイメージ(基本情報技術者試験ですら出てくる)なので、ランダムアクセスは苦手だけど、最後尾や先端とかに追加したり削除したりとかは得意。バブルソートはarr[1]とかみたいなランダムアクセスをしながら行いますよね。(多分やり方次第ではランダムアクセスしなくてもできるとは思うが、無学な俺には無理…)ということはリスト構造とは相性が悪すぎる。ランダムアクセスが苦手なものを使うわけだから。どうしてもバブルソートで行うなら、「**リストからデータを取り出して、一旦配列にコピー。その配列をバブルソートで整列させて、元のリストに戻す。**」と言う作業をしないといけません。無駄が多すぎます。リスト構造の良さを切り捨てていますね。それならいっそ、最初から配列構造で管理したほうがいいです。リスト構造でソート済みで管理したいだけなら、「**追加時に、ソート済みになるように位置を調べてそこに追加する**」でしょうか。この考え方はあるサイトさんから学んだのですが、追加時にリニアサーチで「ソート済みになるように追加位置を決める」。その後にそこに追加する。って言う感じでした。まず an = { 1, 3, 8 } に 5 を追加したい場合、まずanにあるデータ列を見て 5 をどこに追加すればソート済みになるか調べる。3 と 8 の間、つまり(0番目から考えると) 2番目に追加すればソート済みになりそうですね。ということで、この2番目に5を追加すればいい。ってことです。これを追加するときに行う。一応リスト構造は走査するためのポインタ(C++でいうiterator)がその位置にあって、行ったり来たりすることを考慮しないのならO(1)です。つまりどこに挿入しようと常に一定の時間しかかからないです。データ量がどんなに大きくとも。(ただし「どこに挿入するか」とかのチェックは考慮していない)~~
|
|
2
2
|
|
|
3
|
-
|
|
3
|
+
----
|
|
4
|
-
一応できなくはないですが、リスト構造の良さを捨ててしまっていますよそれ。
|
|
5
4
|
|
|
6
|
-
|
|
5
|
+
[修正]
|
|
7
6
|
|
|
8
|
-
|
|
7
|
+
すみません。修正前の回答は間違えていました…
|
|
8
|
+
私の知識不足が原因でした…
|
|
9
9
|
|
|
10
|
-
|
|
10
|
+
ご指摘を受けてよくよく考えると、バブルソートの要件には「ランダムアクセスで行う事」はありませんでしたね。
|
|
11
11
|
|
|
12
|
-
|
|
12
|
+
----------------
|
|
13
13
|
|
|
14
|
-
とい
|
|
14
|
+
そのままやればいいかと思います。
|
|
15
|
-
ランダムアクセスが苦手なものを使うわけだから。どうしてもバブルソートで行うなら、「**リストからデータを取り出して、一旦配列にコピー。その配列をバブルソートで整列させて、元のリストに戻す。**」と言う作業をしないといけません。
|
|
16
15
|
|
|
17
|
-
|
|
16
|
+
majiponiさんがご指摘してくださったように、**先端から比較して交換すればいい**ですね。
|
|
18
|
-
で管理したほうがいいです。
|
|
19
17
|
|
|
18
|
+
たとえば an = { 3, 2, 6, 1 } であれば、まず先端である 3 のところにポインタを設定し、
|
|
19
|
+
その次の値と比較。 ポインタを pとし、条件式を``p->num > p->num + 1``とすると 3 > 2 となり、条件を満たしますから、
|
|
20
|
+
さらに別の、格納されているデータの型、つまり上記の場合はint型の変数またはポインタを用いて入れ替える。
|
|
20
|
-
|
|
21
|
+
そうすると an = { 2, 3, 6, 1 } となる。ポインタをずらして( p + 1 )、3 と 6 も同様にする。
|
|
22
|
+
…とやると、an = { 2, 3, 1, 6 } となるはずです。これで最大値 6 が確定。
|
|
21
|
-
|
|
23
|
+
また先端に戻って 2 と 3を比較。3と1を比較…とやり、要素数分の-1した回数行えば結果的にソートされますね。
|
|
24
|
+
(後から考えてやっとわかった…)
|
|
22
25
|
|
|
23
|
-
|
|
26
|
+
あるいはdodox86さんがご指摘してくださったように、**ポインタを格納するための配列を用いて行う**方法もありますね。
|
|
27
|
+
(流石にこれはまったく気づかなかった…)
|
|
24
28
|
|
|
25
|
-
これを追加するときに行う。一応リスト構造は走査するためのポインタ(C++でいうiterator)がその位置にあって、行ったり来たりすることを考慮しないのならO(1)です。つまりどこに挿入しようと常に一定の時間しかかからないです。データ量がどんなに大きくとも。(ただし「どこに挿入するか」とかのチェックは考慮していない)
|
|
26
29
|
|
|
30
|
+
|