შედარებაზე დაფუძნებული სორტირებები n log n-ს ვერასდროს აჯობებს. დათვლითი სორტირება კანონიერად „ატყუებს“: როცა გასაღებები პატარა მთელი რიცხვებია, საერთოდ არ ადარებს და წრფივ დროში ალაგებს.
იდეა, მექანიზმი და ფასი.
დავუშვათ, ყოველი მნიშვნელობა მთელი რიცხვია 0-დან k − 1-მდე, მაგალითად გამოცდის ქულები ან ასაკები. შექმენი k ზომის მასივი count, ყველა ნული. ერთხელ გაიარე შემავალი მონაცემები და ყოველი v-სთვის გააკეთე count[v]++.
[3, 6, 1, 3, 4, 1, 6, 3]-სთვის ეს იძლევა count = [0, 2, 0, 3, 1, 0, 2]: ორი 1, სამი 3, ერთი 4, ორი 6.
თუ მხოლოდ დალაგებული რიცხვები გჭირდება, უკვე მზად ხარ: თითო v ამოწერე count[v]-ჯერ. ორი მარტივი გავლა, O(n + k), და ელემენტებს შორის არცერთი შედარება.
ჩვეულებრივ ჩანაწერებს ალაგებ გასაღებით (ადამიანებს ასაკით), ამიტომ პოზიციები გჭირდება და არა მხოლოდ რაოდენობები.
count პრეფიქსულ ჯამად აქციე: count[v] ხდება „რამდენი გასაღებია ≤ v“. მაშინ v გასაღების ელემენტები გამოსავლის უჯრებს იკავებს count[v−1]-დან count[v] − 1-მდე. მაგალითში 3-ები 2, 3 და 4 უჯრებს იკავებს.
ახლა შემავალი მონაცემები მარჯვნიდან მარცხნივ გაიარე: v გასაღების ყოველი ელემენტისთვის შეამცირე count[v] და ელემენტი ჩასვი out[count[v]]-ში. მარჯვნიდან მარცხნივ გავლა ბოლო 3-ს ბოლო 3-ის უჯრაში სვამს, ამიტომ ტოლი გასაღებები შემავალი მონაცემების რიგს ინარჩუნებს: დათვლითი სორტირება სტაბილურია.
სწორედ ეს სტაბილურობა ამუშავებს თანრიგებით სორტირებას (radix sort): რიცხვები ჯერ ბოლო ციფრით დაალაგე, მერე წინა ციფრით და ა.შ., ყოველ ჯერზე სტაბილური დათვლითი სორტირებით.
ნებისმიერ სორტირებას, რომელიც რიგის შესახებ მხოლოდ ორი ელემენტის შედარებით იგებს, უარეს შემთხვევაში დაახლოებით n log n შედარება სჭირდება. შესაძლო რიგი n!-ია, და ყოველი კი/არა შედარება კანდიდატებს საუკეთესო შემთხვევაში ანახევრებს, ამიტომ საჭიროა log₂(n!) ≈ n log n კითხვა.
დათვლითი სორტირება ამ ზღვარს გვერდს უვლის, რადგან გასაღებებს მასივის ინდექსებად იყენებს, რასაც შედარებითი სორტირება ვერ აკეთებს.
ფასი არის k წევრი O(n + k) დროსა და მეხსიერებაში. ქულები 0..100 ან ასაკები 0..120 იდეალურია. 10⁹-მდე მნიშვნელობები, ტელეფონის ნომრები ან სტრიქონები არა: count მასივი უზარმაზარი იქნებოდა. მაშინ გამოიყენე ჩვეულებრივი O(n log n) სორტირება, ან radix sort, თუ გასაღებები ფიქსირებული ზომის მთელებია. სასარგებლო ხრიკი: თუ მნიშვნელობები დიდია, მაგრამ ცოტაა, ჯერ შეკუმშე ისინი (დაალაგე განსხვავებული მნიშვნელობები და თითო მისი რანგით შეცვალე).
ლექცია ვიდეოს სახით.
ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.
გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.
👀 რას უყურო: სამი ფაზა: დათვლა, პრეფიქსული ჯამი, განთავსება. ბოლო ფაზაში შენიშნე, რომ სკანირება მარჯვნიდან მარცხნივ მიდის და ყოველი count ერთით მცირდება.
| v | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| count | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 count occurrences of each value 0..k-1 2 prefix-sum count[] → count[v] = #(≤ v) 3 scan input right→left: out[--count[v]] = v 4 // zero comparisons between elements
სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.
რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.