ჩასმულის დახარისხება

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

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

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

მასივების ტერმინოლოგიით, წარმოიდგინეთ, რომ ქვემასივი ინდექს 0-იდან ინდექს $5$‍-მდე უკვე სორტირებულია და ჩვენ გვინდა, რომ ამ სორტირებულ ქვემასივში ჩავსვათ ელემენტი, რომელიც ახლა მდებარეობს ინდექს 6-ზე, რათა ქვემასივი ინდექს 0-იდან ინდექს 6-მდე იყოს სორტირებული. აი, როგორ ვიწყებთ:

და, აი, როგორ უნდა გამოიყურებოდეს ქვემასივი, როცა მოვრჩებით:

მე-6 პოზიციაზე მყოფი ელემენტის მის მარცხნივ არსებულ ქვემასივში ჩასასმელად ჩვენ განმეორებითად ვადარებთ მას მის მარცხნივ მყოფ ელემენტებს (გადავუყვებით მარჯვნიდან მარცხნივ). მოდით, მე-6 პოზიციაზე მყოფ ელემენტს დავარქვათ გასაღები. ყოველ ჯერზე, როცა ვხედავთ, რომ გასაღები არის მის მარცხნივ მყოფ ელემენტზე ნაკლები, ჩვენ ამ ელემენტს გადმოვაცურებთ ერთი პოზიციით მარჯვნივ, რადგან ვიცით, რომ გასაღები უნდა მოხვდეს ამ ელემენტის მარცხნივ. ამ იდეის ასამუშავებლად ორი რამის გაკეთება გვჭირდება: უნდა გვქონდეს გადმოცურების ოპერაცია, რომელიც ელემენტს ერთი პოზიციით მარჯვნივ გადმოაცურებს და გასაღების მნიშვნელობა უნდა შევინახოთ ცალკე გამოყოფილ ადგილზე (რათა მას არ გადაეწეროს მის მარცხნივ მყოფი პირველი ელემენტის მნიშვნელობა). ჩვენს მაგალითში მე-6 პოზიციაზე მყოფი ელემენტი შევინახოთ ცვლადში, სახელად key:

ახლა key-ს ვადარებთ ელემენტს მე-5 პოზიციაზე. ვხედავთ, რომ key (5) არის ნაკლები, ვიდრე მე-5 პოზიციაზე მყოფი ელემენტი (13), ასე რომ, ამ ელემენტს გადმოვაცურებთ მე-6 პოზიციაზე.

შევნიშნოთ, რომ გადმოცურების ოპერაცია უბრალოდ გადმოწერს ელემენტს ერთი პოზიციით მარჯვნივ. შემდეგში, key-ს ვადარებთ მე-4 პოზიციაზე მყოფ ელემენტს 4. ვხედავთ, რომ key (5) არის ნაკლები, ვიდრე ელემენტი მე-4 პოზიციაზე (10) და ამ ელემენტს გადმოვაცურებთ:

ახლა key-ს ვადარებთ მე-3 პოზიციაზე მყოფ ელემენტს და ამ ელემენტს გადმოვაცურებთ:

იგივე ხდება მე-2 პოზიციაზე მყოფი ელემენტის შემთხვევაშიც:

ახლა მოვდივართ პირველ პოზიციაზე მყოფ ელემენტთან, რომლის მნიშვნელობაა 3. ეს ელემენტი ნაკლებია key-ზე და ამიტომ მას არ გადმოვაცურებთ. სანაცვლოდ, key-ს ვსვამთ ამ ელემენტის მარჯვენა პირველივე პოზიციაზე (ანუ მე-2 პოზიციაზე), ამ პოზიციაზე მყოფი წინა ელემენტი წინა ნაბიჯში გადმოვაცურეთ ერთი პოზიციით მარჯვნივ. შედეგად ქვემასივი ინდექს 0-იდან ინდექს 6-მდე გახდა სორტირებული:

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

ვინაიდან ქვემასივი, რომელიც მხოლოდ ინდექს 0-ს შეიცავს, არის ჩვენი საწყისი სორტირებული ქვემასივი, პირველი გასაღები არის ინდექსი 1. (სორტირებულ ქვემასივს გაჩვენებთ წითლად, გასაღებს ყვითლად, ხოლო მასივის ჯერ კიდევ დასასორტირებელ ნაწილს — ლურჯად.) ვსვამთ გასაღებს მის მარცხნივ მყოფ სორტირებულ ქვემასივში:

ახლა სორტირებული ქვემასივი არის ინდექს 0-იდან ინდექს 1-მდე და ახალი გასაღები არის ინდექსი 2. ჩვენ ვსვამთ მას მის მარცხნივ მყოფ სორტირებულ ქვემასივში:

ვაგრძელებთ, თითოეულ ელემენტს მორიგეობით განვიხილავთ გასაღებად და ვსვამთ მას მის მარცხნივ მყოფ სორტირებულ ქვემასივში:

როგორც კი მასივის ყველაზე მარჯვენა ელემენტს ჩავსვამთ, მთელი მასივი დასორტირებული გვექნება:

ერთი-ორი სიტუაცია, რომელიც ჩვენს მაგალითში შეგვხვდა, უფრო მეტ ყურადღებას საჭიროებს: როდესაც ჩასასმელი გასაღები არის მის მარცხნივ მყოფ ყველა ელემენტზე ნაკლები (როგორც 2 და 3 გასაღებები ჩავსვით) და როდესაც ის არის უფრო მეტი ან ტოლი, ვიდრე მის მარცხნივ მყოფი ყველა ელემენტი (როგორც მაშინ, როცა ჩავსვით გასაღები 13). პირველ შემთხვევაში გასაღების მარცხენა ქვემასივში მყოფი ყველა ელემენტი გადაცურდება ერთი პოზიციით მარჯვნივ და უნდა გავჩერდეთ, როგორც კი მასივის მარცხენა ბოლოში გავალთ. მეორე შემთხვევაში პირველად, როცა გასაღებს ვადარებთ მის მარცხნივ მყოფ ელემენტს, ვარკვევთ, რომ გასაღები უკვე არის მის სწორ ადგილზე მის მარცხნივ მყოფ ყველა ელემენტთან მიმართებაში; არცერთი ელემენტი არ გადმოცურდება და გასაღები ჩაისმება ისევ იმ ადგილზე, რომლიდანაც დაიწყო.

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

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.