View Full Version : الگوریتمهای سورت
Sepidar
سه شنبه 25 فروردین 1383, 20:24 عصر
سلام
این الگوریتم Quick Sort است. کسی میتونه توضیح بده چه شکلی کار میکنه؟
PROCEDURE Quick;
PROCEDURE PartialSort(Left,Right:WORD);
VAR
L1,R1,I,J,K:WORD;
BEGIN
K:=(A[Left]+A[Right]) DIV 2;
I:=Left;
J:=Right;
REPEAT
WHILE A[I]<K DO
Inc(I,1);
WHILE K<A[J] DO
Dec(J,1);
IF I<=J THEN
BEGIN
Switch(A[I],A[J]);
Inc(I,1);
Dec(J,1);
END;
UNTIL I>J;
IF Left<J THEN
PartialSort(Left,J);
IF Right>I THEN
PartialSort(I,Right);
END;
BEGIN
PartialSort(1,MaxArray);
END;
Kambiz
سه شنبه 25 فروردین 1383, 23:03 عصر
در لینک زیر الگوریتم QuickSort به زیبایی شرح داده شده:
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
و در لینک زیر هم 16 الگوریتم مرتبسازی متفاوت قرار داره:
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
Sepidar
چهارشنبه 26 فروردین 1383, 00:07 صبح
ممنون :تشویق:
اگه حسش بود ترجمه میکنم میذارمش همینجا
رضا جاسبی
یک شنبه 25 بهمن 1383, 19:46 عصر
Sepidar عزیز که تو سایت دیدم خیلی خیلی کارت درسته ! نمی دونم که حسش رو پیدا کردی یا نه ! ولی برای بقیه می نویسم که :
الگوریتم Quick sort که به روش بازگشتی کار می کنه به این ترتیبه که از ابتدا و انتهای یک آرایه شروع می کنه و یک عدد رو مبنا می کنه و حرکت می کنه ! هر جا که در مسیر رو به جلو ( از ابتدا ) به عددی برخورد کرد که از مبنا بزرگتر بود متوقف می شه و بر عکس در مسیر رو به عقب ( جرکت از انتها ) هم عدد کوچکتر از مبنا ببینه متوقف می شه ! و بعد جای این دو تا رو عوض می کنه ! زمانی که این دو تا اشاره گر به هم برسند یعنی تمام عناصز قبل از این اشاره گر از مبنا کوچکتر و بعد از اشاره گر از مبنا بزرگترند. بنابراین آرایه به دو زیر آرایه تقسیم می شه و با همین روش هر دو زیر آرایه مرتب می شن. فقط اینجا برای من یک نکته مبهمه که چرا مبنا رو میانگین دو عدد ابتدا و انتها گرفته ؟ به نظر من باید مبنای ما عدد ابتدا باشد و جای این عدد دقیقا جایی است که دو اشاره گر به هم می رسند. در واقع به نظر من الگوریتم باید به این صورت باشد
PROCEDURE Quick;
PROCEDURE PartialSort(Left,Right:WORD);
VAR
L1,R1,I,J,K:WORD;
BEGIN
K:=A[Left]; { Reza Jasbi }
I:=Left+1;
J:=Right;
REPEAT
WHILE A[I]<K DO
Inc(I,1);
WHILE K<A[J] DO
Dec(J,1);
IF I<=J THEN
BEGIN
Switch(A[I],A[J]);
Inc(I,1);
Dec(J,1);
END;
UNTIL I>J;
Switch(A[Left],A[J]); { Reza Jasbi }
IF Left<J THEN
PartialSort(Left,J);
IF Right>I THEN
PartialSort(I,Right);
END;
BEGIN
PartialSort(1,MaxArray);
END;
mohs_158
پنج شنبه 13 اسفند 1383, 19:13 عصر
سلام
آقای جاسبی
شما حتی می تو نید به صورت تصادفی مبنا را انتخاب کنید!! :flower:
aspersica
یک شنبه 16 اسفند 1383, 22:25 عصر
سلام بچه ها!
من میگم چرا فقط به Quick Sort می پردازید!؟؟
بابا این همه Sort های دیگه!!
بیاین رو Oی اونهای دیگه صحبت کنیم!!
:sunglass: :wink:
فعلا!
Hamedm
جمعه 26 فروردین 1384, 19:03 عصر
سلام
میشه سورس VB این الگوریتمو اینجا بذارید.
vBulletin® v4.2.5, Copyright ©2000-1403, Jelsoft Enterprises Ltd.