مرتب سازی درجی (Insertion sort) در جاوا

سلام دوستان در این سری از آموزش برنامه نویسی جاوا به آموزش مرتب سازی درجی (Insertion sort) در جاوا می پردازیم شاید سوال ابتدای کار سوال شما این باشد که مرتب سازی درجی (Insertion sort) چیست ؟ در ادامه به سوال نیز پاسخ خواهیم داد با ما همراه باشید تا نحوه پیاده سازی الگوریتم مرتب سازی درجی (Insertion sort) را یاد گیرید.

نحوه کارکرد الگوریتم مرتب سازی درجی (Insertion sort)

یک الگوریتم مرتب‌سازی ساده بر مبنای مقایسه است و برای زمانی که تعداد داده زیاد باشد اصلا مناسب نیست در الگوریتم مرتب سازی درجی (Insertion sort) موقعیت یا مکان (Position) از 1 شروع می شود و همه عنصر ها را به چپ میاورد تا در جای درست خود قرار گیرند.
در ادامه یک gif از مرتب سازی درجی را مشاهده خواهید کرد.

یک مثال ساده از الگوریتم مرتب سازی درجی (Insertion sort)

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

مزایای مرتب سازی درجی (Insertion sort)

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

معایت مرتب سازی درجی (Insertion sort)

کند است.
برای داده های زیاد کارآمد نیست.
تعداد Shift در داده های زیاد بسیار بالاست (به علت جابه جایی)
نیازمند فضای زیاد

در ادامه مثال مربوط به جاوا آن را برای شما قرار می دهیم.

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

public static void insertionSort(int array[]) {

int n = array.length;

for (int j = 1; j < n; j++) {

int key = array[j];

int i = j-1;

while ( (i > -1) && ( array [i] > key ) ) {

array [i+1] = array [i];

i--;

}

array[i+1] = key;

}

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

public static void main(String a[]){
        int[] arr1 = {9,14,3,2,43,11,58,22};
        System.out.println("Before Insertion Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
        System.out.println();
        insertionSort(arr1);
        System.out.println("After Insertion Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
    }
}

public static void main(String a[]){

int[] arr1 = {9,14,3,2,43,11,58,22};

System.out.println("Before Insertion Sort");

for(int i:arr1){

System.out.print(i+" ");

}

System.out.println();

insertionSort(arr1);

System.out.println("After Insertion Sort");

for(int i:arr1){

System.out.print(i+" ");

}

در نهایت خروجی کد همانند زیر است.

Before Insertion Sort
9 14 3 2 43 11 58 22
After Insertion Sort
2 3 9 11 14 22 43 58

Before Insertion Sort

9 14 3 2 43 11 58 22

After Insertion Sort

2 3 9 11 14 22 43 58

این آموزش هم به پایان رسید.
موفق و پیروز باشید.

مطالعه بیشتر

مرتب سازی درجی (Insertion sort) در جاوا

نحوه کارکرد الگوریتم مرتب سازی درجی (Insertion sort)

یک مثال ساده از الگوریتم مرتب سازی درجی (Insertion sort)

مزایای مرتب سازی درجی (Insertion sort)

معایت مرتب سازی درجی (Insertion sort)

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

نحوه کارکرد الگوریتم مرتب سازی درجی (Insertion sort)

یک مثال ساده از الگوریتم مرتب سازی درجی (Insertion sort)

مزایای مرتب سازی درجی (Insertion sort)

معایت مرتب سازی درجی (Insertion sort)

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

اشتراک گذاری در شبکه های اجتماعی