الگوريتم هاي سورت

[amironline]

سلام دوستان خسته نباشيد
مطالبي جالبي بود

منم يه سوال دارم البت هنوز خودم نتونستم مفهوم روي سوال رو بدونم
اگه ميشه اينو توضيح بدين
يك الگوريتم مرتب سازي جايگذاري بنويسيد كه براي يافتن موقعيت جايگذاري بعدي از جستجوي دودويي استفاده كند

منبعش هم طراحي الگوريتم با شبه كدهاي ++C نيپوليتان - نعيمي پور هست

 

[saalek]

انواع سورت :
از:
http://www.sohail2d.com/forum/viewtopic.php?t=4044&sid=b410a44dccb93f871911044aa9ccb6ea

1-مرتب سازی تعویضی
شامل
مرتب سازی حبابی
مرتب سازی دو طرفه
مرتب سازی سریع

2- مرتب سازی انتخابی
شامل
مرتب سازی ساده
مرتب سازی هیپ

3-مرتب سازی درجی
شامل
مرتب سازی خطی
مرتب سازی دوتایی
مرتب سازی به روش شل
-------------------------------------
سالك:اگر متن زير ناخوانا بود به آدرس بالا مراجعه كنيد.
-------------------------------------
الگوریتم مرج سورت به این شکله که برای مرتب کردن یه آرایه اون رو نصف میکنه و هر نیمه رو مرتب میکنه بهد 2 تا آرایه مرتب شده رو توسط مقایسه خانه به خانه تبدیل به یه آرایه مرتب میکنه .
نکته اینجاست که هر کدوم از این 2 ارایه خودشون دوباره نصف میشن .
نحوه کار به این شکله
1 3 2 9 0 4 1 11
برای اولین بار نصف میشه
1 3 2 9 0 4 1 11
عمل نصف شدن اینقدر تکرار میشه که به خونه های یک عددی برسیم

حالا نیمه اول نصف میشه
1 3 2 9 0 4 1 11
دوباره نیمه اول نصف میشه

1 3 2 9 0 4 1 11

حالا خونه های تک عددی داریم
1و 3 مقاسه میشن
حاصل یک آرایه مرتب 2 عضوییه

1 3 2 9 0 4 1 11

1 3 2 9 0 4 1 11

1 3 2 9 0 4 1 11

حالا این دو آرایه مرتب باهم مقایسه میشن و حاصل یک آرایه مرتب 4 عضوی خواهد بود
اول 1 با 2 مقایسه میشه 1 و 1 به عنوان کوچکترین میره تو آرایه چهار تایی

1

حالا 3 با 2 مقایسه میشه و 2 میره تو آرایه چهار تایی

1 2

حالا 3 با 9 مقایسه میشه و 3 میره
1 2 3
ارایه اول چیزی برا مقایسه کردن با 9 نداره چون تموم شده . از اینجا به بعد هرچی تو آرایه دومی هست به ادامه آرایه چهار تایی اضافه میشه . اینجا فقط 9 اضافه میشه
1 2 3 9


1 2 3 9 0 4 1 11
حالا طرف دوم نصف میشه

1 2 3 9 0 4 1 11

1 2 3 9 0 4 1 11
مرتب میشه
1 2 3 9 0 4 1 11

1 2 3 9 0 4 1 11

1 2 3 9 0 4 1 11

حالا 0و1
0
حالا 4و1
0 1
حالا 4و11
0 1 4
حالا 11
0 1 4 11

1 2 3 9 0 1 4 11
حالا یه آرایه 8 تایی و مرتب تشکیل میشه

1و0

0

1و1

فرض کن 1 اولی رو انتخاب کنیم

0 1

2و1

0 1 1

2و4

0 1 1 2

3و4

0 1 1 2 3

9و4

0 1 1 2 3 4

9و11

0 1 1 2 3 4 9

و 11

0 1 1 2 3 4 9 11

حالا آرایه مرتبه

این الگریتم رو فقط با روش های بازگشتی میشه ÷یاده سازی کرد .

سرعت الگریتم خیلی خوبه اما حافظه زیادی اشغال میکنه

 

[amironline]

سالك جون دستت درد نكنه
من تا اونجا كه فهميدم اين سوال منظورش اينه كه ميخوايم يه تعداد عدد رو مرتب كنيم و محل عدد رو بايد با استفاده از جستجويي دودويي پيدا كنيم

الگوريتمي كه به نظر من مي‌رسه اينه كه يه آرايه خال بگيريم و هر عدد رو كه خونديم با استفاده از جستجويي دودويي جاشو پيدا كنيم و تو ارايه قرار بديم

نظر شما چيه؟

 

[saalek]

من بلد نيستم.
دوستان بفرمايند.
.
خيلي طول ميكشه تا بروم ياد بگيرم . بهتره منتظر من نمانيد. ولي بعدا حتما وقت مي گذارم.

 

[amironline]

سالك جون ممنون
اگه از دوستان راه حلي به نظرش ميرسه بگه

 

[amironline]

همونطور كه قبلا گفتم منظور سوال اين بود كه يه تعداد عدد رو بخونيم و با استفاده از جستجوي دودويي جاشونو پيدا كرده و مرتب كنيم
كه در حقيقت اسمش ميشه مرتب سازي درجي با جستجوي دودويي يا binary insertion sort
اينم كد برنامه

#include <stdio.h>
#include <conio.h>
void main()
{
	clrscr();
	int low,high,mid,k,count;
	int a,b,c,d;
	int x[5]={15,13,7,9,14};
	int arr[10]={0};
	count=0;
	scanf("%d",&a);
	count++;
	arr[0]=a;
	scanf("%d",&b);
	count++;
	if (a>b)
	{
		arr[1]=a;
		arr[0]=b;
	}
	else
	{
	arr[1]=b;
	}
	scanf("%d",&c);
	count++;
	low=0;
	high=count-1;
	while (low!=high)
	{
		mid=(low+high)/2;
		if (c<x[mid])
			high=mid-1;
		else if (c>x[mid])
			low=mid+1;
		else
			{
			printf("\n exist");
			}
	}
	if (arr[mid]>c)
	{
		for(int j=9;j>=mid;j--)
			{
			arr[j+1]=arr[j];
			}
		arr[mid]=c;
	}
	for(int i=0;i<=9;i++)
		printf("\n arr[%d]= %d",i,arr[i]);
	getch();
}