مرتب کردن ارایه ها

مرتب کردن ارایه ها

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

برنامه شکل 16-4 مقادیر موجود در ارایه ی ده عنصری مرتب می کند. شیوه ای که در این برنامه از ان استفاده شده است مرتب کردن حبابی یا مرتب کردن فرورونده نام دارد. چون مقادیر کوچک تر به تدریج راه خود را به صورتی حباب گونه به سمت بالای ارایه پیدا می کند و در عین حال مقادیر بزرگ تر به پایین ارایه فرو می روند. در این روش برنامه چندین باراز روی ارایه عبور می کند در هر بار عبور زوج عناصر متوالی با یکدیگر مقایسه می شوند. اگز زوجی به ترتیب صعودی است(یا مقادیر یکسانی دارتد) ان ها را به همان صورتی که هستند نگه می داریم و اگر به ترتیب نزولی است جای این دو مقدار را در ارایه عوض می کنیم.

این برنامه ابتدا a[0] را با a[1] سپس a[1] را با a[2]   a[2]را با a[3] ... a[8] را با a[9] مقایسه می کند. هر چند 10 عناصر داریم ولی فقط 9 مقایسه انجام می شود.به علت نجوه ی مقایسه های متوالی در یک عبور ممکن است یک مقدار بزرگ چند محل پایین تر برود اما یک مقدار کوچک تنها یک محل می تواند به بالا حرکت کند. در عبور اول بزرگ ترین مقدار مطمئنا به ته ارایه(محل a[9]) فرو می رود.در عبور دوم دومین مقدار بزرگ مطمئنا به محل a[8] در عبور نهم نهمین مقدار از نظر بزرگی در a[1] قرار می گیرد. پس از انجام این مراحل کوچک ترین مقدار خود به خود در a[0] جای می گیرد بنابراین برای مرتب کردن یک ارایه ی 10 عنصری تنها 9 عبور لازم است.

عمل مرتب کردن توسط حلقه ی for درونی انجام می شود. اگر جا به جایی لازم باشد این کار با سه دستورانتساب زیر انجام می گیرد:

hold = a[i];

a[i] = a[i + 1];

a[i + 1] = hold;

که متغیر اضافیhold  یکی از دو مقداری را که بابید جا به جا شوند موقتا در خود ذخیره می کند. این جا به جایی را نمی توان فقط به دو دستور انتساب

a[i] = a[i + 1];

a[i + 1] = a[i + 1];

انجام داد چون اگر مثلا  a[i]دارای مقدار 7 و a[i +1] دارای مقدار 5 باشد با اولین انتساب هر دو مقدار برابر 5 می شود و مقدار 7 از بین می رود. به همین دلیل به متغیر اضافی hold نیاز داریم.

 حسن اصلی مرتب کردن حبابی در سهولت برنامه نویسی ان است اما بسیار کند عمل می کند.این اشکال در مرتب کردن ارایه های بزرگ بیشتر نمود پیدا می کند.

----------------

#include<iostream>

#include<conio.h>

#include<iomanip>

using namespace std;

int main()

{

const int arraySize = 10;

int a[arraySize] = {2, 4, 6, 8, 10, 89, 68, 45, 37, 1};

int i, hold;

cout << "Data items in original orde\n";

for(i = 0; i < arraySize; i++)

cout << setw(4) << a[i];

for(int pass = 0; pass < arraySize - 1; pass++)

for(int i = 0; i < arraySize - 1; i++)

if(a[i] > a[i + 1]) {

hold = a[i];

a[i] = a[i + 1];

a[i+ 1] = hold;

}

cout << "\nData items in ascending order\n";

for(i = 0; i < arraySize; i++)

cout << setw(4) << a[i];

cout << endl;

getch();

return 0;

}