انواع الگوریتم های مرتب سازی

[neda.m]

لگوریتم مرتب‌سازی، در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.
پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریتم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.

از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده‌است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).

مبحث مرتب‌سازی در کلاس‌های معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های مختلف کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتم‌های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.

سه تا از معروف ترین الگوریتم ها رو گذاشتم اینجا، اگه خواستین بقیه اش رو هم بخونین، برین تو ویکی پدیا ببینید


مرتب سازی حبابی:

(به انگلیسی: Bubble Sort)

فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگ‌ترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند. مثلا:

۰ - ۰) ۵ ۶ ۴ ۲

۱ - ۱) ۵ ۶ ۴ ۲

۱ - ۲) ۵ ۴ ۶ ۲

۱ - ۳) ۵ ۴ ۲ ۶

۲ - ۱) ۴ ۵ ۲ ۶

۲ - ۲) ۴ ۲ ۵ ۶

۳ - ۱) ۲ ۴ ۵ ۶​

مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:

۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴

۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴

۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴

۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴

۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴

۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷

۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷

۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷

۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷​

همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست. پیاده سازی (مرتب سازی حبابی) در c++

void bubble_sort (int arr [ ] , int n)

{

register int i , j , t , c;

(-- for (i = n - ۲ ; i >= ۰ ; i

{

c = ۰;

(++ for (j = ۰ ; j <= i ; j

if (arr [ j ] > arr [ j + ۱ ])

{

; ] t = arr [ j

arr [ j ] = arr [ j + ۱ ];

; arr [ j + ۱ ] = t
C++;

}

(if (c == ۰

; break

}
}
​

مرتب سازی گزینشی (انتخابی):

(به انگلیسی: Selection Sort)

معمولاً اطلاعات و داده‌های خامی که در اختیار برنامه نویس قرار داره بصورت نامرتب هستن. مواقعی پیش می‌یاد که لازمه این داده‌ها بر حسب فیلد خاصی مرتب بشن؛ مثل لیست دانش آموزان بر حسب معدل ، لیست کارمندان بر حسب شماره پرسنلی ، لیست دفترچه تلفن بر حسب نام خانوادگی و ... روشهای متعددی برای مرتب سازی وجود داره که من قصد دارم تا حد امکان شما رو با این روشها آشنا کنم. برای شروع روش مرتب سازی انتخابی (Selection Sort) رو توضیح می‌دم.

روش انتخابی اولین روشیه که به ذهن می‌رسه: بزرگ‌ترین رکورد بین رکوردهای لیست رو پیدا می‌کنیم و به انتهای لیست انتقال می‌دیم. از بقیه رکوردها بزرگ‌ترین رو انتخاب می‌کنیم و انتهای لیست - کنار رکورد قبلی - قرار می‌دیم و ... مثلا:

۰: ۹ ۱ ۶ ۴ ۷ ۳ ۵

۱: ۵ ۱ ۶ ۴ ۷ ۳ ۹

۲: ۵ ۱ ۶ ۴ ۳ ۷ ۹

۳: ۵ ۱ ۳ ۴ ۶ ۷ ۹

۴: ۴ ۱ ۳ ۵ ۶ ۷ ۹

۵: ۳ ۱ ۴ ۵ ۶ ۷ ۹

۶: ۱ ۳ ۴ ۵ ۶ ۷ ۹​

پیاده سازی (مرتب سازی انتخابی) در c++:

void selection_sort (int arr[] , int n)

{

register int i , j;

int max , temp;

(--for (i = n - ۱ ; i > ۰ ; i

}

max = ۰;

for (j = ۱ ; j <= i ; j++)

if (arr[ max ] < arr[ j])

max = j;

; ] temp = arr[ i

arr[ i ] = arr[ max];

arr[ max ] = temp;

}

}​

مرتب سازی سریع:

(به انگلیسی: Quick Sort)

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستن و بالعکس. مثلاً اعداد صحیح زیر رو در نظر بگیرید:

۵ ۶ ۱ ۹ -۲ ۴ ۵ ۱۵ ۳ ۱ ۴ ۱۰​

عدد ۵ رو به عنوان محور در نظر می‌گیریم. داده‌ها به این صورت بازچینی می‌شن:

۱ -۲ ۴ ۳ ۱ ۴ ۵ ۶ ۹ ۵ ۱۵ ۱۰​

همونطور که مشاهده می‌کنید اعداد سمت چپ عدد ۵ زیر خط دار همگی از ۵ کوچیکتر و اعداد سمت راست بزرگ‌تر یا مساوی اون هستن.

پیاده سازی مرتب سازی Quick sort در c++

تابع partition با دریافت آرایه و حد بالا و پایین تکه‌ای که باید تقسیم بشه عملیات لازم رو انجام می‌ده، و اندیس محل تفکیک رو (محل عدد ۵ در مثال بالا) به عنوان نتیجه بر می‌گردونه.

int partition (int arr[ ] , int low , int high)

{

int lb = low + ۱ , rb = high , temp , pivot = arr[ low ] , p;

while (lb <= rb)

{

while (arr[ lb ] <= pivot && lb <= rb)

lb++;

while (arr[ rb ] > pivot && lb <= rb)

rb--;

if (lb < rb)

{

temp = arr[ lb];

arr[ lb ] = arr[ rb];

arr[ rb ] = temp;

}

}

(if (rb == high

p = high;

else if(rb == low)

p = low;

else

p = lb – ۱;

arr[ low ] = arr[ p];

arr[ p ] = pivot;

return p;

}
​

اگه این تابع رو برای مثال بالا استفاده کنیم مقدار ۶ (اندیس ۵ زیرخط دار) برگشت داده می‌شه. با تکرار کردن این عملیات برای دو قسمت به دست اومده (در مثال بالا از اندیس صفر تا ۵ و از اندیس ۷ تا ۱۱) داده‌ها به صورت کامل مرتب می‌شن.

بر اساس گفته‌های بالا تابع مرتب سازی به این صورت خواهد بود:

void quick_sort (int arr[ ] , int low , int high)

{
if (low < high)

{

int p = partition(arr , low , high);

quick_sort(arr , low , p – ۱);

quick_sort(arr , p + ۱ , high);

}

}​

همونطور که مشاهده می‌کنید این تابع بصورت بازگشتی نوشته شده. در صورتی که بخواید به صورت غیر بازگشتی بنویسید باید از پشته به صورت زیر استفاده کنید:

void quick_sort (int arr[ ] ,int n)

{

stack st;

st.push(۰);

st.push(n – ۱);

int low , p , high;

while(! st.isempty())

{

high = st.pop();

low = st.pop();

p = partition(arr , low , high);

if (p > low)

{

st.push(low);

st.push(p – ۱);

}

if (p < high)

{

st.push(p + ۱);

st.push(high);

}

}

}
​

 

[Sylar]

پاسخ : انواع الگوریتم های مرتب سازی

اول از همه تشکر میکنم بابت مطلب!
اگر ++C کار میکنید دونستن این موارد برای درک حل الگوریتمیتون خیلی مفیده! ولی به هیچ درد دیگه ای نمیخوره!
خوده ++C بهترین ابزار ممکن برای Sort کردن را در خودش نگه داری میکنه!
آرایه ای که میخوایید سورت کنید را به این صورت به تابع میدید!

#include <algorithm>

sort(Arr,Arr+N);

اینطوری از خانه ی اول آرایه تا N عنصر بعد را به بهترین نحو ممکن سورت میکنه!
میشه حتی نحوه سورت کردن را هم تغییر داد! و کلی کارای دیگه که باش میشه کرد. اگر کسی تمایل داره بدونه بگه تا بگم!

 

[fzgm]

پاسخ : انواع الگوریتم های مرتب سازی

ندا،مرسی!
ولی خب،میدونی که برای خودمون تکراریه!

آقای علیرضا شما هم مرسی!
نکته جالب توجهی بود!

 

[trustme]

پاسخ : انواع الگوریتم های مرتب سازی

با تشکر از ندا و علیرضا!
علیرضا، شما هم لطف کن کار با این تابع رو کامل توضیح بده
الگوریتم ندا هم به نظر خوب بود! دقت داشته باشین که بعضی اوقات در C++ نمی نویسیم! مثلا در VB6 !

 

[Sylar]

پاسخ : انواع الگوریتم های مرتب سازی

با تشکر از ندا و علیرضا!
علیرضا، شما هم لطف کن کار با این تابع رو کامل توضیح بده
الگوریتم ندا هم به نظر خوب بود! دقت داشته باشین که بعضی اوقات در C++ نمی نویسیم! مثلا در VB6 !

چشم.
متاسفانه من با VB هیچ وقت کار نکردم ولی یک نکته ای که هست اینه که Sort کردن مسئله ی خیلی پیش و پا افتاده ایه و اگر یک نفر بخواد
یک برنامه درست و حسابی بنویسه نباید روی همچین چیزی وقت زیادی صرف کنه! برای همین حدس میزنم هر زبان برنامه نویسی کم کم خودش
تابع برای Sort کردن داشته باشه!

و اما ادامه مبحث سورت! یکی از کارای قشنگی که میشه کرد اینه که میشه نحوه ی مقایسه برای سورت کردن را تغییر داد! مثلا نزولی سورت کرد! یا هر جور دیگه ای که عشقتون میکشه!
به این صورت که یک آرگومان جدید باید برای تابع Sort بفرستید.

ابتدا یک تابع میسازید که خروجیش Bool باشه و ورودیش دو تا int . اون وقت داخلش نحوه ی مقایسه تون را تعیین میکنید! برای مثال:

bool cmp(int a,int b){
return a<b
}​

بعد تابع سورت را کال میکنید و در پایان اسم تابع سورت تون را بش میگید.

sort(Arr,Arr+N,cmp)​

اگر مراحل بالا را پیش برید عین آدم سورت میکنه! اگر در تابع CMP به جای
return a<b
بگید
return a>b
براتون نزولی سورت میکنه! . الان هر کاری بخواهید میتونید بکنید. مثلا فرض کنید ساختمان داده ای دارید که میخوایید اونارو سورت کنی. به مثال زیر توجه کنید.

struct test{
int a,b,c
}list[100]

bool cmp(test a,test b){
return a.a<b.a
}

sort(list,list+100,cmp)
​

این مثال برای اینکه نشون بده چقدر دستتون بازه مثال خوبی بود!
بدیهیه که با پوینترها هم میتونید به همین طریق کار کنید تا سرعت برنامتون بره بالا تر!

 

[trustme]

پاسخ : انواع الگوریتم های مرتب سازی

دو الگوریتم به زبان VB ! البته توی VB.net من چند سری sort برای آرایه ها رو دیدم! ولی کارم بهشون نکشیده
(و تصدیق می کنم که کسی دیگه خودش نمی شینه بنویسه! ولی در برنامه ساده من حال می کنم خودم ببینم تابعم رو )

'sort n top cells with bubble-sort algorithm
Function bubble_sort(ByRef arr() As Integer, n As Integer)
Dim i, j, t, c As Integer
For i = n - 2 To 0 Step -1
c = 0
For j = 0 To i
If (arr(j) > arr(j + 1)) Then
t = arr(j)
arr(j) = arr(j + 1)
arr(j + 1) = t
c = c + 1 'in VB.net "c+=1" is shorter
End If
Next j
If c = 0 Then Exit For
Next i
End Function

'sort n top cells with selection-sort algorithm
Function selection_sort(ByRef arr() As Integer, ByVal n As Integer)
Dim i, j As Integer
Dim max, tmp As Integer
For i = n - 1 To 1 Step -1
max = 0
For j = 1 To i
If (arr(max) < arr(j)) Then
max = j
temp = arr(i)
arr(i) = arr(max)
arr(max) = temp
End If
Next j
Next i
End Function​

روش آخر رو هم گذاشتم اگه کسی واقعا خواست با وی بی بنویسه، خودش زحمتی بکشه (و این دوتا زحمتی برای نوشتن نداره )

 

[armita]

پاسخ : انواع الگوریتم های مرتب سازی

شما می تونید از http://www.concentric.net/~ttwang/sort/sort.htm سورس کامل الگوریتم های مختلف رو دریافت کنید .

 

[delafrooz.mir]

پاسخ : انواع الگوریتم های مرتب سازی

سورت خود ++c شدیدا سورت خوبیه! یه سری ایده ی فوق العاده زده که تقریبا سریع ترین سورتیه که می تونه وجود داشته باشه... من شنیدم که مثلا یه الگوریتم هست که 7تا عدد رو با 5تا مقایسه سورت می کنه ( نمی دونم عدداشو درست می گم یا نه! شاید هم 5تا رو با 7تا سورت می کنه!!!! ) بعد سورت ++C این طوریه که هر وقت کارش به جایی رسید که خواست 7تا عدد رو سورت کنه، از این استفاده می کنه. بعضی جاها هم حتی selection sort رو که از o(n^2) هست رو به جای quick sort به کار میبره... خلاصه خفن ترین سورت ممکنه. خود من تا حالا نشده که برنامه ی یه الگوریتم سورت کردنو بنویسم، هر وقت خواستم از سورت خود ++C استفاده کردم!

 

[delafrooz.mir]

الگوریتم های sort

یه تاپیک در این مورد زده شد، ولی می خواستم اینجا یه کم بیشتر توضیح بدم. در ضمن اونجا یه کم بحث کشید به برنامه نویسی که فعلا خیلی ربطی نداره!

اگه جلوی شما اعداد 4-7-3-2-10 رو بذارن و بگن سورتش کنین، راحت سورتشون می کنین. تا جایی که شنیدم هنوز کسی نفهمیده مغز آدم چه طوری اعداد رو سورت می کنه.
حالا اگه بخوایم یه راه حل کلی براش ارائه بدیم، یه سری الگوریتم سورت کردن پیدا می شن...

الگوریتم های سورت کردن اول اولش دو دسته اند: الگوریتم های مقایسه ای و الگوریتم های غیر مقایسه ای ( البته شاید این دسته بندی با این اسم وجود نداشته باشه، ولی کلا یه همچین دسته بندی ای هست )
مقایسه ای ها اونایی هستن که خود اعداد رو با خودشون مقایسه می کنین، مثلا اگه 4 و 5 رو خواستین سورت کنین، میاین می بینین که 4 از 5 کوچیکتره
غیر مقایسه ای اونایی هستن که همه ی اعداد یا چیزای موجود که می خوایم سورتشون کنیم رو با چیزایی که از قبل می دونیم سورت شده هستن مقایسه می کنیم.

ثابت میشه که الگوریتم های مقایسه ای، order اِشون از nlgn بیشتر مساویه ( اگه شد یه جای دیگه میگم اثباتشو ) ولی الگوریتم های غیرمقایسه ای از o(n) هم هستن.درسته که اینا زمانشون کمتره اما محدودیت های جدی دارن... در پست بعدی الگوریتم های غیرمقایسه ای رو بررسی می کنیم

نکاتی که باید بدونین:
1) lg به معنای لگاریتم پایه ی 2 هست. وقتی می گیم lgn یعنی باید عددی رو پیدا کنیم که وقتی 2 به توان اون عدد می رسه، میشه n. مثلا lg16=4
2) یه نکته ی دیگه این که، order یک الگوریتم به معنای زمانش هست ( یه جورایی همین طوره، ولی اگه بخوایم کامل بحث کنیم باید یه پست جدا زد! ) وقتی میگیم o(n) هست یک الگوریتم، یعنی این که مثلا اگه بخوای که این الگوریتم رو برای 1000تا چیز انجام بدی، تعداد کارایی که باید انجام بدی دور و ور 1000تاست، مثلا 2000 تا یا 920 تا یا 10هزار تا! ولی دیگه نمی شه یک میلیون! اگه زمان یک الگوریتم به صورت چند جمله ای باشه، بزرگترین توان n ( که n همون تعداد چیزاییه که می خوای الگوریتم رو روشون اجرا کنی! ) رو د نظر می گیری. در حالت کلی هم ضریبش خیلی مهم نیست، مگه این که اون ضریب نسبت به خود n بزرگ باشه

 

[delafrooz.mir]

پاسخ : الگوریتم های sort

خب 2نوع الگوریتم غیرمقایسه ای معروف هست... که البته یه کوچولو فرق می کنن:

1) Bucket sort
این sort محدودیت داره زیادم داره!
فرض کنین که می خواین یه سری اسم رو sort کنین. مثلا بگین که اونایی که اسمشون با الف شروع میشه روز 5شنبه بیان برای ثبت نام! براتون هم مهم نیست که اول کسی بیاد برای ثبت نام که حرف دوم فامیلش ب است یا خ !
میاین 32 تا سطل قرار می دین، که برچسب هر کدوم یه حرف الفباست. بعد فامیلا رو دونه دونه چک می کنین که حرف اولشون چیه. می ندازینش توی سطلی که این حرفو داره. اگه بهتون 100 تا اسم بدن، حداکثر تعداد کارایی که می کنین 100 میشه... بعد هم 32 تا سطل رو به ترتیب می خونین که می شه حدود 100+32 عملیات.
یا مثلا بهتون می گن که یه سری عدد صحیح 1 تا 100 بهتون می دیم که سورتشون کنین. این طوری 100 تا سطل می ذارین و هر عددی رو می ندازین توی سطل خودش. بعد هم اعداد توی سطل ها رو به ترتیب می خونین.
در حالت کلی اگه بخواین n تا چیز رو توی m تا سطل بندازین، عملیاتی که انجام می دین o(m+n) هست، که اگه m زیاد باشه چیز خوبی نیست...

در این الگوریتم محدودیت هایی هست، در مورد مثال آخری این چیزا هستن:
1) باید حتما بدونین که اعداد بین 1 تا 100 هستن
2) باید حتما بدونین که صحیح هستن، اگه اعشاری باشن بدبخت می شین!
3) اینم باید بدونین که مثلا 100 تا سطل می خواین، اگه شد یک میلیون هم کارتون زیاد میشه هم حافظه بیشتر می بره!

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

 

[delafrooz.mir]

پاسخ : الگوریتم های sort

خب الگوریتم بعدی اینه:
2) Radix sort
فرض کنین که یه سری عدد توی بازه ی 1 تا 1میلیون ( یعنی کمتر از 1میلیون ) بهتون می دن و می خواین سورتشون کنین، اگه بخواین از روش قبلی استفاده کنین که مجبورین 1میلیون تا سطل داشته باشین و مثلا برای 100تا عدد باید o(m+n)=o(1000000) کار انجام بدین دیگه ...
ولی میشه یه ایده ی استقرایی زد. فرض کنین که پشت همه ی عددها به اندازه ی کافی صفر بذاریم تا همه شون یه سری رشته ی 6رقمی بشن. حالا میاین و 10تا سطل می ذارین و اولین رقم هر عدد رو بررسی می کنین و توی سطل مربوطه میندازین. بعد هر سطل رو جداگانه سورت می کنین ( که طبق فرض استقرا بلدین این کارو بکنین )
حالا نکته اینجاست که در مرحله ی اول n بار عددا رو چک می کنین. توی هر مرحله همین طوره، یعنی اگه عدداتون ماکسیموم 6رقمی باشن، 6n بار کار انجام دادین. این کارو واسه سورت کردن رشته ی کاراکتری هم میشه کرد...
خب من گفتم که این خیلی با قبلیه فرق نداشت! جفتشون هم محدودیت دارن! اولا که عدد ها باید یه سقف و کف داشته باشن، بعد هم ترجیحا صحیح باشن یا تا یه تعداد محدودی رقم اعشار داشته باشن... ولی اگه این محدوده ها بهتون داده شده باشه، بهتره از این نوع الگوریتم استفاده کنین چون از o(n) هستن!

همین دیگه... فعلا واسه امروز بسه خسته شدم دیگه!

 

[neda.m]

پاسخ : انواع الگوریتم های مرتب سازی

آره، سورت های خود C++ خوبه خیلی. ولی اینکه این الگوریتم ها رو یاد بگیریم یا درباره ش فکر کنیم، فایده ش به اینه که یه ایده هست و این که بدونیم چه نوع سورت هایی وجود داره، چون بعضی جاها به درد می خوره واقعا! به صورت معمول کم پیش میاد، ولی مثلا مواقعی هست که سرعتش و ساده بودن الگوریتم از همه چیز واست مهم تره و مثلا می خوای لوپ کمتر داشته باشه. اون موقع هست که نمی شه از همون سورت ها استفاده کرد! مثلا تو رسکیو سیمولیشن، سرعت سورت کردن و اولویت دادن به مجروح ها خیلی خیلی مهمه! پس باید از الگوریتم خوبی استفاده کرد که در کمترین زمان، سورت بکنه

 

[delafrooz.mir]

پاسخ : انواع الگوریتم های مرتب سازی

آره... اگه اون پست جدیدی که زدم رو بخونی، منم اون جا 2تا الگوریتم نوشتم که به نظر میاد اصلا به درد نمی خورن ولی وقتی محدوده های لازمو بهت بدن، به جای این که سورت nlgn بنویسی، می تونی n بنویسی که بسی فایده ها دارد!

 

[fzgm]

پاسخ : الگوریتم های sort

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

 

[fani]

پاسخ : الگوریتم های sort

یکی دیگه هست اسمش هست booble sort یعنی سرت حبابی
الگوریتمش اینجوریه که شما اگه ان عدد داشته باشی ان -1 بار حلقه رو اجرا میکنی تو هر دور بزرگتری عدد رو توی اولی خونه ای که خوندی میذاری
مثلا اعداد یک تا ده رو به صورت نامنظم بهت میدن میگن سرت کن اول از اولی تا اخری رو نیگا میکنی وده رو میاری وجاش رو با جای خونه ی اول و جا به جا میکنی بعد از دومین خونه تا ده و..... اینجوری اعداد بزرگ مثل حباب میرن بالا

 

[maziar]

پاسخ : الگوریتم های sort

البته نميشه راحت درباره سورت ها حرف زد

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

 

[Dark Eagle]

پاسخ : الگوریتم های sort

هیچ الگوریتمی هیپ سورت نمی شه هم اوردرش خوبه هم میشه درخته مورد نظر رو توازن بخشید تا اوردر به نسبت کاهش را یابد.

 

[mehrad :|]

پاسخ : الگوریتم های sort

هیچ الگوریتمی هیپ سورت نمی شه هم اوردرش خوبه هم میشه درخته مورد نظر رو توازن بخشید تا اوردر به نسبت کاهش را یابد.

البته جای heap sort باید بگی merge sort :)
merge sort تو خیلی از سوالا کاربرد داره (حتی سوالایی که ربطی به sorting نداره)

 

[Dark Eagle]

پاسخ : الگوریتم های sort

من که هیپ رو نسبت به مرج ترجیح میدم..........
اوردر جفتشون تقریبا یکیه..........
ولی حدودا هیپ کمتره فقط یه مشکل داره که نمی شه همه جا ازش استفاده کرد..............
اوردر هیپ بعد از توازن خیلی کمتر از (nlog(n .............
باااااا مارو دسته کم نگیر لا اقل فرق هیپو مرجو می دونیم...........

 

[-_sInA_-]

پاسخ : الگوریتم های sort

چیجوری میشه یه ترکیبی از مرج و هیپ درست کرد ؟

مثلا خود سورت ++c مخلوطی از این 2 تاست.

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