سلام دوستان
من نیاز به یه الگوریتم مرتب سازی بسیار بسیار سریع دارم .
آیا سریعترین آنها Shellاست یا باز هم الگوریتم سریعتی هست . اگه کسی الگوریتم بهتری داره لطفاً راهنمائی کنه
ممنون
سلام دوستان
من نیاز به یه الگوریتم مرتب سازی بسیار بسیار سریع دارم .
آیا سریعترین آنها Shellاست یا باز هم الگوریتم سریعتی هست . اگه کسی الگوریتم بهتری داره لطفاً راهنمائی کنه
ممنون
این چه نوع آلگوریتمیه ؟ میشه در موردش توضیح بدبد؟آیا سریعترین آنها Shellاست
فکر کنم کوئیک سورت سریع ترین بود.
یه نمونه برنامه الگوریتم 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.
پیچیدگی الگوریتم های مرتب سازی می توانند بر اساس نوع قرارگیری داده ها می توانند تغییر داشته باشند. در حالتی که داده ها بسیار نا مرتب هستند الگوریتم Quick Sort دارای بهترین پیچیدگی یا N Log N می باشد .ولی اگر داده ها از قبل مرتب باشند پیچیدگی N^2 یعنی برابر همین Shell Sort می شود.اگر نمی دانید داده های شما دقیقا به چه نحو هستند باید از Sort هایی که حساس به نوع قرار گیری داده ها نمی باشد، استفاده کنید مانند Heap Sort و یا Merge Sort .من نیاز به یه الگوریتم مرتب سازی بسیار بسیار سریع دارم .
آیا سریعترین آنها Shellاست یا باز هم الگوریتم سریعتی هست . اگه کسی الگوریتم بهتری داره لطفاً راهنمائی کنه
که هر دوی این الگوریتم ها دارای پیچیدگی N Log N می باشند تنها پیچیدگی حافظه به میزان N به آنها اضافه می شود.
الگوریتم Shell Sort جزء طبقه بندی پیچیدگی N^2 قرار می گیرد که سرعت آن از الگوریتم های N Log N کمتر است.در ضمن باید علاوه بر پیچیدگی زمانی پیچیدگی مکان (حافظه مورد) نیاز را در نظر بگیرید.در صورتی که حافظه برای شما مهم نیست از Quick Sort یا Merge Sort استفاده کنید
برای اطلاعات بیشتر به لینک زیر مراجعه کنید و اگر سئوالی داشتید بپرسید
http://linux.wku.edu/~lamonml/algor/sort/sort.html
موفق باشید
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
البته تعداد عناصرتون هم می تونه مهم باشه ! مرتب سازی عناصر کم با زمان مصرفیO(NlogN)زیاد کارا نیست و در برخی موارد مرتب سازی درجی با زمان مصرفیO(N*N)کاراتر و سریع تر از الگوریتم هائی با پیچیدگی زمانیO(NlogN)است.
و البته همروند سازی (اجرا روی چند پردازنده ، یا چند ریسمانی) فرایندها در الگوریتم هم میتواند مهم باشد
اگه کسی الگوریتم غیر بازگشتی QuickSortرو داره بذاره
ممنون می شم که کمک کنید
#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;
}
}
تا اون جایی که من می دونم الگوریتمی وجود نداره که در بهترین حالت (منظورم بهترین حالت کلیه -حالت متوسط تازه اونم به صورت تقریبی- نه بهترین حالت جزیی) زمانی کمتر از nLOGn داشته باشه.نمونه اش هم Quick Sort و ...
حد پایین الگوریتم های مرتب سازی که در هر تکرار بیش از یک وارونگی رو حذف میکنن،(مثل MergerSort) در بدترین حالت "سقف لوگاریتم (!n)" یا همان nlogn-1.45n است و در حالت میانگین کف لوگاریتم !n یا همان nlogn-1.45nچرا وجود داره. مثلا Radix sort از درجه (O(nk هست که
الگوریتم هایی که در هرتکرار حداکثر یک وارونگی رو حذف کنن در بدترین حالت و حالت متوسط (n^2) هستن(مثل Exchange sort)
این به این معنیه که هیچ الگورییتم مرتب سازی با ویژگی بالا نمیتونید بسازید که در بدترین حالت و حالت متوسط از nlogn بهتر عمل کنه؛
اگه لیست به صورت صعودی مرتب شده باشه و توهم بخوای صعودی مرتب کنی؛ الگوریتم مرتب سازی درجی در n تکرار به جواب میرسه؛ یعنی از nlogn بهتر عمل میکنه.اما اگه از قبل به صورت نزولی مرتب شده باشه(بدترین حالت) در (n^2) تکرار به جواب میرسه ( مثل QuickSort)الگوریتمی وجود نداره که در بهترین حالت زمانی کمتر از nLOGn داشته باش
البته هیچوقت نمیتونین بگین که مثلا همیشه MergeSort بهتره،؛ چون بر اساس مقدار n مثلا n<=1000 ممکن است دیگری بهتر باشه.
دوست عزیز، بازهم حرفتون درست نیست. یه بار دیگه پست منو بخونید:
درسته که در اصل نمیشه (nLog(n رو با nk مقایسه کرد. اما معمولا nk خیلی کمتر میشه. حتی اینم در نظر داشته باشید که در Radix Sort با تغییر مبنا، میشه k رو کمتر هم کرد.چرا وجود داره. مثلا Radix sort از درجه (O(nk هست که در اون n تعداد اعداد و k طول متوسط اعداده. اون مطلبی هم که شما میگید فقط در مورد الگوریتمهایی که بر اساس مقایسه اعداد با همدیگه کار میکنند درسته
اینجا هم نگاه بندازین: http://en.wikipedia.org/wiki/Radix_sort
اگه برنامه کامل quicksort , merge sort,heap sort دارین (++C ) لطفا کمک کنید
فهرست الگوریتمهای مرتبسازی
در جدول 1، n تعداد دادهها و k تعداد دادهها با کلیدهای متفاوت است. ستونهای بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان میدهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود دادهها) است.
در جدول2 الگوریتمهایی را توضیح میدهد که به علت اجرای بسیار ضعیف و یا نیاز به سختافزار خاص، کاربرد زیادی ندارند.
اینم لینکش :
http://fa.wikipedia.org/wiki/%D8%A7%...A7%D8%B2%DB%8C