آموزش مرتب سازی انتخابی

فرض کنید که به شما آرایه ای بدهند و از شما بخواهند که بزرگترین عنصر این آرایه را در خروجی نمایش دهید.برای این کار برنامه ای خواهید نوشت که بزرگترین عنصر را به شما بدهد.

* آرایه خانه هایی پشت سر هم از حافظه است که در آن متغییر ها را ذخیره میکنیم

حال فرض کنید که از شما بپرسند عنصر6 ام این آرایه به ترتیب بزرگ به کوچک چیست؟ آن وقت چکار خواهید کرد؟ برای حل این قبیل مسائل باید کل آرایه را مرتب کنیم!

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

مرتب سازی انتخابی یا Selection sort

در مرتب سازی انتخابی از اولین خانه آرایه شروع می کنیم و این خانه را با خانه های بعد از خودش تا آخرین خانه ی آرایه، یکی یکی مقایسه می کنیم

هر جا که مقدار متغییر خانه ای از خانه ی اولی کمتر بود نگه میدارد و مقایسه را تا اخرین خانه ارایه ادامه میدهد و کوچکترین مقدار ارایه را یافته و مقدار آن را با خانه اول جابجا میکند اگر مقدار کوچکی نبود کاری نکرده و به سراغ خانه بعدی میرود یعنی خانه دوم .

مقدار خانه دوم را با خانه های بعدی ارایه مقایسه میکند و کوچکترین مقدار دوباره جستجو کرده یافته و با خانه دوم جابجا میکند اگر هیچکدام از مقدار خانه دوم کوچکر نبود کاری انجام نمیدهد و سراغ خانه بعدی میرود و این کار را برای تمام خانه های آرایه ( غیر از آخرین خانه که به مقایسه ای احتیاج ندارد) انجام می دهیم.

در شکل رو به رو مراحل این کار بخوبی نشان داده شده است:

حالا به سراغ کد نویسی مرتب سازی ارایه میرویم

در این قسمت کد های مرتب سازی ارایه را با زبان php نوشته ایم:

1234567891011121314151617181920212223242526272829<?php
function change_place(&$x, &$y){
$temp = $x;
$x = $y;
$y = $temp;
}
function selection_Sort(&$arr, $n)
{
  for ($i = 0; $i < $n - 1; $i++) {
  $min = $i;
  for ($j = $i + 1; $j < $n; $j++)
  if ($arr[$j] < $arr[$min])
  $min = $j;
change_place ($arr[$min], $arr[$i]);
  }
}
 
function printArray(&$arr,$size)
{
for ($i=0; $i < $size; $i++) {
  echo $arr[$i] . "<br>"
}
}
 
$arrayeh = array(12, 14, 13, 5, 6,10,4,1,2);
$m = sizeof($arrayeh);
selection_Sort($arrayeh, $m);
printArray($arrayeh, $m);
 ?>

توضیح کد های بالا:

در تابع با نام change_place ما یک متغییر خالی در نظر میگیریم به نام temp

برای تعویض جای دو خانه متغییر یکی از خانه ها (خانه اول)را در متغییر خالی همان temp میریزیم

سپس داده های خانه دوم را در داخل خانه اول که حال خالیست میریزیم

بعد از ان داده های خانه اول را که در temp ریخته بودیم را در خانه دوم میریزیم

حالا داده های دو خانه با هم تعویض شدند

در فانکشن بعدی دو ورودی میخواهد از ما که یکی طول ارایه است دومی اندازه ارایه یعنی همان تعداد خانه های ارایه هر بار یکی یکی خانه های ارایه را میخواند و اگر کوچکتر از داخل متغیرmin شماره خانه ها نگه میدارد سپس با حلقه بعدی خانه بعد از خانه i را میگیرد و مقایسه میکند کوچکترین داده را پیدا میکند وشماره ان را در min ذخیره میکند یعنی متغیر داخل j کوچکترین است و سپس فانکشن تعویض جا را صدا میزند که متغییر های داخل دو خانه را با هم جا به جا کند این عمل تا زمانی که i مساوی با طول ارایه شد ادامه پیدا میکند فانکشن بعدی پس از اتمام مرتب سازی خانه های ارایه را خوانده و چاپ میکند.

نویسنده مطلب: سیما نوری

منبع مطلب