مرتب سازی درج در جاوا

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

مرتب سازی درج چیست؟

اساساً، مرتب‌سازی درج الگوریتمی است که توسعه‌دهندگان از آن برای سازمان‌دهی رشته‌های اعداد کوچک استفاده می‌کنند. همه مقادیر را به دو پشته تقسیم می کند - یکی مرتب شده و دیگری مرتب نشده. یکی یکی، اعداد در پشته "غیرقابل طبقه بندی" انتخاب می شوند و به ترتیب درست قرار می گیرند. بیایید نگاهی دقیق‌تر به ورودی و خروجی مرتب‌سازی درج کنیم:

• ورودی: یک آرایه A با عناصر عددی مرتب نشده: A[0،1، n، n-2...].
• خروجی: آرایه ای حاوی اعداد یکسان اما کاملا مرتب شده است. این یکی معمولاً به عنوان B شناخته می شود: B[0]B[1]...B[n-1].

روش های انگشت شماری برای استفاده از مرتب سازی درج وجود دارد - در اینجا محبوب ترین آنها وجود دارد:

• مرتب سازی عددی (ترتیب افزایشی): [1، 2، 3، 4، 5]
• مرتب‌سازی عددی (ترتیب نزولی): [5، 4، 3، 2، 1]
• مرتب سازی بر اساس حروف الفبا: [a, b, c, d]

توجه: اگر یک آرایه خالی یا یک تکتون دارید، این ها به طور پیش فرض مرتب شده اند.

درک نظریه مرتب سازی درج

قبل از بررسی کد پشت مرتب سازی درج، اجازه دهید الگوریتم را با استفاده از زبان غیر فنی تجزیه کنیم. از آنجایی که کد مرتب سازی را به ترتیب صعودی نشان خواهیم داد، منطقی است که در این پست الگوریتم را گام به گام توضیح دهیم. مرحله 1. تکرار بین arr[1]و arr[n]جایی که nیک مقدار عددی معمولاً کمتر از 10 است. مرحله 2. عنصری را که انتخاب کردید (معروف به key) با عدد قبلی در دنباله با استفاده از sort()روش مقایسه کنید. مرحله 3. اگر همه عناصر کوچکتر از جانشینان خود هستند، مقایسه را تکرار کنید تا مقدار بزرگتری پیدا کنید. مرحله 4. برای ایجاد یک دنباله مرتب شده، یک مقدار بزرگتر را یک موقعیت فراتر از مقدار کوچکتر عوض کنید. مرحله 5. این فرآیند را تکرار کنید تا زمانی که یک رشته مرتب شده از کاراکترها به دست آورید

مرتب سازی آرایه های اولیه

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

1. یک آرایه برای مرتب سازی اعلام کنید

برای شروع، اجازه دهید یک رشته از مقادیر را ایجاد کنیم که بعداً با استفاده از جاوا نمایش خواهیم داد. برای استفاده از مرتب سازی درج، باید یک آرایه ایجاد کنید. برای آن، استفاده کنیدint[]

int[] arrayA = {10, 14, 20, 30};

2. از sort_arr برای پیاده سازی الگوریتم استفاده کنید

متد sort_arr یکی از رایج‌ترین روش‌ها برای پیاده‌سازی مرتب‌سازی درج است. در عمل به این صورت است:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. یک حلقه و یک تکرار کننده ایجاد کنید

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

for(int i=0; i< sort_arr.length; ++i){

اکنون که یک حلقه عملکردی دارید، زمان ایجاد یک تکرار کننده است که همه عناصر را به ترتیب دلخواه مرتب می کند. از این به بعد تکرار کننده را " " می نامیم j.

int j = i;

4. ایجاد یک "حلقه در حالی که"

وقتی نوبت به مرتب سازی درج می شود، یک حلقه "while" برای یک آرایه مرتب شده جدید ضروری است. برای تنظیم آن برای مرتب‌سازی درج مرتبه صعودی، یک توسعه‌دهنده باید دو شرط را رعایت کند:

• مقدار اختصاص داده شده به j باید بزرگتر از 0 باشد
• مقدار اختصاص داده شده به باید بزرگتر از شاخص j-1باشدj

به محض اینکه هر دو شرط در حلقه while درست باشد، مقدار کلید آرایه با jشاخص برابر خواهد شد.

5. مرتب سازی آرایه

پس از راه‌اندازی حلقه while، مقادیر jو j-1تا زمانی که یکی یا هر دو شرط در حلقه while از کار بیفتد، تعویض می‌شوند. به طور مشابه، مرتب سازی برای هر مقدار در حلقه for تکرار می شود تا زمانی که شرایط حلقه for نیز از بین برود. در اینجا نحوه عملکرد مرتب سازی درج در عمل آمده است:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

مرتب سازی ArrayList

اگرچه درک ریاضی پشت مرتب سازی درج مهم است، اما وقتی نوبت به توسعه نرم افزار واقعی می رسد، ArrayLists را بسیار بیشتر از دنباله ها در آرایه های اولیه مرتب می کنید. در اینجا یک راهنمای گام به گام برای مرتب سازی ArrayList آورده شده است:

1. یک کلاس جدید Elementبرای آیتم های متعلق به مجموعه ایجاد کنید.

   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }

2. در یک مجموعه، یک روش وجود دارد compareTo()- ما از آن برای مقایسه شناسه‌های دو عنصر استفاده می‌کنیم.

   public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }

3. الگوریتم را اعمال کنید و چند حلقه برای مرتب کردن اشیا ArrayListبه جای مقایسه آنها ایجاد کنید.

   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }

4. ArrayListهمانطور که در زیر نشان داده شده است، می توانید عناصر بیشتری را نیز به آن اضافه کنید :

   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);

5. حالا نوبت مرتب سازی است:

   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array
   list.forEach(e -> System.out.print(e.getId() + ", "));

6. حالا بیایید ورودی و خروجی را با هم مقایسه کنیم تا مطمئن شویم که هیچ اشتباهی نکرده ایم. در اینجا مقایسه رشته ای است که به عنوان مثال استفاده کردیم.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

مشکلات تمرین مرتب سازی درج

اکنون که از این الگوریتم مرتب‌سازی استفاده کرده‌اید، وقت آن است که مهارت‌های نظری و عملی خود را آزمایش کنید. آزمون تئوری شماره 1 به شما یک آرایه [1، 4، 6، 8] داده می شود و یک عنصر جدید n = 7 به آن اضافه می کنید. تعداد مقایسه هایی که باید انجام دهید تا دنباله ای مرتب شده از اعداد را بدست آورید چقدر است؟ مقدار نهایی شاخص n را در آرایه نشان دهید. آزمون تئوری شماره 2 در یک مصاحبه شغلی، یک سرپرست تیم از شما می خواهد ثابت کنید که درج مرتب سازی روشی ناکارآمد است. با توجه به یک رشته عددی از [0، 3، 6، 8، 9]، ترتیب توالی ورودی شما برای به حداکثر رساندن زمان اجرای مورد نیاز برای مرتب سازی چگونه باید باشد؟ تمرین مشکل آرایه [0، 1، 4، 5، 2، 3، 7، 9، 8] را با استفاده از مرتب سازی درج برای جاوا به ترتیب صعودی مرتب کنید.

نتیجه

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