مقدمه

اگر اوپن مایند را دنبال کرده باشید می دانید که می خواهیم تعدادی از الگوریتم های مرتب سازی معروف را بررسی کنیم. مرتب سازی انتخابی یا  Selection Sort  هم یکی دیگر از آن الگوریتم هاست که امروز قصد داریم به شما آموزش دهیم.

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

• مفهوم مرتب سازی
• Bubble sort
• Insertion sort
• Selection Sort
• Merge sort
• Quick sort
• Heap sort
• Distribution sorts
• Concurrent sorts
• Counting Sort

شرح الگوریتم مرتب سازی انتخابی

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

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

مثال از روند اجرای مرتب سازی انتخابی

به مثال زیر دقت کنید:

• ۳ ۵ ۱ ۲ ۴
• ۱ ۵ ۳ ۲ ۴
• ۱ ۲ ۳ ۵ ۴
• ۱ ۲ ۳ ۵ ۴
• ۱ ۲ ۳ ۴ ۵
• ۱ ۲ ۳ ۴ ۵

بخش پر رنگ تر در لیست اعداد، در واقع همان بخش مرتب شده است.

پیاده سازی مرتب سازی انتخابی

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

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

بنابراین آن کوچکترین عنصر بخش مرتب نشده به انتهای بخش مرتب شده اضافه می شود و با این کار طول بخش مرتب شده یکی اضافه می شود و از طول بخش مرتب نشده کاسته می شود.

با تکرار این کار به اندازه تعداد عناصر، آرایه مرتب شده به دست می آید.

public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int min = array[i];
        int minId = i;
        for (int j = i+1; j < array.length; j++) {
            if (array[j] < min) {
                min = array[j];
                minId = j;
            }
        }
        // swapping
        int temp = array[i];
        array[i] = min;
        array[minId] = temp;
    }
}

پیچیدگی زمانی

یافتن کوچکترین عنصر برای انتقال به بخش مرتب شده، درجه زمانی O(n) خواهد داشت، چرا که با به اندازه طول آرایه مقایسه انجام داد. همچنین این کار را به اندازه طول آرایه باید تکرار کنیم تا تمام عناصر در جایگاه مرتب قرار بگیرند.

پس درجه زمانی الگوریتم مرتب سازی انتخابی O(n^2) است.

نوشته الگوریتم مرتب سازی انتخابی یا Selection Sort اولین بار در اوپن مایند. پدیدار شد.