Selection Sort

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

ვთქვათ, გვაქვს შემდეგი მიმდევრობა arr = { 7 , 9 , 6, 2, 8 }

i = 0 თვის    arr[0] = 7;  minimum { arr[0, arr.sizi()] } = 2 ; 7 > 2 ამიტომ გავუცვალოთ ამ ორ ელემენტს ადგილები და მივიღებთ  arr = { 2 , 9 , 6, 7, 8 }

i = 1 თვის arr[1] = 9 ; minimum { arr[1, arr.sizi()] } = 6 ; 9 >  6 ამიტომ გავუცვალოთ ამ ორ ელემენტს ადგილები და მივიღებთ arr = { 2 , 6 , 9 , 7, 8 }

i = 2 თვის arr[2] = 9 ; minimum { arr[2, arr.sizi()] } = 7 ; 9 > 7 ამიტომ გავუცვალოთ ამ ორ ელემენტს ადგილები და მივიღებთ arr = { 2 , 6 , 7 , 9 , 8 }

i = 3 თვის arr[3] = 9 ; minimum { arr[3, arr.sizi()] } = 8 ; 9 >  8 ამიტომ გავუცვალოთ ამ ორ ელემენტს ადგილები და მივიღებთ arr = { 2 , 6 , 7 , 8 , 9 }

i = 4 თვის arr[4] = 9 ; minimum { arr[4, arr.sizi()] } = 9 ; 9 ბოლო ელემენტია და არაფერზე მეტი არ იქნება და არც ნაკლები, რადგან ბოლო ელემენტი ედარება თავის თავს და ის ადგილს არ შეიცვლის.

selection-sort-1

ამ ალგორითმის მუშაობის დრო არის კვადრატული, რადგან მინიმალური ელემენტის პოვნას სჭირდება წრფივი დრო (ყველა ელემენტი უნდა გავიაროთ) ეს ხდება N -ჯერ (მასივის ელემენტების რაოდენობაჯერ). ეს მიახლოებითი შეფასებაა, ისე კი პირველ იტერაციაზე სრულდება 1 შედარება და მასივის N ელემენტის გავლა. ანუ მთლიანი მასივში მინიმუმის მოძებნა, შემდეგ იტერაციაზე უკვე N-1 სიგრძის მასივში ელემენტის მოძებნა და ა.შ. ანუ ჯამში იქნება 1 + 2 + 3 + 4 + . . . + N = N^2 / 2 ~ O (N^2)

 

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

 

 

One thought on “Selection Sort

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