مقایسه الگوریتم های مرتب سازی

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

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

A = {7, 3, 9, 1}

3 7 9 1 —> 3 7 9 1 —> 3 7 1 9 Step 1
3 7 1 9 —> 3 1 7 9 —> 3 1 7 9 Step 2
1 3 7 9 —> 1 3 7 9 —> 1 3 7 9 Step 3

همانگونه که ملاحظه کردید در
مرحله اول، ابتدا 7 با 3 مقایسه شده و چون 3 از 7 کوچکتر است جایشان عوض می
شود. سپس در همان مرحله 7 با 9 مقایسه شده و چون 9 از 7 بزگتر است پس
جابجایی صورت نمی گیرد و در انتهای همان مرحله 9 با 1 مقایسه شده و بدلیل
کوچکتر بدن 1 از 9 بین آن دو جابجایی صورت می گیرد .

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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}

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 ) حتما عناصر قبل از آن مرتب هستند اما در
الگوریتم حبابی اینچنین نبود لذا بازده زمانی الگوریتم درجی از حبابی
بیشتر است، و کارایی برنامه را بالا می برد .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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++ :

1
2
3
4
5
6
7
8

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 بالا که الگوریتم
جستجوی ترتیبی است، ما دارای 3 پارامتر ورودی که شامل آرایه، طول آن و عدد
مورد جستجو هستیم. اگر عدد را پیدا کردیم تابع مقدار 1 و در غیر اینصورت
مقدار منفی 1 را برمیگرداند که می توانیم در تابع main از نتیجه این تابع
استفاده نماییم .

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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; // در اینصورت عدد در آرایه وجود ندارد
}

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

الگوريتم های مرتب سازی

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

مرتب سازی حبابی

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

مقايسه الگوريتم های مرتب سازی

الگوریتم های مرتب سازی اغلب بر اساس زیر دسته بندی می شوند:

• پیچیدگی زمانی مقایسه عناصر برحسب اندازه لیست (n) . معمولا برای یک الگوریتم مرتب سازی عادی O(n log n) بهترین حالت و O(n2) بدترین حالت است. زمان ایده آل O(n) است.
• پیچیدگی زمانی تعداد جابه جائی ها برای الگوریتم های درجا (in place).
• مصرف حافظه (و استفاده از منابع دیگر سیستم). برخی از الگوریتم های مرتب
سازی برون از جا (out place) هستند. که به محل کمکی برای نگهداری داده
های موقت علاوه بر داده های در حال مرتب شدن نیاز دارند.
• بعضی از الگوریتم ها بازگشتی یا غیر بازگشتی یا هردو هستند.
• پايداری. الگوریتم های مرتب سازی پايدار ترتیب نسبی رکوردها با کلیدهای
مساوی را برقرار می کنند. یعنی اگر دو رکورد R و S با یک کلید وجود داشته
باشد و R قبل از S در لیست اصلی آمده باشد، در لیست مرتب شده هم R قبل از S
می آید.
• متد کلی. روش مرتب سازی داده ها که می تواند درج،‌ تعویض، انتخاب، ادغام و
غیره باشد. برای مثال مرتب سازی حبابی و سریع مرتب سازی تعویضی هستند.

مرتب سازی حبابی

مرتب سازی حبابی (bubble sort) ساده ترین روش مرتب کردن داده ها می باشد.

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

عناصر کوچکتر به سمت بالای لیست حرکت می کنند به همین دلیل “حبابی” نامیده شده است.

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

با وجود سادگی این الگوریتم بسیار ناکارآمد است و به جز آموزش به ندرت در جاهای دیگر استفاده می شود.

پیاده سازی

شبه کد الگوریتم مرتب سازی حبابی به صورت زیر است:

for i:= 1 to n do
   for j:=n downto i+1 do
      if A[j-1] > A[j] then
         swap( A[j-1], A[j] )
      end if
   end for
end for

یک راه برای بهتر کردن الگوریتم فوق توجه به این نکته است که در هر
مرحله بزرگترین عنصر به انتهای لیست منتقل می شود. یعنی هر بار یک عنصر در
محل خود قرار می گیرد که در گام بعدی می توان آن را در نظر نگرفت. بنابراین
برای یک لیست با n‌ عنصر در مرحله بعد نیاز به بررسی n-1 عنصر دیگر می
باشد.

با توجه به اینکه ممکن است در مرحله ای کلیه عناصر در محل خود قرار
بگیرند اگر جا به جائی در یک گام وجود نداشته باشد به معنی مرتب بودن لیست و
خاتمه الگوریتم است.

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

do
   swapped := false
   n := n-1
   for i:=0 to n do
      if A[i] > A[i+1] then
         swap( A[i], A[i+1] )
         swapped := true
      end if
   end for
while swapped

مثال. آرایه ای با عناصر “5 1 4 2 8” را در نظر
بگیرید. گام های لازم برای مرتب سازی لیست به صورت صعودی به صورت زیر است.
در هر مرحله عماصری که مقایسه می شوند پررنگ تر نشان داده شده اند.

First Pass
( 5 1 4 2 8 )—» ( 1 5 4 2 8 )
( 1 5 4 2 8 )—» ( 1 4 5 2 8 )
( 1 4 5 2 8 )—» ( 1 4 2 5 8 )
( 1 4 2 5 8 )—» ( 1 4 2 5 8 )

Second Pass
( 1 4 2 5 8 )—» ( 1 4 2 5 8 )
( 1 4 2 5 8 )—» ( 1 2 4 5 8 )
( 1 2 4 5 8 )—» (1 2 4 5 8 )

آرایه مرتب شده است اما الگوریتم به کار خود ادامه می دهد تا به مرحله ای برسد که هیچ جابه جائی صورت نمی گیرد.
Third Pass
( 1 2 4 5 8 )—» ( 1 2 4 5 8 )
( 1 2 4 5 8 )—» ( 1 2 4 5 8 )

آرایه مرتب شده است و الگوریتم پایان می پذیرد.

ارزیابی کارائی

اگر n تعداد عناصر لیستی است که دارد مرتب می شود. در هر مرحله يک عنصر
در محل خود قرار می گيرد که در مرحله بعد نياز به بررسی ندارد بنابراين
تعداد کل مقايسه ها برابر با (n-1)+(n-2)+…+1 می شود. حاصل اين مجموع مساوی n(n-1)/2 است که پيچيدگی O(n2) را دارد. پيچيدگی در بهترين حالت O(n) است و زمانی اتفاق می افتد که داده های ليست از قبل مرتب باشد بنابراين حلقه do-while تنها يکبار اجرا می شود.

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

مرتب سازی انتخابی (selection sort) روش بهبود يافته مرتب سازی حبابی است.

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

پیاده سازی

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

for i:=0 to n-2 do
   min:=i
   for j:=(i + 1) to n-1 do
      if A[j] < A[min] then
         min:= j
      end if
   end for
   swap (A[i] , A[min])
end for

مثال. در زير مراحل مختلف برای مرتب کردن 5 عنصر “64 25 12 22 11” مشاهده می شود.

First Pass
(64 25 12 22 11) ( 11 25 12 22 64)
Second Pass
(11 25 12 22 64) ( 11 12 25 22 64)
Third Pass
(11 12 25 22 64) (11 12 22 25 64)
Forth Pass
(11 12 22 25 64) (11 12 22 25 64)

ارزیابی کارائی

در مقايسه با الگوريتم های ديگر مرتب سازی انتخابی، به دليل سادگی
ساختار، صرف نظر از ترتيب داده های ليست هميشه يک زمان اجرا را می دهد.
(n-1) جابه جائی در کل مورد نياز است که نسبت به مرتب سازی حبابی کمتر است و
اگر تعداد جابه جائی ها مهم باشد مرتب سازی انتخابی روش مناسبی است. تعداد
مقايسه ها در کل برابر است با (n-1)+(n-2)+…+1= Θ(n2).

مرتب سازی انتخابی برای ساختارهائی مانند ليست پيوندی که روش حذف و
اضافه کارائی دارند سودمند است. در اين حالت کوچکترين عنصر از ليست حذف شده
و سپس به انتهای مقاديری که قبلا مرتب شده اند اضافه می شود.

مثال.

64 25 12 22 11
11 64 25 12 22
11 12 64 25 22
11 12 22 64 25
11 12 22 25 64

مقايسه الگوريتم های مرتب سازی

توضیحات	بدترين	بهترین	حافظه	پایدار	روش	مرتب سازی
زمان ها در الگوريتم بهينه	O(n2)	O(n)	O(1)	Yes	Exchange	Bubble Sort
	O(n2)	O(n2)	O(1)	No	Selection	Selection Sort
بهترين حالت وقتی ليست مرتب است	O(n2)	O(n)	O(1)	Yes	Insertion	Insertion Sort	*
	O(n2)	O(n log n)	O(1)	Yes	Insertion	Binary Insertion Sort
	O(n log n2)	O(n log n)	O(1)	No	Insersion	Shell Sort
	O(n2)	O(n2)	O(1)	Yes	exchange	Shaker Sort
	O(n2)	O(n log n)	O(n)	No	Partionioning	Quick Sort	*
O(1) درالگوريتم غيربازگشتی حافظه	O(n log n)	O(n log n)	O(n)	Yes	Merging	Merge Sort	*
	O(n log n2)	O(n log n2)	O(n)	Yes	Merging	Odd-Even Merge Sort
	O(n2)	O(n log n)	O(n)	Yes	Indexing	Radix Sort	*
	O(k+n)	O(k+n)	O(k+n)	Yes	Indexing	Counting Sort	*
	O(n log n)	O(n log n)	O(1)	No	Selection	Heap Sort	*
	O(n2)	O(n log n)	O(n)	Yes	Selection	Tree Sort	*
	O(n2)	O(n)	O(k)	Yes	Indexing	Bucket Sort
مرتب سازي موازي است	O(log n2)	O(n log n)				Bitonic Sort
تعداد اقلام منحصر بفرد m	O(n)	O(n)	O(1)	Yes	Selection	Bingo Sort

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

مقایسه الگوریتم های مرتب سازی