Insertion Sort

Insertion Sort მიმდევრობის დალაგების ერთ-ერთი ელემენტარული ალგორითმია. ალგორითმის მუშაობის პრინციპი მცირედით წააგავს უკვე განხილულ Selection Sort-ს, მაგრამ მათ შორის არის განსხვავება: Insertion Sort-ი ალგორითმი გარკვეული შემავალი მონაცემებისთვის უფრო სწრაფად მუშაობს, ვიდრე Selection Sort-ი.

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

Insertion

მოდით ახლა განვიხილოთ პრაქტიკულად.  გვაქვს მიმდევრობა 5 2 4 6 1 3.

პირველ იტერაციაზე პირველი ელემენტი 5-ია და მის მარცხნივ არ იქნება არცერთი ელემენტი, ამიტომ გადავდივართ ეგრევე მეორე იტერაციაზე.

მეორე იტერაციაზე, 2 ნაკლებია მის მარცხნივ მდებარე ელემენტზე , 5-ზე, ამიტომ 2-სა და 5-ს შევუცვალოთ ადგილები და გვექნება 2 5 4 6 1 3

შემდეგ იტერაციაზე უკვე ვიხილავთ 4-ს. 4-ი ნაკლებია მის მარცნივ მდებარე ელემენტზე, 5-ზე და ამ ორ ელემენტს ვუცვლით ადგილებს. 2 4 5 6 1 3 . ამით ეს იტერაცია არ დასრულებულა. ახლა ვამოწმებთ 4-ის მარცხნივ მდებარე ელემენტი მეტი ხომ არ არის 4-ზე. (ასე ჩავდივართ ბოლომდე). ამ შემთხვევაში 4-ის მარცხნივ მდებარე ელემენტი ნაკლებია 4-ზე და ეს იტერაცია სრულდება.

შემდეგ იტერაციაზე გადავდივართ 6-ზე. 6-ი არ არის ნაკლები  მის მარცხნივ მდებარე ელემენტზე და პირველ ელემენტამდე ჩასვლას აზრი არ აქვს, რადგან თუ 6-ის მარცხნივ არ არის მასზე მეტი ელემენტი, არც იმის მარცხნივ იქნება. მიმდევრობა დარჩება იგივე. 2 4 5 6 1 3

შემდეგ იტერაციაზე 1-ს ვიხილავთ. 1-ის ნაკლებია 6-ზე და ვუცვლით ადგილს. 2 4 5 1 6 3. ეს იტერაცია არ დასრულებულა. 1-ი კიდევ ნაკლებია მის მარცნივ მდებარე ელემენტზე და ასე ჩავალთ პირველ ელემენტამდე (რადგან 1 ყველა ელემენტზე ნაკლებია, რაც მის მარცხნივაა). ამ იტერაციის დასრულები შემდეგ ვიღებთ შემდეგ მიმდევრობას 1 2 4 5 6 3

დაგვრჩა ბოლო ელემენტი. 3-ს ვადარებთ მის მარცხნივ მდებარე ელემენტს. 3-ი ნაკლებია 6-ზე და ვუცვლით ადგილებს. 1 2 4 5 3 6. ამის მერე 3-ს კვლავ ვადარებთ მის მარცხნივ მდებარე ელემენტს 5-ს და კვლავ ნალებია, ამიტომ კიდევ გავუცვალოთ ადგილები. 1 2 4 3 5 6. ამის მერე კიდევ გავაგრძელოთ შედარებები და ვნახავთ, რომ 3 კვლავ ნაკლებია მის მარცხნივ მდებარე ელემენტზე და გავუცვალოთ ადგილები. 1 2 3 4 5 6. ამის მერე შევადაროთ 3-ი მის მარცხნივ მდებარე ელემენტს და ვნახავთ რომ აღარ არის ნაკლები 3-ი მის მარცნივ მდებარე ელემენტზე და აქ იტერაცია მთავრდება.

განვიხილოთ ალგორითმის მუშაობის დრო. თუ პარამეტრად შემომავალი მასივის დალაგებულია ზრდის მიხედვით, მაშინ გვიწევს N-1 შედარება და 0 გაცვლა. ხოლო თუ მასივი დალაგებულია კლების მიხედვით, მაშინ შედარებათა რიცხვი ტოლია N^2 / 2 და გაცვლების რიცხვიც ტოლია N^2 / 2. ანუ ალგორითმის მუშაობის დრო არის კვადრატული . მაგრამ თუ მასივი ნაწილობრივ დალაგებულია, მაშინ ალგორითმის მუშაობის დრო წრფივია, რადგან გაცვლების რაოდენობა არის ინვერსიების რაოდენობის ტოლი. შედარებების რაოდენობისთვის კიდე სამართლიანია ტოლობა

შედარებები = გაცვლები  + (N-1)

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

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s