نحوه مرتب سازی آرایه در جاوا

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

مختصری در مورد مرتب سازی

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

روش داخلی برای مرتب سازی آرایه ها در جاوا: Arrays.sort

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

• Arrays.sort(Array) : از آن برای مرتب کردن آرایه‌های انواع اولیه یا اشیاء به ترتیب صعودی استفاده کنید. از نظم طبیعی عناصر استفاده می کند.
• Arrays.sort(Array, fromIndex, toIndex) : این روش مرتب سازی بارگذاری شده به شما امکان می دهد فقط بخشی از آرایه را که توسط پارامترهای fromIndex و toIndex مشخص شده است مرتب کنید.
• Arrays.sort(Array, comparator) : این یکی برای مرتب‌سازی آرایه‌های اشیا با استفاده از یک مقایسه‌کننده سفارشی است. مقایسه کننده ترتیب عناصر را مشخص می کند.
• Arrays.parallelSort(Array) : این نسخه روش آرایه را به صورت موازی مرتب می کند و از چندین رشته برای بهبود عملکرد استفاده می کند. برای مرتب سازی آرایه های بزرگ مفید است.
• Arrays.parallelSort(Array, fromIndex, toIndex) : این نسخه بارگذاری شده از متد parallelSort امکان مرتب سازی محدوده خاصی از عناصر در آرایه را فراهم می کند .

آنها به شما این امکان را می دهند که به سرعت عناصر را بر اساس نظم طبیعی آنها یا با استفاده از یک مقایسه کننده سفارشی مرتب کنید. بیایید این روش را با دو مثال بررسی کنیم، یکی شامل رشته ها.

مثال 1: مرتب سازی رشته ها

فرض کنید آرایه ای از آلات موسیقی زهی داریم: «ویولن»، «ویولا»، «ویولن سل» و «کنترباس». برای مرتب کردن آنها بر اساس حروف الفبا می توانیم از روش Array.sort استفاده کنیم .

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

خروجی اینجاست: در این برنامه ابتدا کلاس java.util.Arrays را وارد می کنیم تا به متد Array.sort دسترسی پیدا کنیم . سپس یک آرایه زهی به نام ابزارهای حاوی نام آلات موسیقی ایجاد می کنیم. پس از آن، Arrays.sort(instruments) را فراخوانی می کنیم . بنابراین این روش یک آرایه می گیرد، عناصر را به ترتیب صعودی بر اساس ترتیب طبیعی آنها (الفبایی) مرتب می کند. در نهایت، از طریق آرایه مرتب شده حلقه می زنیم و هر ابزار را چاپ می کنیم.

مثال 2: مرتب سازی اعداد صحیح

بیایید مثال دیگری را در نظر بگیریم که در آن آرایه ای از اعداد صحیح را به ترتیب صعودی مرتب می کنیم.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

خروجی: در اینجا یک آرایه عدد صحیح به نام اعداد با چندین عنصر مرتب نشده ایجاد می کنیم. در مرحله بعد، Arrays.sort (اعداد) را فراخوانی می کنیم تا یک آرایه را به ترتیب صعودی مرتب کنیم. توجه داشته باشید که روش Array.sort آرایه اصلی را در جای خود تغییر می دهد. بنابراین برای حفظ آرایه اصلی ، قبل از مرتب سازی یک کپی تهیه کنید.

مثال 3: ترتیب نزولی

در مورد مرتب سازی نزولی چطور؟ با Arrays.sort نیز آسان است . فقط از یک مقایسه کننده سفارشی استفاده کنید. در اینجا یک مثال است:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

خروجی بعدی است: در اینجا ما یک آرایه از اعداد صحیح به نام اعداد داریم. با ارسال ()Comparator.reverseOrder به عنوان آرگومان دوم به متد Arrays.sort ، یک مقایسه کننده سفارشی را مشخص می کنیم که عناصر را به ترتیب نزولی مرتب می کند. متد Comparator.reverseOrder () مقایسه کننده ای را برمی گرداند که ترتیب طبیعی عناصر را معکوس می کند. توجه داشته باشید که در اینجا از کلاس wrapper Integer به جای نوع int اولیه استفاده می کنیم زیرا متد Comparator.reverseOrder() به اشیا نیاز دارد. اگر آرایه ای از مقادیر int اولیه دارید، باید قبل از استفاده از این روش، آنها را به اشیاء عدد صحیح تبدیل کنید . با استفاده از یک مقایسه کننده سفارشی، می توانید به راحتی آرایه ها را با استفاده از روش Arrays.sort در جاوا به ترتیب نزولی مرتب کنید.

الگوریتم های مرتب سازی کلاسیک خودنویس در جاوا

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

مرتب سازی حباب

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

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

در اینجا متد آرایه ای از اعداد صحیح را به عنوان ورودی می گیرد. حلقه بیرونی از 0 به n-1 می رود. در اینجا n اندازه آرایه است. حلقه داخلی عناصر مجاور را با هم مقایسه می کند. اگر ترتیب اشتباه باشد، روش آنها را تعویض می کند. این روش تا زمانی که کل آرایه مرتب شود تکرار می شود. در اینجا یک خروجی از برنامه ما است:

انتخاب مرتب سازی

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

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

در اینجا یک خروجی از برنامه است: بیایید گام به گام آن را توضیح دهیم. حلقه بیرونی از ابتدای آرایه تا عنصر دوم به آخر (تا n-1) تکرار می شود. این حلقه هر عنصر را یکی یکی به عنوان نقطه شروع قسمت مرتب نشده آرایه انتخاب می کند . در داخل حلقه بیرونی، minIndex را به نمایه فعلی i مقداردهی می کنیم، با فرض اینکه ایندکس کوچکترین آیتم در قسمت مرتب نشده آرایه باشد . حلقه داخلی از i+1 شروع می شود و تا آخرین عنصر آرایه بالا می رود . با مقایسه هر عنصر با حداقل عنصر فعلی ( arr[minIndex] ) فهرست کوچکترین مورد را در قسمت مرتب نشده آرایه جستجو می کند . اگر عنصری را پیدا کنیم که کوچکتر از عنصر حداقل فعلی است، minIndex را به شاخص عنصر حداقل جدید به روز می کنیم. پس از تکمیل حلقه داخلی، شاخص حداقل عنصر را در قسمت مرتب نشده آرایه پیدا کردیم . سپس با استفاده از یک دمای متغیر موقت، عنصر حداقل را با اولین عنصر از قسمت مرتب نشده تعویض می کنیم. حلقه بیرونی ادامه می یابد تا زمانی که همه عناصر مرتب شوند، به تدریج قسمت مرتب شده آرایه گسترش می یابد . در نهایت آرایه مرتب شده در متد main قبل و بعد از فراخوانی متد selectionSort چاپ می شود .

ادغام مرتب سازی

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

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

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

مرتب سازی درج

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

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

خروجی برنامه هم مثل همیشه است: در اینجا متد insertionSort الگوریتم Insertion Sort را پیاده سازی می کند. از طریق آرایه تکرار می شود و هر عنصر را به عنوان یک کلید در نظر می گیرد. کلید را با عناصر قبل از خود مقایسه می کند و در صورت بزرگتر بودن آنها را یک موقعیت جلوتر می برد و به طور موثر عناصر را جابجا می کند تا جایی برای کلید در موقعیت صحیح ایجاد شود. حلقه بیرونی از عنصر دوم ( i = 1 ) تا آخرین عنصر آرایه تکرار می شود. حلقه داخلی از عنصر فعلی ( arr[i] ) شروع می شود و به عقب می رود ( j = i - 1 ) تا زمانی که موقعیت صحیح کلید را پیدا کند یا به ابتدای آرایه برسد . در داخل حلقه داخلی، اگر یک عنصر ( arr[j] ) بزرگتر از کلید باشد، یک موقعیت به جلو منتقل می‌شود ( arr[j + 1] = arr[j] ) تا جایی برای کلید باز شود. این روند تا زمانی که موقعیت صحیح کلید پیدا شود ادامه می یابد. پس از تکمیل حلقه داخلی، کلید در موقعیت صحیح قرار می گیرد ( arr[j + 1] = کلید ). در روش main یک آرایه نمونه ایجاد می شود و قبل و بعد از مرتب سازی با استفاده از روش insertionSort چاپ می شود .

مرتب سازی سریع

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

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

خروجی اینجاست: بنابراین در اینجا ما سه روش برای پیاده سازی مرتب سازی سریع داریم. روش QuickSort سه پارامتر دارد: آرایه ای که باید مرتب شود، شاخص پایین زیرآرایه و شاخص بالای زیرآرایه. در ابتدا، بررسی می کند که آیا زیرآرایه بیش از یک عنصر دارد یا خیر. اگر چنین است، یک محور را با استفاده از روش پارتیشن انتخاب می‌کند، به صورت بازگشتی زیرآرایه را قبل از pivot مرتب می‌کند و به صورت بازگشتی زیرآرایه را بعد از Pivot مرتب می‌کند. روش پارتیشن، محور را به عنوان آخرین عنصر زیرآرایه ( arr[high] ) انتخاب می کند. شاخص پارتیشن (i) را روی اندیس کم منهای 1 تنظیم می کند. سپس از اندیس کم به شاخص بالا - 1 تکرار می شود و بررسی می کند که آیا هر عنصر کمتر یا مساوی با محور است یا خیر. اگر چنین است، عنصر را با عنصر موجود در شاخص پارتیشن (i) تعویض می کند و شاخص پارتیشن را افزایش می دهد. در نهایت، عنصر محوری را با عنصر موجود در شاخص پارتیشن + 1 تعویض می کند و شاخص پارتیشن را برمی گرداند. روش پارتیشن، محور را به عنوان آخرین عنصر زیرآرایه ( arr[high] ) انتخاب می کند. شاخص پارتیشن (i) را روی شاخص کم منهای 1 تنظیم می کند. سپس از شاخص کم به شاخص بالا - 1 تکرار می شود و بررسی می کند که آیا هر آیتم کوچکتر است یا برابر با محور. اگر چنین است، عنصر را با عنصر موجود در شاخص پارتیشن (i) تعویض می کند و شاخص پارتیشن را افزایش می دهد. در نهایت، عنصر محوری را با عنصر موجود در شاخص پارتیشن + 1 تعویض می کند و شاخص پارتیشن را برمی گرداند. متد swap یک روش کاربردی است که برای مبادله دو عنصر در آرایه استفاده می شود . در روش اصلی ، یک آرایه نمونه ایجاد شده و قبل و بعد از مرتب سازی با استفاده از روش QuickSort چاپ می شود .

نتیجه گیری

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