فصل 3: الگوریتم‌های مرتب‌سازی
مرتب‌سازی فرآیند چیدن مجدد یک دنباله از اشیاء به‌منظور قرار دادن آنها در یک ترتیب منطقی است. به عنوان مثال، صورتحساب کارت اعتباری شما تراکنش‌ها را به ترتیب تاریخ ارائه می‌دهد و شما کتاب‌های خود را به ترتیب الفبایی نویسنده و عنوان روی قفسه کتاب‌هایتان مرتب می‌کنید. مرتب‌سازی یک عملیات اساسی در علوم کامپیوتر است و نقش حیاتی در بسیاری از کاربردها ایفا می‌کند. الگوریتم‌های مرتب‌سازی کلاسیک متنوعی وجود دارند که رویکردهای مختلفی به این مسئله دارند.
در این فصل، چندین روش مرتب‌سازی کلاسیک و ساختار داده مهمی به نام صف اولویت را بررسی می‌کنیم. ابتدا به بحث در مورد چندین روش مرتب‌سازی ابتدایی، از جمله مرتب‌سازی انتخابی، مرتب‌سازی درج و شل‌سورت می‌پردازیم. این روش‌ها در بسیاری از کاربردها مناسب هستند، اما برای مسائل بزرگ، به مرتب‌سازی ادغامی و مرتب‌سازی سریع، دو الگوریتم مرتب‌سازی بازگشتی که می‌توانند تعداد زیادی آیتم را مرتب کنند، می‌پردازیم. در پایان به بحث در مورد صف‌های اولویت و کاربرد آنها در مرتب‌سازی و سایر کاربردها می‌پردازیم.
مرتب‌سازی‌های ابتدایی
ساده‌ترین الگوریتم‌های مرتب‌سازی عملیات زیر را انجام می‌دهند:
- مرتب‌سازی انتخابی: کوچک‌ترین آیتم را پیدا کرده و آن را با اولین ورودی تعویض کنید، سپس دومین کوچک‌ترین آیتم را پیدا کرده و آن را با دومین ورودی تعویض کنید، و همین‌طور ادامه دهید.
- مرتب‌سازی درج: هر آیتم را به نوبت گرفته و آن را در موقعیت مناسب در میان آن‌هایی که قبلاً در نظر گرفته شده‌اند (نگه‌داشتن آنها مرتب) قرار دهید.
این عملیات نحوه انجام معمول وظایف مرتب‌سازی توسط انسان‌ها را منعکس می‌کند و برای اندازه‌های مسئله کوچک مؤثر هستند. با این حال، برای مرتب‌سازی آرایه‌های بزرگ مقیاس‌پذیر نیستند و عملی نمی‌شوند.
مرتب‌سازی انتخابی
مرتب‌سازی انتخابی یک الگوریتم مرتب‌سازی ساده است که به این صورت کار می‌کند: ابتدا کوچک‌ترین آیتم در آرایه را پیدا کرده و آن را با اولین ورودی (خود آن اگر اولین ورودی کوچک‌ترین باشد) تعویض کنید. سپس، بعدی کوچک‌ترین آیتم را پیدا کرده و آن را با دومین ورودی تعویض کنید. به همین ترتیب ادامه دهید تا کل آرایه مرتب شود.
حلقه داخلی مرتب‌سازی انتخابیHere is the Persian translation of the provided markdown file, with the code comments translated:
این فایل مارک‌داون را به فارسی ترجمه کنید. برای کد، کد را ترجمه نکنید، فقط توضیحات را ترجمه کنید. اینجا فایل است:
on sort برای پیدا کردن عنصر کمینه در زیرآرایه نامرتب a[i..N-1] استفاده می‌شود. شاخص عنصر کمینه در min ذخیره می‌شود. سپس، a[i] با a[min] تعویض می‌شود، که عنصر کمینه را در موقعیت نهایی خود قرار می‌دهد. همانطور که شاخص i از چپ به راست حرکت می‌کند، عناصر سمت چپ آن در آرایه مرتب شده‌اند و دیگر لمس نخواهند شد.
اینجا پیاده‌سازی مرتب‌سازی انتخابی در جاوا است:
public static void selectionSort(Comparable[] a) {
// تعداد عناصر آرایه
int N = a.length;
// برای هر عنصر آرایه
for (int i = 0; i < N; i++) {
// شاخص عنصر کمینه را در min ذخیره کن
int min = i;
// برای هر عنصر بعدی
for (int j = i+1; j < N; j++) {
// اگر عنصر جاری از عنصر کمینه کوچکتر است، شاخص آن را به min تخصیص بده
if (less(a[j], a[min])) min = j;
}
// عنصر i را با عنصر کمینه تعویض کن
exch(a, i, min);
}
}مرتب‌سازی انتخابی حدود ~N^2/2 مقایسه و N تعویض برای مرتب‌سازی یک آرایه به طول N استفاده می‌کند. زمان اجرا به ورودی حساس نیست - برای آرایه‌ای که از قبل مرتب است یا آرایه‌ای با همه کلیدهای برابر، تقریباً به همان اندازه طول می‌کشد که برای یک آرایه به ترتیب تصادفی اجرا شود.
مرتب‌سازی درج
مرتب‌سازی درج یک الگوریتم مرتب‌سازی ساده دیگر است که با ساخت آرایه نهایی مرتب شده یک آیتم در هر مرحله کار می‌کند. برای آرایه‌های بزرگ نسبت به الگوریتم‌های پیشرفته‌تر مانند مرتب‌سازی سریع، مرتب‌سازی انباشت یا مرتب‌سازی ادغام کارآمد نیست، اما مزایایی دارد:
- برای مجموعه‌های داده کوچک کارآمد است.
- در عمل کارآمدتر از مرتب‌سازی انتخابی است.
- پایدار است؛ یعنی ترتیب نسبی عناصر با کلیدهای برابر را تغییر نمی‌دهد.
- درجا است؛ یعنی فقط به مقدار ثابت
O(1)فضای حافظه اضافی نیاز دارد. - آنلاین است؛ یعنی می‌تواند فهرستی را همانطور که دریافت می‌کند مرتب کند.
اینجا پیاده‌سازی مرتب‌سازی درج در جاوا است:
public static void insertionSort(Comparable[] a) {
// تعداد عناصر آرایه
int N = a.length;
// برای هر عنصر آرایه از دوم به بعد
for (int i = 1; i < N; i++) {
// برای هر عنصر از i به سمت چپ
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
// عنصر جاری را با عنصر قبلی تعویض کن
exch(a, j, j-1);
}
}
}حلقه درونی مرتب‌سازی درج عناصر بزرگتر را یک موقعیت به راست جابه‌جا می‌کند، تا جایی برای قرار دادن عنصر جاری ایجاد شود.Here is the Persian translation of the provided markdown file, with the code comments translated:
زمان اجرای مرتب‌سازی درج‌ی به ترتیب اولیه‌ی موارد در ورودی بستگی دارد. به عنوان مثال، اگر آرایه بزرگ باشد و ورودی‌های آن از قبل مرتب شده باشند (یا تقریباً مرتب شده باشند)، مرتب‌سازی درج‌ی بسیار سریع‌تر از زمانی است که ورودی‌ها به صورت تصادفی یا معکوس مرتب شده باشند.
مرتب‌سازی شل
مرتب‌سازی شل یک گسترش ساده از مرتب‌سازی درج‌ی است که با اجازه‌ی تبادل ورودی‌های آرایه که فاصله‌ی زیادی از هم دارند، سرعت می‌گیرد تا آرایه‌های نیمه‌مرتب شده‌ای را تولید کند که می‌توان به طور کارآمد مرتب کرد، در نهایت با استفاده از مرتب‌سازی درج‌ی.
ایده این است که آرایه را به گونه‌ای مرتب کنیم که هر hامین ورودی (شروع از هر نقطه‌ای) یک زیرتوالی مرتب شده را تشکیل دهد. چنین آرایه‌ای به عنوان h-مرتب شده شناخته می‌شود. به عبارت دیگر، یک آرایه h-مرتب شده شامل h زیرتوالی مرتب شده مستقل است که با هم آمیخته شده‌اند. با h-مرتب کردن برای مقادیر بزرگ h، می‌توانیم موارد را در آرایه به فاصله‌های طولانی جابه‌جا کنیم و بنابراین آن را برای h-مرتب کردن با مقادیر کوچکتر h آسان‌تر کنیم. استفاده از چنین رویه‌ای برای هر توالی از مقادیر h که به 1 ختم می‌شود، یک آرایه مرتب شده را تولید خواهد کرد: این همان مرتب‌سازی شل است.
اینجا پیاده‌سازی مرتب‌سازی شل در جاوا آمده است:
public class MaxPQ<Key extends Comparable<Key>> {
// آرایه‌ای برای نگهداری اولویت‌ها
private Key[] pq;
// تعداد عناصر در آرایه
private int N;
// ساخت یک صف اولویت با ظرفیت داده شده
public MaxPQ(int capacity) {
pq = (Key[]) new Comparable[capacity+1];
}
// بررسی اینکه آیا صف اولویت خالی است یا خیر
public boolean isEmpty() {
return N == 0;
}
// افزودن یک کلید به صف اولویت
public void insert(Key key) {
pq[++N] = key;
swim(N);
}
// حذف و بازگرداندن بزرگ‌ترین کلید از صف اولویت
public Key delMax() {
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null;
return max;
}
// بالا بردن یک کلید در صف اولویت
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
// پایین بردن یک کلید در صف اولویت
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
private booleaاینجا ترجمه فارسی فایل مارک‌داون داده شده است. برای کد، فقط توضیحات را ترجمه کرده‌ام و خود کد را تغییر ندادم.
```java
n less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
}این کد یک پشته‌ی باینری با جهت‌گیری بیشینه را با استفاده از آرایه‌ای به نام pq برای ذخیره‌سازی درخت باینری کامل مرتب‌شده پیاده‌سازی می‌کند. عملیات insert() و delMax() با استفاده از متدهای کمکی swim() و sink() برای بازگرداندن نظم پشته، تعادل پشته را حفظ می‌کنند.
زمان‌سنج
یک نوع داده انتزاعی مفیدتر، یک انتزاع ساده و موثر برای یک زمان‌سنج است که در صفحه‌ی مقابل نشان داده شده است. برای استفاده از آن، یک شیء Stopwatch را هنگامی که می‌خواهید تایمر را شروع کنید ایجاد کنید، سپس از متد elapsedTime() برای دریافت زمان سپری‌شده به ثانیه از زمان ایجاد شیء استفاده کنید. پیاده‌سازی از System.currentTimeMillis() جاوا برای دریافت زمان کنونی به میلی‌ثانیه از نیمه‌شب اول ژانویه ۱۹۷۰ استفاده می‌کند.
متغیر نمونه start زمان ایجاد زمان‌سنج را ثبت می‌کند، و elapsedTime() از start برای محاسبه‌ی زمان سپری‌شده استفاده می‌کند. کلاینت نشان داده شده معمولی است: محاسبه‌ای را انجام می‌دهد و از یک Stopwatch برای اندازه‌گیری زمان انجام آن استفاده می‌کند. نوع داده Stopwatch یک انتزاع موثر است زیرا مفهوم زمان‌سنج (رابط) را از پیاده‌سازی (استفاده از System.currentTimeMillis() جاوا) جدا می‌کند. این جداسازی رابط و پیاده‌سازی یک ویژگی اساسی نوع‌های داده انتزاعی است که در تمام ADTهای این کتاب خواهیم دید.
خلاصه
نوع‌های داده انتزاعی عنصری ضروری در برنامه‌نویسی شی‌گرا هستند که در برنامه‌نویسی مدرن به طور گسترده استفاده می‌شوند. در این بخش، ما موارد زیر را دیده‌ایم:
- تعریف یک نوع داده انتزاعی به عنوان یک کلاس جاوا، با متغیرهای نمونه برای تعریف مقادیر نوع داده و متدهای نمونه برای پیاده‌سازی عملیات‌ها بر روی آن مقادیر.
- توسعه‌ی چندین پیاده‌سازی از همان API، با استفاده از نمایش‌های مختلف از همان نوع داده انتزاعی.فایل مارک‌داون را به فارسی ترجمه می‌کنم. برای کد، فقط نظرات را ترجمه می‌کنم و خود کد را ترجمه نمی‌کنم:
نوع داده انتزاعی
- تمایز دادن بین API ها، کلاینت ها و پیاده‌سازی های یک نوع داده انتزاعی.
- طراحی API ها برای انواع داده انتزاعی.
- توسعه کلاینت ها و کلاینت های آزمایشی برای استفاده در آزمایش و اشکال‌زدایی.
- استدلال در مورد صحت پیاده‌سازی یک نوع داده انتزاعی، با استفاده از ادعاها.
- مقایسه عملکرد پیاده‌سازی‌های مختلف از همان API.
این فعالیت‌ها بخش ضروری از توسعه هر برنامه جاوا هستند. هر برنامه جاوایی که می‌نویسیم شامل استفاده از انواع داده انتزاعی از کتابخانه‌ها خواهد بود؛ بسیاری از آنها شامل توسعه انواع داده انتزاعی جدید خواهند بود. در بخش بعدی، سه نوع داده انتزاعی اساسی را که اجزای ضروری بسیاری از برنامه‌ها هستند در نظر می‌گیریم، و در بخش 1.4 فرآیند تجزیه و تحلیل ویژگی‌های عملکردی پیاده‌سازی‌ها را به طور مفصل بررسی می‌کنیم.