安定ソート

安定なソート（stable sort）とは、 順序的に同等な要素が複数あったときに、その並びが元のまま保たれるもののことを言います。 ソート概要(アルゴリズムとデータ構造)
例えば、個人データを認識するための番号順に並べ、さらに組別に並べても、組ごとに認識番号順が保たれているソートです。
Ruby で。

class Person
  attr_reader :no,:klass

  def initialize(no,klass)
    @no    = no
    @klass = klass
  end
end

persons = [
   Person.new(15, 1),
   Person.new(1 , 2),
   Person.new(11, 2),
   Person.new(4 , 2),
   Person.new(17, 1),
   Person.new(7 , 2),
   Person.new(18, 1),
   Person.new(9 , 1),
   Person.new(10, 2),
   Person.new(6 , 1),
   Person.new(12, 1),
   Person.new(8 , 2),
   Person.new(13, 1),
   Person.new(3 , 2),
   Person.new(14, 1),
   Person.new(2 , 1),
   Person.new(16, 2),
   Person.new(5 , 1),
   Person.new(19, 1)]

sort メソッドは安定ソートではない。

persons.sort!{|a, b| a.no <=> b.no}
persons.each{|p| print "#{p.no} "}
#=>  1 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 

persons.sort!{|a, b| a.klass <=> b.klass}

# 組順に並べると元の番号順は保たれない。
puts("\n")
persons.each{|p| print "#{p.klass} "}
#=>  1 1  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  2 

puts("\n")
persons.each{|p| print "#{p.no} "}
#=> 19 2 18 17  5  6 15 14  9 13 12 10 11  8  7 16  4  3  1 

安定ソート

i = 0
p = persons.sort_by{|p| [p.no, i += 1] }
i = 0
p2 =p.sort_by{|p| [p.klass, i += 1] }

puts("\n")
p2.each{|p| print "#{p.klass} "}
#=>  1 1  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  2 

puts("\n")
p2.each{|p| print "#{p.no} "}
#=>  2 5  6  9 12 13 14 15 17 18 19  1  3  4  7  8 10 11 16 

Haskell の sortBy は安定ソート。

-- http://rosettacode.org/wiki/Sort_stability
-- http://en.wikipedia.org/wiki/Stable_sort#Stability
module Main where

import Data.List

data Person = Person{
        no    :: Integer,
        klass :: Integer } deriving (Eq,Read,Show)

persons = [
    Person{no=15,klass=1},
    Person{no=1 ,klass=2},
    Person{no=11,klass=2},
    Person{no=4 ,klass=2},
    Person{no=17,klass=1},
    Person{no=7 ,klass=2},
    Person{no=18,klass=1},
    Person{no=9 ,klass=1},
    Person{no=10,klass=2},
    Person{no=6 ,klass=1},
    Person{no=12,klass=1},
    Person{no=8 ,klass=2},
    Person{no=13,klass=1},
    Person{no=3 ,klass=2},
    Person{no=14,klass=1},
    Person{no=2 ,klass=1},
    Person{no=16,klass=2},
    Person{no=5 ,klass=1},
    Person{no=19,klass=1}]

ordNo :: Person -> Person -> Ordering
ordNo  a b | (no a) <= (no b) = LT
           | otherwise        = GT

ordKlass :: Person -> Person -> Ordering
ordKlass  a b | (klass a) <= (klass b) = LT
              | otherwise              = GT

ordByNo ::[Person]
ordByNo = sortBy ordNo persons

ordByKlass ::[Person]
ordByKlass = sortBy ordKlass ordByNo

main = do
  putStrLn $ show $ map klass ordByKlass
  -- => [1,1,1,1, 1, 1, 1, 1, 1, 1, 1,2,2,2,2,2, 2, 2, 2]
  putStrLn $ show $ map no    ordByKlass
  -- => [2,5,6,9,12,13,14,15,17,18,19,1,3,4,7,8,10,11,16]