Ruby sortメソッドで使用される<=>メソッドの比較処理が理解できない

Question

前提・実現したいこと

Rubyの配列をソートする「sort」メソッドで、
要素同士を比較するため「<=>」が使用されているとのことですが、
なぜ<=>が使用されることで、ソートされるのかが理解できません。

<=>の処理は、以下のようになることは理解しております。

1<=>2 =>-1
1<=>1 => 0
2<=>1 => 1

ただ、配列でsortを使用するとなった場合、以下の結果となると思います。
ここが理解できません。

[2,5,1,3,4,6].sort{|a,b| a<=>b}
=>[1,2,3,4,5,6]

私が認識している処理順としては、
1.　配列の[0]２と[1]５が、ぞれぞれa、bに入る
2.　5が大きいので、-1が帰る
3.　次に[2]1と[3]3が、ぞれぞれa、bに入る
4.　3が大きいので、-1が帰る
・・・

上記の認識だとしても、
[1]と[3]はどちらも-1で返されているから
sort順として、同じ順番になってしまうと思っています。

試したこと

リファレンスや、書籍を読みましたが
書かれてる内容を理解できませんでした。

Answer 1

上記の認識だとしても、

全く違います。

ソートをsort等専用機能を使わずに自分で書いてみると理解できるかと思います。
簡単なアルゴリズムとしては、
・1番目以降(つまり配列全体)で一番小さい要素を見つけ、1番目と交換、
・2番目以降で一番小さい要素を見つけ、2番目と交換
・3番目以降で一番小さい要素を見つけ、3番目と交換
・以下同様

配列の中で一番小さいものを<=>を使って求める方法は分かりますか？

Comments

[renessa]

回答ありがとうございます。
>配列の中で一番小さいものを<=>を使って求める方法
こちらの方法も分かっておりません。

[otn]

> こちらの方法も分かっておりません。

それは困りましたね。
・配列要素を単に１つずつ表示する方法はわかりますか？
・aとbの小さい方を<=>を使って判断して、それを表示する方法はわかりますか？

[renessa]

>・配列要素を単に１つずつ表示する方法はわかりますか？
こちらは以下のように取り出せると思います。

```
a = [1,2,3,4,5]
a.each do |i|
p i
end
```

>・aとbの小さい方を<=>を使って判断して、それを表示する方法はわかりますか？
ここは条件式までは書けますが、出力方法がわからないです
```
a = 10
b = 20
if (a <=> b) == -1
#不明
end
```

[otn]

その2つがわかるのであれば、
a の i 番目以降の最小値 min を求めるのは、
min = a[i]
a[i..-1] do |ai| ### a[i..-1]でなくてa[(i+1)..-1]でも良いが
if (ai <=> min) == -1
min = ai
end
end
というのは自分でも書けたはずですね。

これを使って、回答に書いたプログラムを作ってみましょう。
どのように<=>を使ってソートされるのかがわかると思います。

回答に書いた手順で、「小さい順に並ぶ」ことになるのはわかりますよね？
（１番小さい物を先頭に、残りで一番小さい物をその次に、以下同じ）

[renessa]

ありがとうございます。さっそく作って見たいと思いますが、
a[i..-1] do |ai|
上記、rangeメソッドの..-1とはなんでしょうか？
(i以上、-1以下？)

「..」の後に来る値が、プラスの値なら理解できますが、
..-1とマイナスの値となると、処理が理解できません。
※irbで以下実行しましたが、案の定そのままの値で返ります。

```
a = 10..-1
a.each do |i|
p i
end
=>10..-1
```

※何度も質問してしまい申し訳ありません、
　基礎が理解できていないため、上記のような質問になってしまっていると自負しています。
　やはり、もう一度基礎から学び直す必要がありそうです。

[otn]

> 上記、rangeメソッドの..-1とはなんでしょうか？
a[-1]の意味がわからないと言うことですよね？
配列要素の参照の基本を復習しましょう。

Answer 2

sortするには何らかの方法で a と b とを a,b とするのか b,a とするのかを決める必要があります。
大抵のsortでは大小比較しますから <=>が「sortのdefaultの比較方法」とされているわけです。
単純な大小比較では出来ない場合に sort{|a,b| a<=>b} の様に比較の仕方を定義します。
例えば英単語のsortで、大文字小文字全角を同じに扱いたいときは <=>ではだめなので sort{|a,b| a.半角変換してlower_case <=>b.半角変換してlower_case}みたいに。
あ、これも <=>か。
大小比較でないsortってパットは思いつかない。

Answer 3

その「認識している処理順」は多分間違っています。
端から順番に比較していくわけではありません。

Rubyのソートはクイックソートらしいので、

クイックソート | アルゴリズム [AOJ 10029][Ruby/Java] | 酒と涙とRubyとRailsと

こんな感じで処理が進んでいます。