ალგორითმები და მონაცემთა სტრუქტურები (ალგორითმი) , საკონტროლო , ბილეთი N9

დაწერეთ SelectSort(A) ალგორითმი(იტერაციული ან რეკურსიული) , დაამტკიცეთ მისი სისწორე და შეაფასეთ ოპერაციების რაოდენობა უარეს შეთხვევაში .

SelectSort (A) 

სანამ A მიმდევრობა ცარიელი არ არის შეასრულე შემდეგი ოპერაციები :

იპოვე მინიმალური ელემენტი A სიმრავლეში , ამოშალე იქიდან და ჩართე B-ში ;

დააბრუნე  B ; 

სისწორის დამტკიცება :

როცა A სიმრავლე ერთ ელემენტიანია, მაშინ B სიმრავლეშიც იქნება ერთი ელემენტი და რა თქმა უნდა ეს სიმრავლე იქნება დალაგებული . ახლა განვიხილოთ შემთხვევა როცა A სიმრავლე არის n ელემენტიანი .  რადგან ყოველ ჯერზე ჩვენ ვირჩევთ მინიმალურ ელემენტს ამიტომ ჭეშმარიტი იქნება თუ დავწერთ a(1) <= a(2) ,= a(3) <= . . . <= a(n) სადაც ინდექსები აღნიშნავს ამოღების რიგითობას .  დავუშვათ რომ n -ზე ნაკლები ელემენტისთვის ალგორითმი სწორად იმუშავებს და B სიმრავლე იქნება დალაგებული. ამ დროს ბოლოს ამოღებული ელემენტის “ინდექსი” იქნება n-1 . ალგორითმის პირობიდან ვიცით რომ a(n-1) <= a(n) რადგან ეს ასეა , მაშინ B=(a(1),a(2), . . . , a(n-1), a(n) ) იქნება დალაგებული , ესე იგი ალგორითმი სწორად მუშაობს .

 

ოპერაციების რაოდენობა :

A სიმრავლეში მინიმალური ელემენტის პოვნას სჭირდება  c1*n ოპერაცია და ამოშლას  სჭირდება c2 ოპერაცია და იმის შემოწმებას A ცარიელია თუ არა სჭირდება ერთი ბიჯი.

T(SelectSort(A)) =  T(SelectSort(A-{A სიმრავლის მინიმალური ელემენტი}) + 1 +с1*n+с2 = . . . =T(SelectSort(0))+c1(n+(n-1)+(n-2)+. . . +1) + (c2+1)n =1+c1*((n(n+1))/2)+(c2+1)n = O(n^2) 

 

 

 

 

 

 

 

 

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