مقدمه

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

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

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

شرح الگوریتم مرتب سازی درجی

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

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

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

مثال از عملکرد مرتب سازی درجی

برای مثال، اگر در آرایه زیر بخش پررنگ، بخش مرتب شده باشد (به صورت صعودی)، ادامه اجرای الگوریتم به صورت زیر است:

۳ ۵ ۷ ۸ ۴ ۲ ۱ ۹ ۶ :

در این مرحله ۴ را به آرایه در جایگاه بعد از ۳ درج می کنیم. برای این کار با حرکت ۴ به سمت چپ خود، تمام عناصر بعد از ۳ به سمت راست Shift می شوند. به انتقال های زیر دقت کنید:

۳ ۵ ۷ x 8 ۲ ۱ ۹ ۶

۳ ۵ x 7 8 ۲ ۱ ۹ ۶

۳ x 5 7 8 ۲ ۱ ۹ ۶

۳ x 5 7 8 ۲ ۱ ۹ ۶

 

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

تصویر متحرک زیر هم اجرای بخش های مختلف الگوریتم را روی یک مثال دیگر نشان می دهد.

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

پیاده سازی الگوریتم مرتب سازی درجی

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

public static void insertionSort(int array[]) {
    for (int j = 1; j < array.length; j++) {
        int current = array[j];
        int i = j-1;
        while ((i > -1) && (array[i] > current)) {
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = current;
    }
}

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

سپس اولین عنصر از بخش غیرمرتب (همان عنصر دوم آرایه) با آخرین عنصر بخش مرتب شده مقایسه می شود. عنصر غیرمرتب فعلی در متغیر

current

به طور موقت نگهداری می شود و اگر بزرگترین عنصر داخل بخش مرتب از مقدار

current

هم بزرگتر باشد، آن عنصر و همه سمت راستی هایش هُل داده می شوند تا جای عنصر

current

باز شود و به بخش مرتب شده منتقل شود.

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

while

انجام شده است.

اما اگر عنصر

current

از بالاترین و بزرگترین عنصر بخش مرتب کوچکتر نباشد چه؟ در آن صورت جا به جایی نداریم و عنصر داخل

current

به سادگی به انتهای بخش مرتب اضافه می شود و به این شکل به بخش مرتب وارد می شود.

با تکه کد زیر هم می توانید تابع

insertionSort

 تعریف شده را در تابعی دیگر به کار بگیرید.

int[] array = new int[]{1, 7, 5, 6, 9, 4, 2, 3};
insertionSort(array);
System.out.println(Arrays.toString(array))

نتیجه اجرا هم به صورت زیر و یک آرایه صعودی مرتب شده است:

[1, 2, 3, 4, 5, 6, 7, 9]

پیچیدگی زمانی مرتب سازی درجی

در ادامه و برای بررسی پیچیدگی زمانی الگوریتم مرتب سازی درجی، به بدترین حالت ممکن در اجرا می پردازیم.

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

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

 

 

 

این مطلب با تلخیص از مرجع https://stackabuse.com/insertion-sort-in-java نوشته شده است.

 

 

نوشته الگوریتم مرتب سازی درجی یا Insertion sort اولین بار در اوپن مایند. پدیدار شد.