مرتب سازی

[amir-yazdel]

سلام
توی سایت جست جو کردم و مرتب سازی حبابی رو دیدم.
یه نوع مرتب سازی دیگه هم هست که من الآن اسمش تو ذهنم نیست و نیاز به اون دارم. عزیزان اگر روش دیگری به جز حبابی برای مرتب سازی میدونند لطف کنند و بنویسند.

[MOHSEN8000]

سلام
دوست عزیز فکر کنم تعداد Sort هایی که وجود داره خیلی زیادتر از اون چیزی هست که بشه توی پست به اونا پرداخت ولی احتمالا منظور شما Sort های معروف هست که معمولا پر کاربرد تره. ولی تعداد همین ها هم کم نیست. این Sort هایی هست که معروف تر از بقیه هست. اسماشو نگاه کن هر کودومشو خواستی بگو تا بقیه بتونن بهتر کمکت کنن.
Bubble Sort , Heap Sort , Merge Sort , Quick Sort , Counting Sort , Selection Sort , ...
فکر کنم مقصودت یکی از همین ها باشه. ولی دقیق تر مقصودتو بگی ، بهتر می تونن کمکت کنن.

[amir-yazdel]

خیلی ممنون
بی زحمت Selection Sort رو توضیح بدید.

[MOHSEN8000]

روش مرتب سازی انتخابی اولین روشی هست که برای مرتب سازی به نظر می رسه. کار اون هم به این صورت هست که وقتی تعدادی عدد رو داری ، می گردی و بزرگترین اونارو پیدا می کنی و مثلا به انتهای لیست می بری و از بین بقیه اعداد دوباره می گردی و بزرگ ترین رو انتخاب می کنی و به انتهای لیست می بری و این کار رو همین طوری ادامه می دی تا این که اعداد رو به کامل مرتب کنی. و قطعا به n-1 مرحله نیاز داری برای مرتب سازی همه اعداد. این روش معایبی داره از جمله این که به شکل ورودی داده ها بستگی نداره ، یعنی حتی اگه تو آرایه مرتب شده کامل رو هم بهش بدی نمی تونه تشخیص که این آرایه مرتب هست و دوباره همین n-1 مرحله رو در مورد اون به کار می بره ضمن این که حجم محاسبات در این روش هم خیلی بالاست ( n ( n - 1 ) / 2 ) و همون طور که گفتم آرایه ورودی رو به هر شکلی که بدی ، دقیقا همین تعداد مقایسه انجام می ده. از جمله معدود محاسن این روش هم می شه به ساده بودن پیاده سازیش با هر زبانی اشاره کرد و یا مثلا این که موقع مرتب سازی ، نیازی به استفاده از حافظه کمکی با اندازه نامحدود نداره .
امیدوارم به دردتون خورده باشه.

[mortezamsp]

بیا:
http://www.4shared.com/get/91896555/273cef0b/sorting_-_wwwcplusplusblogskycom.html

[dintic]

با سلام و تشکر از دوست خوبمون.
میشه Merge Sort را هم توضیح بدید .ممنون.

[tondar]

سلام
من برنامه مرج سورت رو براي مرتب كردن دوتا ارايه 25 و 32 تايي با ويژوال c++دارم اما خروجي نميده ميشه كسي ميتونه رفعش كنه?
كسي ميتونه برنامه مرتب كردن همين دو ارايه رو با quicksortوinsertion sortبرام بزاره(بدون ارور با همون ويژوال c++)
ممنون ميشم

[tondar]

اينم برنامه

[tondar]

// neda.cpp : Defines the entry point for the console application.
//
#include <iostream>
using namespace std;
void merge_sort(int A[],int B[],int C[],int a,int b)
{
int i,j,k;
i=j=k=0;
while(i<a && j<b)
{
if(A[i]<B[j])
C[k++]=A[i++];
else
C[k++]=B[j++];
}
while(i<a)
C[k++]=A[i++];
while(j<b)
C[k++]=B[j++];
}
void merge_sort(int A[],int Size);
const int size=32;
int main()
{
int A[32]={3,4,1,7,8,5,6,11,32,43,52,25,41,13,44,65,56,54,3 5,12,23,34,76,73,64,6,87,98,85,48,38,10};
//ints[25]={13,24,35,34,23,31,76,85,90,86,56,45,63,49,80,87, 67,87,30,20,10,40,54,36,68};
merge_sort(A,size);
for(int i=0;i<32;i++)
cout<<A[i]<<' ';
return 0;
}
void merge_sort(int A[],int size)
{
int i,k;
if(size>1)
{
int h=size/2;
int m=size-h;
int *a=new int[h];
int*b=new int[m];
for(i=0;i<h;++i) a[i]=A[i];
for(k=0;k<m;++i,++k) b[k]=A[i];
merge_sort(a,h);
merge_sort(b,m);
merge(a,b,A,h,m);
}
}

[erfan_goohooli]

مرتب سازی ادغامی(Merge Sort): روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شه. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده ، و با ترکیب اونها به مساله اصلی می‌رسیم. در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شن. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب ، و با ادغامشون دادها بصورت کامل مرتب می‌شن.
این هم برنامش:


#include"iostream.h"
#include"conio.h"
void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
void read(int numbers[],int n);

int numbers[100];
int temp[100];

void main()
{
int n;
cout<<"Enter The Array Length = ";
cin>>n;
cout<<"\n\n";
read(numbers,n);
mergeSort(numbers, temp, n);

cout<<"\nDone With Merge Sort.\n";

for (int i = 0; i < n; i++)
cout<<"\n"<< numbers[i];
getch();
}

void read(int numbers[],int n)
{
for(int i=0;i<n;i++)
{
cout<<"Enter The Element ["<<i<<"] = ";
cin>>numbers[i];
}
}

void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}



void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}


void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

[erfan_goohooli]

این هم Quick Sort:


#include<iostream.h>
#include<conio.h>
void read_list(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<"\n\n\t ENTER THE ELEMENT ["<<i<<"] : ";
cin>>a[i];
}
}
void print_list(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<"\n\n\t"<<a[i];
}


void quick_sort(int a[],int first,int last)
{
int low,high,temp,pivot;
low=first;
high=last;
pivot=a[(first+last)/2];

do
{
while(a[low]<pivot)
low++;
while(a[high]>pivot)
high--;
if(low<=high)
{
temp=a[low];
a[low]=a[high];
a[high]=temp;
low=low+1;
high=high-1;
}
}while(low<=high);

if(first<high)
quick_sort(a,first,high);
if(low<last)
quick_sort(a,low,last);
}

void main()
{
int a[20],n;
cout<<"\n\n\t ENTER THE ARRAY LENGTH : ";
cin>>n;
read_list(a,n);
cout<<"\n\n\t THE ARRAY ELEMENTS ARE AS FOLLOWS : ";
print_list(a,n);
quick_sort(a,0,n-1);
cout<<"\n\n\t THE SORTED LIST IS : ";
print_list(a,n);
getch();

}

[rostamidastani]

سلام اگه امکان داره مرتب سازی انتخابی رو بر روی 5 عنصر برام بنویسید ممنون میشم

[kashaneh]

الگوریتم انتخابی :




int smallest

for(i=1;i<n;i++){

smallest=i

for(j=i+1;i<=n;j++){

if(a[j]<a[smallest])

smallest=j

swap(a[i],a[smallest])

}



نکات مهم :
* متغیر n به تعداد عناصر شما و به عبارتی صحیح تر به اندازه آرایه نامرتب شما اشاره دارد
* تابع Swap در آخر الگوریتم، وظیفه جابجایی دو عنصر از آرایه بایکدیگر را به عهده دارد که باید به صورت تابع فرعی پیاده سازی کنید یا اینکه به طریق زیر آنرا بنویسید و جایگزین خط آخر کنید :



temp = a[i]
a[i] = a[smallest]
a[smallest] = temp


* فراموش نشود متغیر temp در ابتدای الگوریتم تعریف شود

[ultra_senator]

mishe begid age bekhaym har marhale az sort chap beshe bayad chi kar kard?