الگوریتم های مرتب سازی : مفهوم مرتب سازی
الگوریتم های مرتب سازی بخش خیلی مهمی از برنامه ها رو انجام می دهند و نقش مهمی را را در آموزش الگوریتم به مبتدیان دارند به همین علت تصمیم گرفتیم تعدادی از این الگوریتم ها را که پر کاربرد تر و جالب تر هستند معرفی کنیم :
- Bubble sort
- Insertion sort
- Selection Sort
- Merge sort
- Quick sort
- Heap sort
- Distribution sorts
- Concurrent sorts
- Counting Sort
در این پست ما به معرفی یک الگوریتم مرتب سازی-sort ساده می پردازیم که از مشهور ترین و ساده ترین الگوریتم های مرتب سازی است و پیاده سازی و درک آن آسان است .
مرتب سازی یعنی این که یک گروه از اطلاعات را بر اساس یکی از شاخص هایش از بزرگ به کوچک یا بر عکس بنویسیم.
این هم کد تابع مرتب سازی – sort است که دو آرگومان دارد یکی آرایه و دیگری طول آرایه :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | void any_sort( int A[],int n) { int i; int j; int temp; for ( i = 0; i < n-1; i++) { for ( j = i+1; j < n; j++) { if( A[i] > A[j]) { temp = A[i]; A[i] = A[j]; A[j] = temp; } } } } |
همین طور که در کد بالا می بینید دو حلقه for داریم که هر کدام مخصوص یک counter هستند اولی i را جلو می برد و به علاوه یک می کند و بعدی j را جلو می برد ، در این مرتب سازی خانه i ام آرایه در نظر گرفته می شود و با خانه های بعدی خود که همان خانه های j ام هستند مقایسه می شوند اگر خانه i ام بزرگ تر از خانه j ام بود مقدار خانه i ام با مقدار خانه j ام عوض می شود.
فرض کنید آرایه ای A به طول ۵ و اعضای زیر را داریم اگر مرتب سازی را انجام دهیم مرحله به مرحله این گونه پیش می رود :
A[5]= {8,5,6,1,4}
۸ ۵ ۶ ۱ ۴
۵ ۸ ۶ ۱ ۴
۱ ۸ ۶ ۵ ۴
۱ ۶ ۸ ۵ ۴
۱ ۵ ۸ ۶ ۴
۱ ۴ ۸ ۶ ۵
۱ ۴ ۶ ۸ ۵
۱ ۴ ۵ ۸ ۶
۱ ۴ ۵ ۶ ۸
در زیر تابع مرتب سازی – sort را می بینید که در main برنامه برای مثال یک آرایه داده ایم که sort – مرتب می کند و آرایه را قبل و بعد از مرتب سازی نشان می دهد:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | // any sort.cpp : open-mind.ir // #include "stdafx.h" #include <iostream> using namespace std; void any_sort( int A[],int n) { int i; int j; int temp; for ( i = 0; i < n-1; i++) { for ( j = i+1; j < n; j++) { if( A[i] > A[j]) { temp = A[i]; A[i] = A[j]; A[j] = temp; } } } } int main() { int i = 0; int A[5]={8,5,6,1,4}; //show array before sort for( i = 0; i < 5; i++) { cout<< A[i]<<" "; } cout<<endl; //sort function any_sort(A,5); //show array after sort for( i = 0; i < 5; i++) { cout<< A[i]<<" "; } cout<<endl; return 0; } |
هزینه ی این الگوریتم برابر این
O(N^2)
می شود.
تشکر از این که ما را دنبال می کنید.
توضیحات واضح، عالی و کاربردی بودند… تشکر و خسته نباشید
سلام اقای دلیرانی مشکل ما رو حل نکردین؟
اقا قرار بود سورتای دیگه رو هم بذارید
به کلی فراموش شد!؟
حتما ، از این هفته شروع می کنم.
۱-الگوریتم جالبی بود ممنون جیزجدیدی یادگرفتم.
۲-سایرالگوریتمهای سرت رو هم قرار بدید(لطفا)
۳-راستش تاحالا اسم -Distribution sorts و Concurrent sorts
رونشنیده بودم.
reshad @ اون الگوریتم ها رو شب های دیگه میذارم .