آموزش الگوریتم های مرتب سازی آرایه ها در برنامه نویسی ++C

[moeintnt]

آموزش الگوریتم های مرتب سازی آرایه ها در برنامه نویسی ++C







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


الگوریتم مرتب سازی حبابی (bubble sort) :

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

A = {7, 3, 9, 1}




۳ ۷ ۹ ۱ ---> 3 7 9 1 ---> 3 7 1 9 Step 1
۳ ۷ ۱ ۹ ---> 3 1 7 9 ---> 3 1 7 9 Step 2
۱ ۳ ۷ ۹ ---> 1 3 7 9 ---> 1 3 7 9 Step 3


همانگونه که ملاحظه کردید در مرحله اول، ابتدا ۷ با ۳ مقایسه شده و چون ۳ از ۷ کوچکتر است جایشان عوض می شود. سپس در همان مرحله ۷ با ۹ مقایسه شده و چون ۹ از ۷ بزگتر است پس جابجایی صورت نمی گیرد و در انتهای همان مرحله ۹ با ۱ مقایسه شده و بدلیل کوچکتر بدن ۱ از ۹ بین آن دو جابجایی صورت می گیرد .در مرحله دوم و سوم نیز این روال اجرا می شود تا در نهایت آرایه ما بصورت صعودی مرتب می گردد. همانطور که می بینید تعداد مقایسه ها زیاد است و اگر آرایه ما عناصر زیادی داشته باشد، الگوریتم حبابی وقت زیادی را برای مراب کردن عناصر از برنامه و CPU خواهد گرفت. در زیر به کد این الگوریتم را با دقت پیگیری نمایید و سعی کنید مثالی را در نرم افزار سیستم خود انجام دهید :

void bubbleSort(int x[], int y)



{
int i, j, temp;

for(i=y-1 ; i>0 ; i--)
for(j=0 ; j<i ; j++)
if(x[j] > x[j+1])
{
temp = x[j];
x[j] = x[j+1];
x[j+1] = temp;
} //end of if
}


در بالا متغیری بنام temp تعریف شده که از آن در جابجا کردن عناصر آرایه استفاده می کنیم به این ترتیب که مقدار اول را در خود نگه می دارد و مقدار دوم در مقدار اول ریخته می شود و در نهایت مقدار اول یا همان temp در مقدار دوم قرار می گیرد و در حقیقت، این متغیر نقش کمکی (واسط) در جابجایی را بازی می کند .

الگوریتم مرتب سازی درجی (insertion sort) :

این الگوریتم هم تقریبا مانند الگوریتم حبابی عمل می کند با این تفاوت که مقایسه در ابتدا از عنصر دوم شروع می شود و فرض بر این است که اولین عنصر از همه کوچکتر است و اگر اینگونه نبود جای این دو عنصر با هم عوض می شود و به همین ترتیب تا آخر و فرق آن با الگوریتم بالا در این است که درج بر روی هر عنصری که باشد حتما عناصر قبل از آن مرتب شده اند :

A = {7, 3, 9, 5, 1}




۷ [۳] ۹ ۵ ۱ ---> 3 7 [9] 5 1 ---> 3 7 9 [5] 1 ---> 3 5 7 9 [1] ---> 1 3 5 7 9


کد الگوریتم درجی را با هم می بینیم با این توضیح که عنصری که علامت درج روی آن است (عنصری که برابر با مقدار متغیر i در حلقه تکرار for ) حتما عناصر قبل از آن مرتب هستند اما در الگوریتم حبابی اینچنین نبود لذا بازده زمانی الگوریتم درجی از حبابی بیشتر است، و کارایی برنامه را بالا می برد

void insertSort(int s[], int len)



{
int i, j, x;

for(i=1 ; i>len ; i++)
{
x = s[i];
j = i-1;
while(j>=0 && s[j]>x)
{
s[j+1] = s[j]
j--;
}
s[j+1] = x;
}
}


الگوریتمهای دیگری نیز هستند که از حیطه این مبحث خارج بوده و شاید در آینده در همین فصل به آنها بپردازیم .
الگوریتم های جستجو در برنامه نویسی C++

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

جستجوی ترتیبی در برنامه نویسی C++ :


int lsearch(int arr[], int length, int num)



{
for(int i=0 ; i<length ; i++) // Search in arr[]
if(arr[i] == num) // Find number 6 in arr[]
return 1;
return -1; // Do not find number 6 in arr[]

}


در تابع lsearch بالا که الگوریتم جستجوی ترتیبی است، ما دارای ۳ پارامتر ورودی که شامل آرایه، طول آن و عدد مورد جستجو هستیم. اگر عدد را پیدا کردیم تابع مقدار ۱ و در غیر اینصورت مقدار منفی ۱ را برمیگرداند که می توانیم در تابع main از نتیجه این تابع استفاده نماییم .

الگوریتم جستجوی دودویی در برنامه نویسی C++ :

int lsearch(int arr[], int length, int num)



{
int min, low = 0, high = length-1;
while(low <= high) // برای اطمینان از وجود بیش از یک عنصر در آرایه
{
mid = (low+high)/2; // پیدا کردن عنصر وسط آرایه
if(num < arr[mid]) // جستجو در نیمه سمت چپ آرایه
high = mid-1;
else if(num > arr[mid]) // جستجو در نیمه سمت راست آرایه
low = mid +1;
else return mid; // در اینصورت عدد مورد نظر عدد وسط است
}
return -1; // در اینصورت عدد در آرایه وجود ندارد
}



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