سریعترین الگوریتم مرتب سازی

[Saeid59_m]

سلام دوستان
من نیاز به یه الگوریتم مرتب سازی بسیار بسیار سریع دارم .

آیا سریعترین آنها Shell‌است یا باز هم الگوریتم سریعتی هست . اگه کسی الگوریتم بهتری داره لطفاً راهنمائی کنه
ممنون

[MNosouhi]

آیا سریعترین آنها Shell‌است
این چه نوع آلگوریتمیه ؟ میشه در موردش توضیح بدبد؟
فکر کنم کوئیک سورت سریع ترین بود.

[Saeid59_m]

یه نمونه برنامه الگوریتم Shell



Var
a:array [1..10000] of integer;
i,j,k,t,g:integer;
begin
g:=10000 div 2;
while (g>0) do begin
for i:=(g+1) to 10000 do begin
j:=i-g;
while (j>0) do begin
k:=j+g
if (a[j]<=a[k]) then j:=0 else begin
t:=a[j];
a[j]:=a[k];
a[k]:=t;
j:=j-g;
end;
end;
end;
g:=g div 2;
end ;
end.

[Saeid59_m]

آیا Quick Sort با Shell فرق می کنه ؟

[whitehat]

من نیاز به یه الگوریتم مرتب سازی بسیار بسیار سریع دارم .

آیا سریعترین آنها Shell‌است یا باز هم الگوریتم سریعتی هست . اگه کسی الگوریتم بهتری داره لطفاً راهنمائی کنه پیچیدگی الگوریتم های مرتب سازی می توانند بر اساس نوع قرارگیری داده ها می توانند تغییر داشته باشند. در حالتی که داده ها بسیار نا مرتب هستند الگوریتم Quick Sort دارای بهترین پیچیدگی یا N Log N می باشد .ولی اگر داده ها از قبل مرتب باشند پیچیدگی N^2 یعنی برابر همین Shell Sort می شود.اگر نمی دانید داده های شما دقیقا به چه نحو هستند باید از Sort هایی که حساس به نوع قرار گیری داده ها نمی باشد، استفاده کنید مانند Heap Sort و یا Merge Sort .
که هر دوی این الگوریتم ها دارای پیچیدگی N Log N می باشند تنها پیچیدگی حافظه به میزان N به آنها اضافه می شود.
الگوریتم Shell Sort جزء طبقه بندی پیچیدگی N^2 قرار می گیرد که سرعت آن از الگوریتم های N Log N کمتر است.در ضمن باید علاوه بر پیچیدگی زمانی پیچیدگی مکان (حافظه مورد) نیاز را در نظر بگیرید.در صورتی که حافظه برای شما مهم نیست از Quick Sort یا Merge Sort استفاده کنید
برای اطلاعات بیشتر به لینک زیر مراجعه کنید و اگر سئوالی داشتید بپرسید
http://linux.wku.edu/~lamonml/algor/sort/sort.html (http://linux.wku.edu/%7Elamonml/algor/sort/sort.html)
موفق باشید

[manager]

البته تعداد عناصرتون هم می تونه مهم باشه ! مرتب سازی عناصر کم با زمان مصرفی O(NlogN) زیاد کارا نیست و در برخی موارد مرتب سازی درجی با زمان مصرفی O(N*N) کاراتر و سریع تر از الگوریتم هائی با پیچیدگی زمانی O(NlogN) است.

[MM_Mofidi]

و البته همروند سازی (اجرا روی چند پردازنده ، یا چند ریسمانی) فرایندها در الگوریتم هم میتواند مهم باشد

[Saeid59_m]

اگه کسی الگوریتم غیر بازگشتی QuickSort‌رو داره بذاره

ممنون می شم که کمک کنید

[manager]

http://en.wikipedia.org/wiki/Image:Sorting_quicksort_anim.gifhttp://i18.tinypic.com/2pzwhsk.gif



#define MAXSTACK 128 /* Size of the stack */
void QuickSort(int *v, int tamanho){
int i, j;
struct limits_type newlimits;
struct stack_type stack;
stack.top = -1;
newlimits.left = 0;
newlimits.right = size-1;
push(&stack, &newlimits);
/* Repeat while there is some unsorted
subvector on the stack */
while(!empty(&stack)){
pop(&stack, &newlimits);
while(newlimits.left > newlimits.right){
/* process the next subvector */
j = Partition(v, newlimits.left,
newlimits.right);
if(j-newlimits.left > newlimits.right-j){
/* put lower subvector in the stack */
i = newlimits.right;
newlimits.right = j-1;
push(&stack, &newlimits);
/*process upper subvector */
newlimits.left = j+1;
newlimits.right = i;
}
else {
/* put upper subvector in the stack */
i = newlimits.left;
newlimits.left = j+1;
push(&stack, &newlimits);
/* process the lower subvector */
newlimits.left = i;
newlimits.right = j-1;
}/*end of if statement */
}/* end of while statement */
}/* end of while statement */
}/* end of QuickSort*/



static void Main(string [] args)
{
int [] T = new int [8];
Random r = new Random(( int )DateTime.Now.Millisecond);
for ( int i = 0 ; i < T.Length ; ++i )
{
T [i] = r.Next(1 ,20);
}
Print(T);
QuickSort(T ,0 ,T.Length);
Print(T);

Console.ReadKey();
}

static void QuickSort(int [] T ,int start,int end)
{
if ( start < end )
{
int l = Partition(T ,start ,end);
QuickSort(T ,start ,l );
QuickSort(T ,l + 1 ,end);
}
}

static void Print(int [] T)
{
Console.WriteLine("Array T : ");
for ( int i = 0 ; i < T.Length ; ++i )
Console.Write("\t{0}" ,T [i]);
Console.WriteLine();
}

static int Partition(int [] T ,int start,int end)
{
int m = T [start];
int i = start ,j = end;
while ( true )
{
do
{
++i;
} while ( i < end && m < T [i] );
do
{
--j;
} while ( j >= start && m > T [j] );
if ( i > j )
break;
Exchange(ref T [i] ,ref T [j]);
}
Exchange(ref T [start] ,ref T [j]);
return j;
}
static void Exchange(ref int a ,ref int b)
{
int temp = a;
a = b;
b = temp;
return;
}
}

[sjj]

تا اون جایی که من می دونم الگوریتمی وجود نداره که در بهترین حالت (منظورم بهترین حالت کلیه -حالت متوسط تازه اونم به صورت تقریبی- نه بهترین حالت جزیی) زمانی کمتر از nLOGn داشته باشه.نمونه اش هم Quick Sort و ...

[someCoder]

تا اون جایی که من می دونم الگوریتمی وجود نداره که در بهترین حالت زمانی کمتر از nLOGn داشته باشه.نمونه اش هم Quick Sort و ...

چرا وجود داره. مثلا Radix sort از درجه (O(nk هست که در اون n تعداد اعداد و k طول متوسط اعداده. اون مطلبی هم که شما میگید فقط در مورد الگوریتمهایی که بر اساس مقایسه اعداد با همدیگه کار میکنند درسته

[Developer Programmer]

چرا وجود داره. مثلا Radix sort از درجه (O(nk هست کهحد پایین الگوریتم های مرتب سازی که در هر تکرار بیش از یک وارونگی رو حذف میکنن،(مثل MergerSort) در بدترین حالت "سقف لوگاریتم (!n)" یا همان nlogn-1.45n است و در حالت میانگین کف لوگاریتم !n یا همان nlogn-1.45n
الگوریتم هایی که در هرتکرار حداکثر یک وارونگی رو حذف کنن در بدترین حالت و حالت متوسط (n^2) هستن(مثل Exchange sort)

این به این معنیه که هیچ الگورییتم مرتب سازی با ویژگی بالا نمیتونید بسازید که در بدترین حالت و حالت متوسط از nlogn بهتر عمل کنه؛


الگوریتمی وجود نداره که در بهترین حالت زمانی کمتر از nLOGn داشته باشاگه لیست به صورت صعودی مرتب شده باشه و توهم بخوای صعودی مرتب کنی؛ الگوریتم مرتب سازی درجی در n تکرار به جواب میرسه؛ یعنی از nlogn بهتر عمل میکنه.اما اگه از قبل به صورت نزولی مرتب شده باشه(بدترین حالت) در (n^2) تکرار به جواب میرسه ( مثل QuickSort)

البته هیچوقت نمیتونین بگین که مثلا همیشه MergeSort بهتره،؛ چون بر اساس مقدار n مثلا n<=1000 ممکن است دیگری بهتر باشه.

[someCoder]

تا اون جایی که من می دونم الگوریتمی وجود نداره که در بهترین حالت (منظورم بهترین حالت کلیه -حالت متوسط تازه اونم به صورت تقریبی- نه بهترین حالت جزیی) زمانی کمتر از nLOGn داشته باشه.نمونه اش هم Quick Sort و ...

دوست عزیز، بازهم حرفتون درست نیست. یه بار دیگه پست منو بخونید:

چرا وجود داره. مثلا Radix sort از درجه (O(nk هست که در اون n تعداد اعداد و k طول متوسط اعداده. اون مطلبی هم که شما میگید فقط در مورد الگوریتمهایی که بر اساس مقایسه اعداد با همدیگه کار میکنند درسته

درسته که در اصل نمیشه (nLog(n رو با nk مقایسه کرد. اما معمولا nk خیلی کمتر میشه. حتی اینم در نظر داشته باشید که در Radix Sort با تغییر مبنا، میشه k رو کمتر هم کرد.

اینجا هم نگاه بندازین: http://en.wikipedia.org/wiki/Radix_sort

[music]

اگه برنامه کامل quicksort , merge sort,heap sort دارین (++C ) لطفا کمک کنید

[Arian_61]

فهرست الگوریتم‌های مرتب‌سازی

در جدول 1، n تعداد داده‌ها و k تعداد داده‌ها با کلیدهای متفاوت است. ستون‌های بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان می‌دهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود داده‌ها) است.


در جدول2 الگوریتم‌هایی را توضیح می‌دهد که به علت اجرای بسیار ضعیف و یا نیاز به سخت‌افزار خاص، کاربرد زیادی ندارند.

اینم لینکش :
http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_% D9%85%D8%B1%D8%AA%D8%A8%E2%80%8C%D8%B3%D8%A7%D8%B2 %DB%8C