مسابقه‌ی تصادفی

 
 
 مرتب كردن اعداد (مسابقه‌ي شماره‌ي 27)
مرتب كردن اعداد (مسابقه‌ي شماره‌ي 27)مسابقه كامپيوتر
در اين مسابقه از شما مي‌خواهيم كه بهترين روش «مرتب‌سازي دنباله‌اي از اعداد» را با توجه به شرايط داده شده به‌دست آوريد.

مرتب كردن اعداد




سؤال

دنباله‌اي از «اعداد حقيقي» متمايز داده شده است. در هر مرحله مي‌توان جاي دو عدد را در اين دنباله با هم عوض كرد. الگوريتمي ارائه دهيد كه با كم‌ترين تعداد استفاده از اين عمل، دنباله را مرتب كند.

1386/1/31لينک مستقيم

فرستنده :
romina HyperLink HyperLink 1386/10/1
مـتـن : man nemidonam in hobab az koja omade?
پاسـخ :رومينا جان!
جواب سؤالت رو بايد از «مولي» بپرسي.
ولي آيا شما هم راه‌حلي براي دوستات ارائه مي‌كني؟
منتظر جوابت هستيم.
موفق باشي!

فرستنده :
مولی HyperLink HyperLink 1386/10/1
مـتـن : سلام. این هم روش مرتب سازی حبابی
فرض کنید دنباله ای از اعداد داریم. ابتدا آنها را پشت سر هم می چینیم. سپس اولین داده را با دومی اش مقایسه می کنیم. بستگی به نوع مرتب سازی ( که می تواند نزولی و یا صعودی باشد) اگر داده اول بزرگتر یا کوچک تر از داده بعدی بود با آن جابجا شود. مثلا اگر مرتب سازی صعودی بود، اگر داده اول بزرگتر از داده دوم بود با آن جابجا می شود. سپس همین کار را برای داده های بعدی می کنیم. یعنی مثلا اگر داده دوم بزرگتر از داده سوم بود و یا داده سوم بزرگتر از داده چهارم، آنها را با هم عوض کند. وقتی کار تمام شد، بزرگترین داده در انتهای داده ها قرار می گیرد. حال همین عملیات را دوباره ولی برای داده های قبل از داده آخر انجام می دهیم. می توان ثابت کرد که تعداد دفعات این عملیات به ازای n داده، n-1 بار می باشد. اما این روش o(n^2) است و روش دیگری وجود دارد که با سرعت کمتر این کار را انجام می دهد که آن merge sort و یا quick sort می باشد که من در اینجا merge sort را توضیح میدهم. در این روش ابتدا داده ها را به دو قسمت برابر تقسیم می کنیم . حال دو حالت داریم: یا تعداد داده زوج داریم و یا فرد. اگر زوج بود که فبها المراد!! و اگر فرد بود می توان داده وسط را 2 بار حساب کرد یکی برای قسمت اول و دیگری برای قسمت دوم و در آخر یکی از آنها را حذف کرد. گفتم که داده ها به 2 قسمت تقسیم شده است. حال هر کدام از قسمت ها را با توجه به شرایط بالا به 2 قسمت مساوی تقسیم می کنیم. این کار را تا جایی ادامه می دهیم که به مجموعه داده هایی 2 تایی میرسیم. حال در این مجموعه های 2 تایی، بر اساس نوع مرتب سازی، اگر داده اول از دومی بزرگتر و یا از آن کوچکتر بود، با آن جابجا می شود. این کار برای تمامی زوج داده ها انجام می شود. سپس یک مرحله عقب می آییم یعنی داده های چهارتایی را در نظر می گیریم که هر کدام شامل 2 قسمت مرتب هستند. این داده ها را هم مرتب می کنیم و آنقدر به عقب بر می گردیم که تمام داده ها مرتب شده باشند. مزیت این روش آن است که
o(n log n) می باشد. امیدوارم متوجه شده باشید. متشکرم.
پاسـخ :تاريخ ارسال: 1386/6/15

فرستنده :
parynaz HyperLink HyperLink 1386/10/1
مـتـن : manam ba moli movafegham
پاسـخ :ايميل فرستنده: pa_r68@yahoo.com
تاريخ ارسال: 1386/5/28

فرستنده :
ناشناس HyperLink HyperLink 1386/5/22
مـتـن : manam ba nazare moli ovafegham
پاسـخ : دوست عزيزي!
اگر مايليد جواب سؤال مطرح شده را هم بگوييد تا مشكل مولي را حل كرده باشيد.

فرستنده :
معين HyperLink HyperLink 1386/4/17
مـتـن : به نظر منم بهترين راه (كوتاه ترين) جستجوي حباب است.

فرستنده :
ناشناس HyperLink HyperLink 1386/3/15
مـتـن : مي تونيد به کتاب کريتيو مراجعه کنيد و جوابهامو توي اونجا ببينيد به روش هاي مختلف:
insertation sort, bubble sort, quick sort, merge sort, ...
که بعضي ها O(n logn) وچرت تر هاشون O(n^2) هستن!!!!

فرستنده :
دوست مولی HyperLink HyperLink 1386/3/5
مـتـن : چرا جواب آقای مولی را نمی دهید که می گوید آیا می توان از روش جستجوی حبابی استفاده کرد یا خیر؟ اینجا 45 نفر دیگر هم با من موافقند.

فرستنده :
مولی HyperLink HyperLink 1386/2/28
مـتـن : می توان از روش جستجوی حبابی استفاده کرد که اگر n عدد داشته باشیم، حداکثر n-1 بار عمل جابجایی را انجام می دهیم. اگر درست گفته ام لطفا بنویسید تا الگوریتم را برایتان بفرستم.

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  4235
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  4235