Számjegyes rendezés (algoritmus)

A Programozás Wiki wikiből

A leszámláló rendezés kiterjesztése ,korábban lyukkártyarendező berendezésekben használták,de alkalmazható azonos d hosszúságú szavak,ugyanannyid számjegyből álló számok,dátumok esetén is.Elsőként a legkevésbé értékes számjeggyel kezdjük,majd a második legkevésbé értékessel,végül eljutunk a legértékesebb jegyig.A módszer stabilsága itt nagyon fontos,mert csak így érhető el a megfelelő számjegysorrend egy számon belül. Időigény:O(d(n+k)),ám ha d konstans és k=O(n),akkor lineáris idejű a rendezés.

 329    720    720    329
 457    355    329    355
 657    436    436    436
 839->  457->  839->  457
 436    657    355    657
 720    329    457    720
 355    839    657    839
          |     |     |

A számjegyes rendezés működése 7 darab 3 számjegyű számot tartalmazó lista esetén. Az első oszlop a bemenet.A többi oszlop a listát mutatja,az egyre értékesebb számjegyek alapján történő rendezések után.A függőleges nyilak ( | ) azt a számjegypozíciót mutatják, amelyikben az előző listát rendeztük és így az adott listát megkaptuk.