PDA

View Full Version : الگوریتمهای سورت



Sepidar
سه شنبه 25 فروردین 1383, 19: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, 22: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
سه شنبه 25 فروردین 1383, 23:07 عصر
ممنون :تشویق:

اگه حسش بود ترجمه میکنم میذارمش همینجا

رضا جاسبی
یک شنبه 25 بهمن 1383, 18: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, 18:13 عصر
سلام
آقای جاسبی
شما حتی می تو نید به صورت تصادفی مبنا را انتخاب کنید!! :flower:

aspersica
یک شنبه 16 اسفند 1383, 21:25 عصر
سلام بچه ها!

من میگم چرا فقط به Quick Sort می پردازید!؟؟
بابا این همه Sort های دیگه!!

بیاین رو Oی اونهای دیگه صحبت کنیم!!

:sunglass: :wink:

فعلا!

Hamedm
جمعه 26 فروردین 1384, 18:03 عصر
سلام

میشه سورس VB این الگوریتمو اینجا بذارید.