სწრაფი ჩასმის ალგორითმი / InsertFast

 InsertFast (a1,a2, . . . , a(n) , c )
{
if ( c <= a1 ) A = (c , a1,a2, . . . , a(n) ) ; return (A) ;
if ( c >= a(n) ) A = (a1,a2, . . . , a(n) , c ) ; return (A) ;
min = 1 ;
max = n;
while ( true )
{
i = (min+max) / 2;
if ( a(i)-1 <= c <= a(i) )
{
A = (a1, a2 , . . . , a(i)-1 , c , a(i), . . . , a(n) ) ;
return (A) ;
}
if ( a(i) <= c <= a(i)+1 )
{
A = (a1, a2 , . . . , a(i) , c , a(i)+1, . . . , a(n) ) ;
return (A) ;
}
if ( c > a(i) ) min = i ;
else max = i;
}
ბიჯების რაოდენობა :
T(InsertFast(A(n),c)) =9 + T(InsertFast(A(n/2),c) = . . . = 9*logn + T(0) + 8 (while-მდე 8 ბიჯი სრულდება) = O(logn) მუშაობის ზედა ზღვარი ლოგარითმულია . 
სისწორის დამტკიცება :
როცა მიმდევრობა ცარიელია , მაშინ ცარიელ მიმდევრობაში ჩაემატება ერთი ელემენტი და ამით ალგორითმი დასრულდება . დავუშვათ რომ ალგორითმი სწორად მუშაობს n-ზე ნაკლები ელემენტისთვის . როცა შესრულდება პირველი 8 ბიჟი ანუ while-მდე ყველა შემდეგ უკვე ციკლში ვანახევრებთ ინდექსს და ვამოწმებთ იქ თუ ჩაისმევა ელემენტი , როცა ეს ასე არ ხდება შემდეგ შუა ელემენტს ვადარებთ ჩასამატებელს და იმის მეტია თუ ნაკლებია ის შუა ელემენტზე იმის მიხედვით ვცვლით საზღვრებს , ანუ ვანახევრებთ მონაცემებს რაც იმას ნიშნავს რომ ალგორითმი სწორად მუშაობს , რადგან n-ზე ნაკლები მონაცემისთვის დაშვებით ვიცით რომ ალგორითმი სწორად მუშაობს .

4 thoughts on “სწრაფი ჩასმის ალგორითმი / InsertFast

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

    • მადლობა რჩევისთვი🙂 ალგორითმებზე წიგნი მეც მაქვს და როცა დრო მაქვს ვარჩევ ხოლმე ჩემთვის საინტერესო საკითხებს🙂 უბრალოდ ამითი ხალხსავ ვეხმარები🙂 მადლობა რჩევისთვის კდიევ ერთხელ და რომელ წიგნზე საუბრობ ისე ?🙂

      • ეს საუკეთესოა : Introduction to algorithms‎ – Thomas H. Cormen
        და ესეც კაია Algorithm Design Manual by Steven Skiena.
        ასევე ამეების მარტო სწავლასაც აზრი არ აქვს თუ პრაქტიკაშიც არ გამოიყენე და მაგისთვის ამოცანები აკეთე, აქ კაი რამეებია http://acm.timus.ru/ თუ გაინტერესებს რათქმაუნდა😀

      • კორმენის წიგნი მაქვს და კიდევ მაქვს ერთი წიგნი. მე ამას ვპოსტავ ხალხს რომ დავეხმარო იმიტომ .

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