ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

تحلیل الگوریتم Insertion Sort مرتب سازی درجی

 
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 31, 2010 1:41 pm    Post subject: تحلیل الگوریتم Insertion Sort مرتب سازی درجی Reply with quote

Insertion-Sort(A)
for j=2 to len(A)
  do key=A[j]
    i=j-1
    while(i>0 and A[i]>key)
     do A[i+1]=A[i]
        i=i-1
    A[i+1]=key   
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 31, 2010 2:00 pm    Post subject: Reply with quote

در این الگوریتم ابتدا کلید را مشخص می کنیم . این کار توسط کپی برداری A[j] در متغیر key انجام می شود.
پس از این کار در ادامه الگوریتم باید key را در جایگاه مناسبی از زیر آرایه مرتب شده که تا j-1 است قرار دهیم.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 31, 2010 2:11 pm    Post subject: Reply with quote

همیشه سعی کنید الگوریتم ها را با یک مثال درخور یادبگیرید.
الگوریتم مرتب سازی درجی را می توان به یک دسته کارت شبیه کرد که این کارت ها روی میز ریخته شده اند . در دست چپ شما یک کارت وجود دارد.
با دست راست یک کارت از روی میز بر می دارید (key) و آن را در دست چپ در جایگاه مناسب قرار می دهید . برای اینکه جایگاه کارت را چک کنید از راست به چپ کارت ها را با چشم مرور کنید تا جای واقعی کارتی که در دست راست دارید را پیدا کنید.
بنابراین همیشه کارت هایی که در دست چپ دارید مرتب هستند.
در دست راست شما همیشه key یا همان ایندکس j قرار دارد.
در دست چپ شما زیرآرایه 1 تا j-1 قرار دارد. حلقه داخلی while روی دست چپ شما عمل می کند.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 31, 2010 4:01 pm    Post subject: Reply with quote

این الگوریتم در بدترین حالت و حالت متوسط پیچیدگی n به توان 2 دارد و در بهترین حالت Best Case پیچیدگی n دارد.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum