PDA

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



gh_mohammady
سه شنبه 07 آذر 1391, 21:01 عصر
با سلام خدمت استاتید و کارشناسان گرامی ...
یک سوال شاید مبتدیانه ، آیا امکانش هست در برنامه نویسی سی شارپ بتونم الگوریتم مرتب سازی حبابی رو به صورت بازگشتی بنویسم ؟

plus
سه شنبه 07 آذر 1391, 21:26 عصر
اگه سوالتون در مورد نوشتن الگوریتم مرتب سازیه به صورت بازگشتی هست، تا اونجا که من یادمه با حلقه این الگوریتم حل میشد و نیازی با بازگشتی نبود البته وقتی با حلقه بشه به صورت بازگشتی هم میشه.
اگه سوالتو در مورد امکان نوشتن الگوریتم بازگشتی در سی شارپ هست که باید بگم بله.شما اگه این الگوریتم رو در زبان دیگه ای دارید توی #C هم میتونید بنویسینش.
اگه سوالتون در مورد تابع مرتب سازی حبابی به صورت آماده در #C هست، متدهای مرتب سازی در #C ازین الگوریتم استفاده نکردن.

gh_mohammady
چهارشنبه 08 آذر 1391, 17:29 عصر
از توجه شما سپاس گزارم ..
اما من عرض کردم می خوام این کارو اجام بدم یعنی الگوریتم حبابی رو به صورت بازگشتی در سی شارپ بنویسم ...
می شه نوشت ؟
می شه راهنماییم کنید؟

SEZAR.CO
چهارشنبه 08 آذر 1391, 17:45 عصر
دقیقا نفهمیدم چی گفتی
اگه میشه واضح تر بگو

gh_mohammady
چهارشنبه 08 آذر 1391, 18:29 عصر
چرا انقدر عجیب به نظر میاد ؟!!!!!!!!!!!!!!
یه الگوریتم برای مرتب سازی وجود داره که الگوریتم مرتب سازی حبابی هستش درسته ؟
این الگوریتم با for نوشته می شه درسته ؟
اگه من بخوام این کار رو توسط توابع بازگشتی بنویسم شدنیه ؟

roolinjax
چهارشنبه 08 آذر 1391, 20:42 عصر
سلام یه جورایی میشه گفت شدنی نیست.
چون اگه ساختار و عملکرد این الگوریتم رو با دقت بررسی کنیم می بینیم که داره در هر دور از حلقه عملیات جابجایی رو از خونه ی بالای آرایه انجام میده و به سمت پایین آرایه میره و در هر دور از حلقه ی بیرونی یکی از اعداد مرتب میشه
اما اگر بازگشتی بشه مسیر رو برعکس میره چون اول به سمت انتها حرکت میکنه و به کف تابع بازگشتی که خورد تازه شروع می کنه به انجام عمل مقایسه و جابجایی که نتیجه درستی رو برنمی گردونه.
خودم سخت فهمیدم چی گفتم ، امیدوارم شما آسون تر فهمیده باشید!!!!!!
کسی اگر فکر میکنه میشه الگوریتمش رو بذاره تا ما هم استفاده کنیم

plus
چهارشنبه 08 آذر 1391, 20:53 عصر
سلام یه جورایی میشه گفت شدنی نیست.
چون اگه ساختار و عملکرد این الگوریتم رو با دقت بررسی کنیم می بینیم که داره در هر دور از حلقه عملیات جابجایی رو از خونه ی بالای آرایه انجام میده و به سمت پایین آرایه میره و در هر دور از حلقه ی بیرونی یکی از اعداد مرتب میشه
اما اگر بازگشتی بشه مسیر رو برعکس میره چون اول به سمت انتها حرکت میکنه و به کف تابع بازگشتی که خورد تازه شروع می کنه به انجام عمل مقایسه و جابجایی که نتیجه درستی رو برنمی گردونه.
خودم سخت فهمیدم چی گفتم ، امیدوارم شما آسون تر فهمیده باشید!!!!!!
کسی اگر فکر میکنه میشه الگوریتمش رو بذاره تا ما هم استفاده کنیم

شما معمولیش روبگذار ببینیم میتونیم بازگشتیش کنیم یا نه.اگه اشتباه نکنم، یه اصلی بود که هر الگوریتمی که بازگشتی حل بشه با حلقه هم حل میشه و برعکس.

gh_mohammady
چهارشنبه 08 آذر 1391, 21:04 عصر
از کارشناسان محترم سپاس گزارم بابت همراهیشون
این کد معمولیش
int[] A = new int[10];
for(int i=1;i<A.Length;i++)
for(int j=0;j<A.Length-i;j++)
if (A[j] > A[j + 1])
{
int temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
}

SEZAR.CO
چهارشنبه 08 آذر 1391, 21:14 عصر
شرمنده من دانش اموز اول دبیرستانم و با با این اسم ها اشنا نیستم وگرنه کمکت می کردم:ناراحت:

plus
چهارشنبه 08 آذر 1391, 21:55 عصر
من این رو به صورت بازگشتی نوشتم ولی از نظر مفهومی همون دو تا حلقه است فقط ظاهرش به صورت بازگشتیه:



public Form1()
{
InitializeComponent();

int[] arr = new int[] { 10, 5, 2, 5, 11, 6 };
BubbleSort(arr);

}

private void BubbleSort<T>(T[] array) where T : IComparable
{
BubbleSort<T>(array, 1, 0, false);
}

private void BubbleSort<T>(T[] array, int i, int j, bool inner) where T : IComparable
{
if (i == array.Length) // End of outer loop index
return;

if (!inner)
{
BubbleSort<T>(array, i, 0, true);
}
else
{
if (j == array.Length - i) // End of inner loop index
{
i++;
BubbleSort(array, i, 0, false);
return;
}

if (((IComparable)array[j]).CompareTo((object)array[j+1]) == 1)
{
T temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
j++;
BubbleSort(array, i, j, inner);
}
}

gh_mohammady
چهارشنبه 08 آذر 1391, 22:26 عصر
ممنونم از راهنماییتون
من این کد رو داشتم
اما مفهوم این خطشو نمی فهمم
BubbleSort<T>(T[] array) where T : IComparable

gh_mohammady
چهارشنبه 08 آذر 1391, 22:29 عصر
البته فقط این که می گه <T> نمی فهمم یعنی چی ؟

plus
چهارشنبه 08 آذر 1391, 22:32 عصر
والا من اینو از خودم در آوردم نوشتم :-D شما از کجا داشتی نمیدونم. :-p
اون خطی که مشخص کردی مربوط به Template هاست.من کد رو جوری با استفاده از Template ها نوشتم که بشه آرایه از هر نوعی رو مرتب کرد.منتها وقتی شما از Template استفاده میکنی گاهی باید شروطی رو برای نوعی که استفاده شده بگذاری، شرطی که من گذشتم اینه که اون نوع باید از نوع IComparable باشه، یعنی مقایسه پذیر باشه تا بتونم با استفاده از متد CompareTo دو تا مقدار از اون نوع رو مقایسه کنم.

plus
چهارشنبه 08 آذر 1391, 22:33 عصر
البته فقط این که می گه <T> نمی فهمم یعنی چی ؟

T برای استفاده از Template هاست.توضیحش در توانایی و حوصله من نیست. شاید بقیه دوستان بتونن براتون توضیح بدن.
ولی برای اینکه شما درگیر این موضوع نشید، بدون استفاده از Template اینطوری میشه:



private void BubbleSort(int[] array)
{
BubbleSort(array, 1, 0, false);
}

private void BubbleSort(int[] array, int i, int j, bool inner)
{
if (i == array.Length) // End of outer loop index
return;

if (!inner)
{
BubbleSort(array, i, 0, true);
}
else
{
if (j == array.Length - i) // End of inner loop index
{
i++;
BubbleSort(array, i, 0, false);
return;
}

if (array[j] > array[j+1])
{
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
j++;
BubbleSort(array, i, j, inner);
}
}

gh_mohammady
چهارشنبه 08 آذر 1391, 22:39 عصر
اگر از الگوریتم حبابی بگذرم ، الگوریتم ادغامی رو میشه به روش بازگشتی نوشت ؟ یا اون هم انقدر درگیری داره؟

plus
چهارشنبه 08 آذر 1391, 22:42 عصر
اگر از الگوریتم حبابی بگذرم ، الگوریتم ادغامی رو میشه به روش بازگشتی نوشت ؟ یا اون هم انقدر درگیری داره؟
من یادم نمیاد چطوری بود این الگورتیم ولی کلا الگوریتمی که از نظر مفهومی حالت for یا for تو در تو رو داره وقتی شما بخوای به صورت بازگشتی بنویسیش پیچیده میشه. مثل همینی که نوشتم.

gh_mohammady
چهارشنبه 08 آذر 1391, 22:46 عصر
آقا یا خانم plus خیلی لطف کردین ، بهتر می دونم رو الگوریتم ادغامی کار کنم ...
لطف می کنید اگه اطلاعاتی در همین زمینه داشتید در اختیارم قرار بدید...
باز هم ازین که منبع علمی خودتون رو بدون هیچ توقعی در اختیار همنوعاتون قرار می دید سپاس گزارم ...

plus
چهارشنبه 08 آذر 1391, 22:48 عصر
خواهش میکنم، ولی در مورد الگوریتم ادغامی چیزی یادم نیست.

gh_mohammady
چهارشنبه 08 آذر 1391, 22:58 عصر
:ناراحت:
بازهم ممنون

gh_mohammady
پنج شنبه 09 آذر 1391, 10:12 صبح
کارشناسان محترم مشکل این کد چیه ؟
private int[] Bsort(int[] x)
{

for (int i = 1; i < x.Length; i++)
for (int j = 0; j < x.Length - i; j++)
if (x[j] > x[j + 1])
{
int temp = x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}

return x;
}



private void mergsort(int n, int[] x)
{
int left = (n / 2)+1;
int right = n - left+1;
int[] Aleft = new int[left];
int[] Aright = new int[right];
Bsort(Aleft);
Bsort(Aright);
merge(left, right, Aleft, Aright);
}
private void merge(int p,int m,int []a,int []b)
{
int []s=new int[0];
int i,j,k;
i=j=k=1;
while(i<=p && j<=m)
{
if(a[i]<b[j])
{
s[k]=a[i];
i++;
}
else
{
s[k]=b[j];
j++;
}
k++;

}
if(j>p)
while(j<=m)
{
s[k]=b[j];
k++;
j++;
}
else if(j>m)
while(j<=p)
{
s[k]=a[i];
k++;
i++;
}
}
ممنون میشم از راهنماییتون

gh_mohammady
پنج شنبه 09 آذر 1391, 10:14 صبح
یا این کد؟
public void m_sort(int low, int high)
{
int mid;

if (low < high)
{
mid=(low+high)/2;
m_sort(low,mid);
m_sort(mid+1,high);
merge(low,mid,high);
}
}
public void merge(int low, int mid, int high)
{
int i, j, k;

i = low; j = mid-1; k = low;
while (i <= mid && j <= high)
{
if (A[i] < B[j])
{
A[k] = A[i];
i++;
}
else
{
B[k] = A[j];
j++;
}
k++;
}
if (i >= mid)
{
B[k] = A[j];
j++;
k++;
}
if (j > high)
{
B[k] = A[i];
i++;
k++;
}
}

خیلی مهمه ممنونم

gh_mohammady
پنج شنبه 09 آذر 1391, 20:08 عصر
خواهش می کنم از دوستان و کارشناسان محترم یه بررسی کوچیک روی این کدها داشته باشند .

roolinjax
پنج شنبه 09 آذر 1391, 20:26 عصر
کارشناسان محترم مشکل این کد چیه ؟
private int[] Bsort(int[] x)
{

for (int i = 1; i < x.Length; i++)
for (int j = 0; j < x.Length - i; j++)
if (x[j] > x[j + 1])
{
int temp = x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}

return x;
}



private void mergsort(int n, int[] x)
{
int left = (n / 2)+1;
int right = n - left+1;
int[] Aleft = new int[left];
int[] Aright = new int[right];
Bsort(Aleft);
Bsort(Aright);
merge(left, right, Aleft, Aright);
}
private void merge(int p,int m,int []a,int []b)
{
int []s=new int[0];
int i,j,k;
i=j=k=1;
while(i<=p && j<=m)
{
if(a[i]<b[j])
{
s[k]=a[i];
i++;
}
else
{
s[k]=b[j];
j++;
}
k++;

}
if(j>p)
while(j<=m)
{
s[k]=b[j];
k++;
j++;
}
else if(j>m)
while(j<=p)
{
s[k]=a[i];
k++;
i++;
}
}
ممنون میشم از راهنماییتون

با توجه به چیزایی که با خوندن کدتون از الگوریتم ادغامی یادم اومد از دوران جوانی که یادش بخیر ! این کد ایرادی نداره.
باید درست کار کنه.
ارور میده یا خروجی درستی برنمی گردونه ؟

gh_mohammady
پنج شنبه 09 آذر 1391, 20:36 عصر
سپاس گزارم از توجه تون
از خط 35 ارور می گیره

roolinjax
پنج شنبه 09 آذر 1391, 20:39 عصر
سپاس گزارم از توجه تون
از خط 35 ارور می گیره

شماره های پشت خطوط درست نشون نمیده تو سیستم من
خود خط رو کپی کنید
و البته متن ارور رو

gh_mohammady
پنج شنبه 09 آذر 1391, 20:42 عصر
if(a[i]<b[j])
ارورشم اینه
Index was outside the bounds of the array.
میدونم وقتی این ارور رو میده i=1 شده و j=5 دلیل این بالارفتن j و ثابت موندن i رو نمی فهمم

gh_mohammady
پنج شنبه 09 آذر 1391, 20:46 عصر
و یه چیزی ،مشکل ربطی به فراخوانیم نداره ؟
من اینطوری کدمو فراخوانی کردم ،تو رویداد یک باتن :
mergsort(A.Length, A);

roolinjax
پنج شنبه 09 آذر 1391, 20:48 عصر
به خاطر اینکه قطعه زیر بیش از حدش اجرا میشه
else
{
s[k]=b[j];
j++;
}
شما باید با گذاشتن شر مناسب جلوی این کارو بگیری.
ببخشید اگر دیرم نشده بود کد رو توسیستم خودم می زدم و ارورشو رفع می کردم.
ایشالا که بتونین.
اگر نشد بعدا میام براتون می نویسم
یا علی

gh_mohammady
پنج شنبه 09 آذر 1391, 20:56 عصر
همین که توجه داشتید برام ارزشمنده ، لطفتون پایدار جناب roolinjax (http://barnamenevis.org/member.php?208617-roolinjax)

gh_mohammady
پنج شنبه 09 آذر 1391, 21:44 عصر
هر شرطی میذارم برنامه اجرا نمی شه ....:ناراحت:

fakhravari
پنج شنبه 09 آذر 1391, 23:25 عصر
http://www.codeproject.com/Articles/80546/Comparison-Sorting-Algorithms-in-C-Explained
http://www.codeproject.com/Articles/6033/Sorting-Algorithms-In-C

Mahmoud.Afrad
جمعه 10 آذر 1391, 02:02 صبح
محدوده شمارنده ها رو اصلاح کنید(باید از صفر شروع بشن و کوچکتر از تعداد آرایه باشند)
به آرایه های Aleft , Aright مقداردهی کنید :

private int[] mergsort(int[] x)
{
int n = x.Length;
int left = (n / 2) + 1;
int right = n - left;
int[] Aleft = new int[left];
int[] Aright = new int[right];

for (int i = 0; i < left; i++)
{
Aleft[i] = x[i];
}
for (int j = 0; j < right; j++)
{
Aright[j] = x[left + j];
}

Bsort(Aleft);
Bsort(Aright);

return merge(Aleft, Aright);
}

private int[] merge(int[] a, int[] b)
{
int i = 0, j = 0, k = 0;
int[] s = new int[a.Length + b.Length];

while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])
{
s[k] = a[i];
i++;
}
else
{
s[k] = b[j];
j++;
}
k++;
}

if (i < a.Length && j == b.Length)
{
while (i < a.Length)
{
s[k] = a[i];
i++;
k++;
}
}
else if (i == a.Length && j < b.Length)
{
while (j < b.Length)
{
s[k] = b[j];
j++;
k++;
}
}
return s;
}

private void Bsort(int[] x)
{
for (int i = 1; i < x.Length; i++)
{
for (int j = 0; j < x.Length - i; j++)
{
if (x[j] > x[j + 1])
{
int temp = x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}
}
}
}

gh_mohammady
جمعه 10 آذر 1391, 09:07 صبح
کارشناس /استاد گرامی
از لطفی که داشتید سپاس گزارم
اماهمچنان از خط 33ارور میگیره
s[k] = a[i];
k=10 در حالی که i=5هستش!

gh_mohammady
جمعه 10 آذر 1391, 13:45 عصر
من کدهای زیادی دارم برای مرج سورت و کلاس های مختلف
میخوام همین روشی که انجام دادم رو به عنوان کد تکمیل کنم ، اگه بیس کار مشکل داره بهم بگید لطفا و اگه نه ، مشکلش چیه ؟
بازهم ممنونم

gh_mohammady
جمعه 10 آذر 1391, 15:41 عصر
کدی که من گذاشتم رو امتحان کردید؟ خط 35 که { هست.

طبق کدی که خودم گذاشتم به اینصورت میتونی استفاده کنی:

int[] intArr = new int[15] { 10, 1, 3, 50, 1, 6, 90, 1, 8, 3, 4, 85, 2, 4, 7 };
int[] sortedIntArr = mergsort(intArr);
listBox1.DataSource = sortedIntArr;

بله دقیقا کد شما رو اجرا گرفتم ، البته من 10 تا عدد تصادفی در لیست باکس 1م دارم و در رویداد باتن متد مرج رو همون طوری که فرمودید برای آرایه ای که دارای اعداد تصادفی هست ، فراخوانی کردم و بعد از فراخوانی در لیست باکس دوم ریختم ، نمی دونم چرا آور فلو می ده ، از خط 33 :ناراحت:

gh_mohammady
شنبه 11 آذر 1391, 08:50 صبح
?????????????????????????????????????????????????

Mahmoud.Afrad
شنبه 11 آذر 1391, 13:33 عصر
گفتم که به شمارنده ها (i , j ) توجه کن. هر جا i<a.length هست خوب داخل while باید i به کار بره و افزایش پیدا کنه و همینطور برای j. در کدی که پیام خصوصی کردی شمارنده ها رو جابجا نوشتی. کد متد merge را از پست 32 عینا کپی کن توی برنامت.

gh_mohammady
شنبه 11 آذر 1391, 13:58 عصر
سپاس گزارم استاد گرامی