მარტივი სორტირებები

დალაგებული მონაცემი ხსნის გზას ორობითი ძებნისკენ, ორი მაჩვენებლისკენ და დუბლიკატების მარტივი პოვნისკენ. სამ მარტივ სორტირებაზე ყველა პროგრამისტი სწავლობს, რას ნიშნავს „O(n²)“ პრაქტიკაში.

★ ლექცია: sorting_insertion · ზაზა გამეზარდაშვილი▶ ვიდეო დამწყები⏱ 10 წთ

←ეყრდნობა

1მასივები და დინამიური მასივებიყველა მარტივი სორტირება ელემენტებს ადგილზე ცვლის ერთი მასივის შიგნით.0სირთულე და ზრდის ტემპიორ ჩადგმულ ციკლში შედარებების დათვლა აჩვენებს, რატომ არის ეს სორტირებები O(n²).

გზას უხსნის→

2შერწყმით სორტირება: დაყავი და იბატონესამუშაოს შუაზე გაყოფა არის ის, რაც მარტივი სორტირებების O(n²)-ს ამარცხებს.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ბუშტულებრივი სორტირება: მეზობლების გაცვლა

გაიარე მასივი და შეადარე მეზობლების ყოველი წყვილი. თუ რიგი არასწორია, გაცვალე.

ერთი სრული გავლის შემდეგ უდიდესი მნიშვნელობა ბოლომდეა მიტანილი, როგორც ბუშტი, რომელიც ზედაპირზე ამოდის. ის უკვე საბოლოო ადგილზეა, ამიტომ შემდეგი გავლა ერთი ბიჯით ადრე შეიძლება გაჩერდეს.

ინვარიანტი: k-ე გავლის შემდეგ ბოლო k პოზიცია k უდიდეს მნიშვნელობას შეიცავს, დალაგებულად. გაიმეორე n − 1 გავლა და ყველაფერი დალაგდება. თუ გავლაში არცერთი გაცვლა არ მოხდა, მასივი უკვე დალაგებულია და შეიძლება გაჩერდე; ამის გამო ბუშტულებრივი სორტირება დალაგებულ შემავალ მონაცემებზე O(n)-ია.

02არჩევითი სორტირება: აირჩიე მინიმუმი

მარცხნივ შეინარჩუნე დალაგებული პრეფიქსი. ყოველ რაუნდში დაასკანერე დაულაგებელი ნაწილი, იპოვე მისი მინიმუმი და გაცვალე დაულაგებელი ნაწილის პირველ ელემენტთან. დალაგებული პრეფიქსი ერთით იზრდება.

არჩევითი სორტირება ყოველთვის დაახლოებით n²/2 შედარებას აკეთებს, დალაგებულ შემავალ მონაცემებზეც კი: მინიმუმში დასარწმუნებლად ბოლომდე უნდა დაასკანეროს. მისი ერთადერთი უპირატესობა ისაა, რომ მაქსიმუმ n − 1 გაცვლას აკეთებს, რაც მხოლოდ მაშინაა მნიშვნელოვანი, როცა ჩაწერა ძალიან ძვირია.

ის არ არის სტაბილური: შორ მანძილზე გაცვლამ ელემენტი ტოლ ელემენტზე შეიძლება გადაახტუნოს.

03ჩასმით სორტირება: როგორც კარტის დალაგება ხელში

აიღე შემდეგი ელემენტი და მარცხნივ შეაცურე დალაგებულ ნაწილში: ყოველი დიდი მნიშვნელობა ერთი ბიჯით მარჯვნივ ინაცვლებს, სანამ ცარიელი ადგილი სწორ პოზიციაზე არ აღმოჩნდება.

უარეს შემთხვევაში (უკუღმა დალაგებული შემავალი მონაცემები) ყოველი ელემენტი ყველა წინაზე გადადის: O(n²). მაგრამ თითქმის დალაგებულ მონაცემზე ყოველი ელემენტი ცოტას მოძრაობს და ჩასმით სორტირება დაახლოებით O(n + ინვერსიები)-ში მუშაობს, წრფივთან ახლოს.

ამიტომ იყენებს მას რეალური ბიბლიოთეკები: std::sort და Python-ის Timsort პატარა ნაწილებისთვის (std::sort-ში დაახლოებით 16 ელემენტი, Timsort-ში 32-დან 64-მდე) ჩასმით სორტირებაზე გადადის, სადაც მისი პატარა მუდმივა ყველას ჯობნის. ის ასევე სტაბილურია და ადგილზე ალაგებს.

04რატომაა O(n²) დასამარცხებელი ზღვარი

სამივე სორტირება რიგს ასწორებს ელემენტების მცირე მანძილზე გადაადგილებით. უკუღმა დალაგებულ მასივს დაახლოებით n²/2 არასწორ რიგში მყოფი წყვილი (ინვერსია) აქვს, მეზობლების გაცვლა კი ერთ გაცვლაზე მხოლოდ ერთ ინვერსიას აქრობს. ამიტომ „მეზობლების გაცვლის“ ნებისმიერ მეთოდს უარეს შემთხვევაში O(n²) სამუშაო სჭირდება.

n = 1000-ისთვის ეს ნორმალურია. n = 10⁵-ისთვის კი დაახლოებით 5·10⁹ ბიჯია: ზედმეტად ნელი. უკეთესი რომ იყოს, ალგორითმმა ელემენტები ერთ ბიჯზე შორს უნდა გადაიტანოს, და ზუსტად ამას აკეთებს შერწყმითი და სწრაფი სორტირება, O(n log n)-ს აღწევენ.

პრაქტიკაში ამ სამს იშვიათად დაწერ ხელით, მაგრამ მათი იდეები ბრუნდება: ბუშტის ინვარიანტი, არჩევითის „იპოვე მინიმუმი“ და დალაგებულ ნაწილში ჩასმა.

ფასი ერთი შეხედვით

ბუშტულებრივი (უარესი / დალაგებული)O(n²) / O(n)

არჩევითი (ყოველთვის)O(n²)

ჩასმით (უარესი / თითქმის დალაგებული)O(n²) / ≈O(n)

დამატებითი მეხსიერებაO(1)

დაიმახსოვრე

ბუშტულებრივი, არჩევითი და ჩასმით სორტირება უარეს შემთხვევაში O(n²) ღირს, რადგან ელემენტებს მცირე მანძილზე აადგილებენ.
თითოეული ინარჩუნებს ინვარიანტს: დალაგებულ ნაწილს, რომელიც ყოველ რაუნდში ერთით იზრდება.
ჩასმით სორტირება სწრაფია თითქმის დალაგებულ ან პატარა მასივებზე, ამიტომ მას რეალური ბიბლიოთეკები დღემდე იყენებს.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე, როგორ იზრდება დალაგებული სუფიქსი ყოველი გავლის შემდეგ ერთით. მერე ალგორითმის ველში აირჩიე selection ან insertion და გაუშვი იგივე რიცხვები: დათვალე, რამდენი გაცვლა სჭირდება თითოეულს. სცადე უკვე დალაგებული შემავალი მონაცემებიც.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ბუშტულებრივი სორტირება

შედარებადალაგებული სუფიქსი

ვალაგებთ 8 ელემენტს. ყოველი გავლა დარჩენილთაგან უდიდეს მნიშვნელობას ბოლოში „აბუშტებს“.

ფსევდოკოდი

 1 for i in 0..n-2:            // passes 2   for j in 0..n-2-i: 3     if a[j] <= a[j+1]: keep order 4     else: swap(a[j], a[j+1]) 5   // largest of the pass has "bubbled" to the end 6 // selection sort 7 for i in 0..n-2: 8   m = i                // smallest seen so far 9   for j in i+1..n-1: if a[j] < a[m]: m = j10   swap(a[i], a[m])     // a[i] is final11 // insertion sort12 for i in 1..n-1:13   key = a[i]; j = i-114   while j >= 0 and a[j] > key: a[j+1] = a[j]; j--15   a[j+1] = key         // a[0..i] is sorted

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

ბუშტულებრივი სორტირების პირველი გავლის შემდეგ [5, 1, 4, 2, 8, 3]-ზე, როგორია მასივი?

№2

მონაცემი უკვე დალაგებულია, გარდა ბოლოში მყოფი რამდენიმე ელემენტისა. რომელი მარტივი სორტირება ჯდება საუკეთესოდ?

№3

რატომ უნდა იყოს O(n²) უარეს შემთხვევაში ნებისმიერი სორტირება, რომელიც მხოლოდ მეზობლებს ცვლის?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeHeight Checker დამწყები↗LeetCodeSquares of a Sorted Array დამწყები↗LeetCodeInsertion Sort List საშუალო↗LeetCodeSort Colors საშუალო↗