24-5 مرتب سازی سریع (quicksort)

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

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

ب) مرحله ی بازگشتی: مرحله((الف)) را روی هر یک از ارایه های نامرتب انجام دهید.

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

 45    68    12    10    8    89    4    6    2    37

الف) از سمت راست ارایه تک تک عناصر را با 37 مقایسه کنید تا وقتی که عنصری کوچک تر از 37 پیدا کنید. سپس جای این دو عنصر را تعویض کنید. در این جا اولین عنصر کوچک تر از 37 عدد 12 است. پس 37 را با 12 جا به جا می کنیم. ارایه به صورت زیر در می اید:

45    68    37   10    8    89    4    6    2   12

عنصر 12 به صورت ایتالیک نوشته شده است تا مشخص شود که الان با عنصر 37 تعویض شده است.

ب) بعد از 12 از سمت چپ ارایه هر یک از عناصر با با 37 مقایسه کنید تا زمانی که عنصری بزرگ تر از 37 پیدا کنید. سپس جای این دو عنصر را با هم عوض کنید. در این جا اولین عنصر بزرگ تر از 37 عدد 89 است که بعد از تعویض ارایه به صورت زیر می شود:

45    68    89   10    8    37    4    6    2   12

ج) از سمت راست ارایه ولی از عنصر قبل 89 هر یک از عناصر را با 37 مقایسه کنید که عنصری کوچک تر از 37 پیدا شود. سپس جای این عنصر را با 37 تعویض کنید. در این جا عنصر کوچک تر از 37 عدد 1 است بعد از جابه جایی ارایه به صورت زیر می شود:

45    89    37   8    10    4    6   2    12   

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

بعد از افراز ارایه ی بالا دو زیر ارایه ی نا مرتب داریم. زیر ارایه مقدیر کوچک تر از 37 شامل مقادیر ,10 ,8

12 ,2 ,6 ,4 و زیر مقادیر بزرگ تر از 37 شامل مقادیر 89, 68, 45 است. حال هر دو زیر ارایه به همین ترتیب افراز شده و کار مرتب کردن ارایه ادامه می یابد. با ایت توضیحات تابعی بازگشتی به نام quicksort بنویسید که یک ارایه ی یک بعدی از نوع صحیح را مرتب نماید. این تابع باید یک ارایه صحیح و اندیس شروع و پایان ان را بع عنوان ارگومان دریافت و ان را مرتب نماید. برای انجام مرحله ی افراز quicksort باید تابع partition را فراخوانی کنید.

#include<iostream>

using std::cout;

using std::endl;

#include<iomanip>

using std::setw;

#include<cstdlib>

#include<ctime>

const int SIZE = 10, MAX_NUMBER = 1000;

void quicksort(int * const, int, int);

void swap(int * const, int * const);

int main()

{

int arrayToBeSorted[SIZE] = {0};

int loop;

srand(time(0));

for(loop = 0; loop < SIZE; ++loop)

arrayToBeSorted[loop] = rand() % MAX_NUMBER;

cout << "initial array values are:\n";

for(loop = 0; loop < SIZE; ++loop)

cout << setw(4) << arrayToBeSorted[loop];

cout << "\n\n";

if(SIZE == 1)

cout << "Array is sorted: " << arrayToBeSorted[0] << 'n';

else {

quicksort(arrayToBeSorted, 0, SIZE - 1);

cout << "The sorted array values are:\n";

for(loop = 0; loop < SIZE; ++loop)

cout << setw(4) << arrayToBeSorted[loop];

cout << endl;

}

return 0;

}

void quicksorted(int * const array, int first, int last)

{

int partition(int * const, int, int);

int currentLocation;

if(first >= last)

return;

currentLocation = partition(array, first, last);   // plase an element

quicksort(array, first, currentLocation - 1);      // sort left side

quicksort(array, currentLocation + 1, last);       // sort right side

}

int partition(int * const array, int left, int right)

{

int position = left;

while(true) {

while(array[position] <= array[right] && position != right)

--right;

if(position == right)

return position;

if(array[position] > array[right]) {

swap(&array[position], &array[right]);

position = right;

}

while(array[left] <= array[position] && left != position)

++left;

if(position == left)

return position;

if(array[left] > array[position]) {

swap(&array[position], &array[left]);

position = left;

}

}

}

void swap(int * const ptr1, int * const ptr2)

{

int temp;

temp = *ptr1;

*ptr1 = *ptr2;

*ptr2 = temp;

}