در این جلسه تیم کدگیت را با آموزش مرتب سازی درجی در c++ همراهی کنید. پیش نیاز این آموزش آشنایی با آرایه و توابع هست.
مرتب سازی درجی
مرتبسازی درجی (Insertion Sort) یک الگوریتم مرتبسازی ساده بر مبنای مقایسه است. این الگوریتم برای تعداد دادههای زیاد، کارآمد نیست و در این موارد، الگوریتمهای بهتری مثل مرتبساز سریع، مرتبساز ادغامی و مرتبساز پشته وجود دارد.(ویکیپدیا)
الگوریتم
این الگوریتم به این صورت عمل میکند که تمام عناصر لیست را یکی یکی برمیدارد و آن را در موقعیت مناسب در بخش مرتب شده قرار میدهد. انتخاب عنصر مورد نظر، اختیاری است و میتواند توسط هر الگوریتم انتخابی، انتخاب شود. مرتبسازی درجی به صورت درجا عمل میکند. نتیجه عمل بعد از k مرحله، حاوی k عنصر انتخاب شده به صورت مرتب شده است.
معمولترین نسخه از این الگوریتم که روی آرایهها عمل میکند، به این صورت است:
- فرض کنید یک تابع به اسم Insert داریم که داده را در بخش مرتب شده در ابتدای آرایه درج میکند. این تابع با شروع از انتهای سری شروع به کار میکند و هر عنصر را به سمت راست منتقل میکند تا وقتی که جای مناسب برای عنصر جدید پیدا شود. این تابع این اثر جانبی را دارد که عنصر دقیقاً بعد از بخش مرتب شده را رونویسی میکند.
- برای اعمال مرتبساز درجی، از انتهای سمت چپ آرایه شروع میکنیم و با صدا زدن تابع insert، هر عنصر را به موقعیت درستش میبریم. آن بخشی که عنصر فعلی را در آن میکنیم، در ابتدای آرایه و در اندیسهایی است که آنها را قبلاً آزمایش کردهایم. هر بار صدا زدن تابع insert، یک عنصر را رونویسی میکند، اما این مسئله مشکلی ایجاد نمیکند، زیرا این داده، همانی است که الان در حال درج آن هستیم(ویکیپدیا)
مرتب سازی درجی در c++
برای پیاده سازی مرتب سازی درجی در c++ باید ابتدا فرآیند این الگوریتم را خوب متوجه شوید. ابتدا این الگوریتم فرض میکند ما فقط یک خانه داریم و عنصر بعدی به این یک خانه اضافه میکند و این دو خانه مرتب میشوند. حال که دو خانه مرتب شدند عنصر سوم را به دو خانه قبلی اضافه میکند و حال این 3 خانه را مرتب میکند. این کار را تا جایی ادامه میدهد که تمام عناصر ما مرتب شده باشند.
void insertionSort(int array[] , int size) {
int n = size;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
توضیح کد بالا کمی دشوار است ولی توضیح کلی که در مورد کد میتوان داد این است که حلقه for برای تعداد خانه های آرایه است(همانطور که گفتیم الگوریتم تا تمامی عناصر را مرتب نکند تمام نمیشود) و حلقه دوم برای مرتب کردن عناصر از 0 تا j است.
برای تست برنامه مرتب سازی درجی در c++ کد زیر را بزنید.
int main() {
int size = 9;
int input[] = {4, 2, 9, 6, 23, 12, 34, 0, 1 };
insertionSort(input , size);
for (int i = 0; i < size; ++i) {
printf("%d\n", input[i]);
}
return 0;
}
خروجی برنامه
0
1
2
4
6
9
12
23
34