یکی از مهم ترین عملیاتی که روی آرایه ها میشه انجام داد، طراحی الگوریتم های مرتب سازی روی اونهاست.
الگوریتم های مرتب سازی زیادی موجود هست که تفاوت اصلی اونها نحوه برخوردشون با داده ها و آرایه های طولانیه.
توی این پست قراره یکی از الگوریتم های ساده و معروف که به اسم Selection Sort و یا Bubble Sort معروف هست.
نحوه کار :
اولین قدم اینه که یه دور از اول تا آخر آرایه رو بریم – یعنی پیمایش کنیم – و کوچک ترین بینشونو پیدا کنیم و جای اونو با اولین خونه آرایه عوض کنیم. بار دوم همین کارو می کنیم ولی خونه اول رو در نظر نمیگیریم.
یعنی اگر بخوایم توی هر مرحله آرایه رو بررسی کنیم به این شکل میشه :
{۱۹, ۲۱, ۱۳, ۷, ۱۴, ۱۲} //input
{۷, ۲۱, ۱۳, ۱۹, ۱۴, ۱۲} // i = 0
{۷, ۱۲, ۱۳, ۱۹, ۱۴, ۲۱} // i = 1
{۷, ۱۲, ۱۳, ۱۹, ۱۴, ۲۱} // i = 2
{۷, ۱۲, ۱۳, ۱۴, ۱۹, ۲۱} // i = 3
{۷, ۱۲, ۱۳, ۱۴, ۱۹, ۲۱} // i = 4
یعنی اگر بخوایم به صورت الگوریتم بنویسیم :
i = 0 => min(list[0 to 5]) = 7 => min_index = 3 => swap(list[0], list[3]) i = 1 => min(list[1 to 5]) = 12 => min_index = 5 => swap(list[1], list[5]) i = 2 => min(list[2 to 5]) = 13 => min_index = 2 => swap(list[2], list[2]) i = 3 => min(list[3 to 5]) = 14 => min_index = 4 => swap(list[3], list[4]) i = 4 => min(list[4 to 5]) = 19 => min_index = 4 => swap(list[4], list[4])
و در نهایت سورس کد به زبون c++ :
int * sort(int arr[], length) {
int min, min_index;
for(int i = 0; i < length; i++){
min = arr[i];
min_index = i;
for(int j = i + 1; j < length - 1; j++){
if(arr[j] < min){
min = arr[j];
min_index = j;
}
//جا به جا کردن
// swap
temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
return arr;
}
و اما کد بهینه تر :
int * sort(int arr[], int length){
int min, i, j, temp;
for (i = 0; i < length - 1; i++) {
min = i;
for (j = i + 1; j < length; j++)
if (arr[j] < arr[min])
min = j;
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}