الگوریتم مرتب سازی حبابی

[pc_helper]

سلام
چطور می شه با دست بردن در کد مرتب سازی حبابی الگوریتم آنرا به نوع خطی تغییر داد یعنی از مرتبه و اوردر خطی بشود؟
کد رو دارم:



#include <stdio.h>
#include <iostream.h>
void bubbleSort(int *array,int length)//Bubble sort function
{
int i,j;
for(i=0;i<10;i++)
{
for(j=0;j<i;j++)
{
if(array[i]>array[j])
{
int temp=array[i]; //swap
array[i]=array[j];
array[j]=temp;
}
}
}
}
void printElements(int *array,int length) //print array elements
{
int i=0;
for(i=0;i<10;i++)
cout<<array[i]<<endl;
}

void main()
{
int a[]={9,6,5,23,2,6,2,7,1,8}; // array to sort
bubbleSort(a,10); //call to bubble sort
printElements(a,10); // print elements
}

[m.abbasi.kia]

با سلام خدمت شما دوست عزیز
این کار امکان ندارد و در بهترین حالت یه الگوریتم مرتب سازی از مرتبه n log n که کمتر از این نمیشه.
مثلا سورت ادغامی یا سورت سریع که در بهترین حالت n log n هستن

[manager]

به هیچ طریق نمی تونید این کار رو بکنید. ثابت می شود که هر نوع الگوریتم مرتب سازی از نوع مقایسه ای حداقل به Ω(nlogn) مقایسه نیاز دارد زیرا ارتفاع درخت دودوئی تصمیم ترتیب عناصر برابر log(2n!-1) است که با تقریب استرلینگ می توان به عدد nlogn دست پیدا کرد. این درخت دارای n! برگ است.

[pc_helper]

سلام

ببینید با محاسبه دفعات اجرا می توانیم به دست بیاریم که الگوریتم مرتب سازی حبابی از مرتبه n به توان 2 است، حالا می خواهیم طوری این الگوریتم را تغییر بدهیم که برای بهترین حالت order آن خطی بشود و این باید شدنی باشد، ولی من در کدنویسی ضعف دارم و چون می دونم افراد متخصص و با معلوملاتی در این انجمن هستند به همین دلیل این سوال را در اینجا مطرح کردم تا بهم کمک کنند.

[whitehat]

دوست عزیز، با شرایطی خاص می توان اجرای این الگوریتم را حتی به (1)O رساند، ولی با اجرای کد در حالت تک پردازنده ای شما پیچیدگی به شکل خطی نمی توانید داشته باشید.برای اینکه به حالت خطی برسید شما باید بیش از یک پردازنده داشته باشید. شما می توانید برای اطلاعات بیشتر به یکی از کتابهای الگوریتم های موازی مراجعه کنید
موفق باشید

[manager]

دوست عزیز، با شرایطی خاص می توان اجرای این الگوریتم را حتی به (1)O رساند، ولی با اجرای کد در حالت تک پردازنده ای شما پیچیدگی به شکل خطی نمی توانید داشته باشید.برای اینکه به حالت خطی برسید شما باید بیش از یک پردازنده داشته باشید. ...
جسارت نشه جناب آقای WhitehatT، پردازنده بیشتر زمان مجانبی الگوریتم رو که تغییر نمی ده !!! می ده ؟
به نظرم مثل این می مونه که بگیم این یک دیگ است اگر یک نفر با قاشق شروع کنه به خردن محتویاتش و یک بشقاب است اگر صد نفر همزمان باهم شروع کنند قاشق قاشق از دیگ بخورن !! به نظرم دیگ دیگه دیگه !!! :لبخندساده:

[whitehat]

من منظورم الگوریتم مرتب سازی حبابی است، نه کدی که دوستمان نوشتند. بهتره یک مثال بزنم :


For k = 0 to n-2
If k is even then
for i = 0 to (n/2)-1 do in parallel
If A[2i] > A[2i+1] then
Exchange A[2i] ↔ A[2i+1]
Else
for i = 0 to (n/2)-2 do in parallel
If A[2i+1] > A[2i+2] then
Exchange A[2i+1] ↔ A[2i+2]
Next k

کد بالا را بر روی 2 پردازنده اجرا می کنیم، در این صورت پیچیدگی زمانی این الگوریتم (که همان مرتب سازی حبابی است) در حالت موازی از درجه ( O(N است.(در صورتیکه لازم است بیشتر توضیح دهم؟)
در مورد مثالی که زدید باید بگم که آیا زمانی که یک نفر از دیگه شروع به خوردن می کند تا محتویات آن تمام شما با زمانی که 100 نفر از آن می خورند برابر است؟

[empoly]

با سلام
فکر می کنم :
همان طور که دوستان بیان کرده اند پیچیدگی زمانی الگوریتم مرتب سازی حبابی از مرتبه n به توان 2 است.
دوست عزیزمان بار اول بیان کرده اند که :


چطور می شه با دست بردن در کد مرتب سازی حبابی الگوریتم آنرا به نوع خطی تغییر داد یعنی از مرتبه و اوردر خطی بشود
ولی در بار دوم بیان کرده اند:


ببینید با محاسبه دفعات اجرا می توانیم به دست بیاریم که الگوریتم مرتب سازی حبابی از مرتبه n به توان 2 است، حالا می خواهیم طوری این الگوریتم را تغییر بدهیم که برای بهترین حالت order آن خطی بشود و این باید شدنی باشد
حالا تفاوت این دوتا در چیه؟!!!
نظر بنده این است که از اونجایی که پیچیدگی الگوریتم ها را برای حالت های مختلف نظیر بهترین حالت ، بدترین حالت و حالت متوسط به دست می آورند. منظور این سوال این هست که با ایجاد تغییر در کد داده شده کاری کنیم که پیچیدگی این الکوریتم در بهترین حالت از مرتبه خطی باشد. این است که مساله اصلا مربوط به اجرای موازی و.... نیست.
واما بهترین حالت برای الگوریتم حبابی چه هنگام به وجود می آید؟
جواب : وقتی که داده های ورودی از اول مرتب باشند (فرض کنید که می خواهیم آرایه را به صورت غیر نزولی مرتب کنبم یعنی از کوچک به بزرگ و آرایه داده شده به صورت int a[]={1 و2و3و4و5و6و7و8و9} باشد ) در این شرایط الگوریتم اصلاح شده باید از مرتبه n باشد.

void bubbleSort(int *array,int length)//Bubble sort function
{
int i,j;
bool IsSorted = false;
for(i=n;i>=0 && !IsSorted;i--)
{
IsSorted =true;
for(j=0;j<i;j++)
{
if(array[i]>array[j])
{
IsSorted =false;
int temp=array[i]; //swap
array[i]=array[j];
array[j]=temp;
}
}
}
}

امیدوارم منظورم را درست رسونده باشم.
موفق باشید.

[Hamid.Kad]

دقيقاً. و من فكر ميكنم ايشون منظورشون همون مرتب سازي حبابي هوشمند بود. يعني در صورتيكه بعد از پيمايش فهميد كه آرايه مرتب شده ديگه متوقف بشه و ديگه تا آخر ادامه نده. بديهيه كه در بهترين حالت اگه وروديمون مرتب باشه اين الگوريتم از مرتبه خطي خواهد بود