სწრაფი სორტირება სტანდარტული ბიბლიოთეკების უმეტესობის პირველი არჩევანია: ადგილზე ალაგებს და პრაქტიკაში ჩვეულებრივ ყველაზე სწრაფია. მისი დაყოფის ბიჯი ცალკე ინსტრუმენტადაც გამოგადგება.
იდეა, მექანიზმი და ფასი.
სწრაფი სორტირება „დაყავი და იბატონეა“, ოღონდ სამუშაო რეკურსიამდე სრულდება და არა მის შემდეგ:
შერწყმა საჭირო არ არის: როცა ორივე მხარე დალაგდება, მთელი შუალედიც დალაგებულია, რადგან ყოველი მარცხენა ელემენტი ყოველ მარჯვენაზე უკვე მცირეა.
დაყოფა ერთი გავლით სრულდება ორი ინდექსით. მაჩვენებელი i „< საყრდენი“ ზონის ბოლოს აღნიშნავს; მაჩვენებელი j ჯერ უნახავ ელემენტებს სკანირებს.
ერთი გავლა, O(n) შედარება, დამატებითი მასივის გარეშე: სწრაფი სორტირება ადგილზე ალაგებს და მხოლოდ რეკურსიის სტეკს იყენებს.
ჰოარის დაყოფა (ორი ერთმანეთისკენ მოძრავი მაჩვენებელი) ნაკლებ გაცვლას აკეთებს და ბევრ ტოლ გასაღებს უკეთ უმკლავდება; სამმხრივი დაყოფა (<, =, >) საუკეთესოა, როცა ბევრი დუბლიკატია.
თუ საყრდენი შუასთან ახლოს ხვდება, ყოველი დაყოფა შუალედს დაახლოებით შუაზე ყოფს: log n დონე O(n) სამუშაოთი, O(n log n), ისევე როგორც შერწყმით სორტირებაში.
თუ საყრდენი ყოველთვის უმცირესი ან უდიდესია, ერთი მხარე ცარიელია, მეორეში კი n − 1 ელემენტია. რეკურსია n სიღრმის ჯაჭვად იქცევა და ჯამური სამუშაოა n + (n−1) + … + 1 = O(n²). „ბოლო ელემენტი საყრდენად“ წესით ეს უკვე დალაგებულ შემავალ მონაცემებზე ხდება, რაც რეალურ მონაცემებში ძალიან ხშირია.
გამოსავალია საყრდენის შემთხვევით არჩევა (ან სამის მედიანა). მაშინ ცუდი შემავალი მონაცემები აღარ არსებობს და მოსალოდნელი დრო ნებისმიერ შემავალ მონაცემებზე O(n log n)-ია. რეალური სორტირებები, მაგალითად introsort, რეკურსიის ზედმეტად გაღრმავებისას heapsort-ზეც გადადის.
მასივებზე პრაქტიკაში სწრაფი სორტირება იმარჯვებს: ადგილზე მუშაობს, მეხსიერებას მიმდევრობით კითხულობს და პატარა მუდმივები აქვს. შერწყმითი იმარჯვებს, როცა გჭირდება სტაბილურობა ან უარესი შემთხვევის მკაცრი გარანტია. სწრაფი სორტირება არ არის სტაბილური.
დაყოფის იდეა სხვა ამოცანასაც ხსნის. k-ე უმცირესი ელემენტის საპოვნელად ერთხელ დაყავი: თუ საყრდენი k ინდექსზე მოხვდა, მზადაა; თუ არა, რეკურსია მხოლოდ ერთ მხარეს. მოსალოდნელი სამუშაო n + n/2 + n/4 + … = O(n). ეს არის quickselect, ხელმისაწვდომი როგორც std::nth_element.
გამოიყენე მედიანისთვის, „top k“-სთვის და პროცენტილებისთვის, როცა მთელი მასივის დალაგება არ გჭირდება.
გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.
👀 რას უყურო: უყურე i-ს (მცირე ზონის ბოლო) და j-ს (სკანერი). ყოველი „დადგმა“ ერთ საყრდენს სამუდამოდ აფიქსირებს. სცადე 10 20 30 40 50 60 ცუდი შემთხვევის სანახავად.
1 quicksort(lo, hi): 2 pivot = a[hi]; i = lo 3 for j in lo..hi-1: compare a[j] with pivot 4 if a[j] < pivot: swap a[i],a[j]; i++ 5 swap a[i],a[hi] // pivot reaches final spot 6 recurse on [lo,i-1] and [i+1,hi]
სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.
რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.