آموزش الگوریتم های مرتب سازی آرایه ها در برنامه نویسی ++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 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++برای اینکه ما بتوانیم عنصری را در یک آرایه جستجو و پیدا نماییم می توانیم به دو روش عمل کنیم. اولین روش اینست که ما از ابتدای آرایه شروع کنیم و تا انتها، یکی یکی بین عناصر بگردیم و عنصر مورد جستجو را با عناصر آرایه مقایسه نماییم، اگر برابر شد که عنصر موجود در آرایه نتیجه جستجو است در غیر اینصورت آن مفدار در آرایه وجود ندارد. روش دوم اینست که ابتدا آرایه را مرتب کنیم و سپس با مقایسه عنصر جستجو با عنصر آرایه عمل جستجو را انجام دهیم .جستجوی ترتیبی در برنامه نویسی منبع: [برای مشاهده لینک ها شما باید عضو سایت باشید | عضویت]