Java에서 배열을 정렬하는 방법

정렬은 프로그래밍에서 가장 일반적이고 필요한 작업 중 하나입니다. 특정 순서로 일부 요소 집합의 순서를 나타냅니다. 이 문서는 Java에서 배열을 정렬하는 표준 방법에 관한 것입니다.

정렬에 대해 간략히 설명합니다.

따라서 정렬은 데이터 집합의 순서를 지정하는 것입니다. 우리의 경우에는 배열입니다. 배열이나 기타 데이터 구조를 정렬하는 목적은 컬렉션의 데이터를 더 쉽게 찾고, 조작하고, 구문 분석할 수 있도록 하는 것입니다. 프로그래머는 정렬이 너무 자주 필요하므로 모든 프로그래밍 언어에는 배열, 목록 및 기타 정렬된 데이터 구조를 정렬하기 위한 내장 메서드가 포함되어 있습니다. 이러한 메서드를 사용하려면 해당 메서드를 호출하세요. 작업은 최대한 단순화됩니다. 일반적으로 내장된 메소드는 최대한 최적화됩니다. 대부분의 경우 작업이나 프로젝트에 사용하는 것이 좋습니다. 그러나 거의 모든 프로그래머는 연구 중에 정렬 알고리즘을 스스로 구현해야 합니다. 따라서 이 완벽한 연습을 통해 프로그래밍의 본질을 이해하는 방법을 배울 수 있습니다. 또한 작업 중에 비표준적인 정렬 방법이 필요한 경우도 있습니다. 많은 정렬 알고리즘이 있습니다. 데이터 세트의 유형이나 크기에 따라 강점과 약점이 있습니다. 표준 정렬 알고리즘에는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬 및 퀵 정렬이 포함됩니다.

Java에서 배열을 정렬하기 위한 내장 메소드: Arrays.sort

가장 간단한 것부터 시작해 보겠습니다. 누군가 이미 우리를 위해 Java로 배열을 정렬하는 방법을 작성해 주었습니다. 이 메소드는 Arrays 클래스, 특히 java.util.Arrays 에 있습니다 . 이 클래스에는 정렬, 검색 등 배열 작업을 위한 다양한 메서드가 포함되어 있습니다. Arrays.sort 메소드는 문자열, 정수 또는 기타 요소 가 포함되어 있는지 여부에 관계없이 Java에서 배열을 정렬하는 편리한 방법을 제공합니다. Java에는 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 메서드 버전을 사용하면 Array의 특정 요소 범위를 정렬할 수 있습니다 .

이를 통해 자연스러운 순서에 따라 또는 사용자 지정 비교기를 사용하여 요소를 빠르게 정렬할 수 있습니다. 문자열과 관련된 두 가지 예를 통해 이 방법을 살펴보겠습니다.

예 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);
        }
    }
}

출력은 다음과 같습니다. 이 프로그램에서는 먼저 Array.sort 메소드 에 액세스하기 위해 java.util.Arrays 클래스를 가져옵니다 . 그런 다음 악기 이름을 포함하는 Instrument라는 문자열 배열을 만듭니다. 그 다음에는 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(numbers)를 호출하여 배열을 오름차순으로 정렬합니다. Array.sort 메서드 는 원래 배열을 내부에서 수정합니다. 따라서 원본 Array 를 유지하려면 정렬하기 전에 복사본을 만드세요.

예시 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 () 메서드는 요소의 자연 순서를 반대로 바꾸는 비교기를 반환합니다. 여기서는 Comparator.reverseOrder() 메서드에 객체가 필요하기 때문에 기본 int 유형 대신 Integer 래퍼 클래스를 사용합니다 . 기본 int 값의 배열이 있는 경우 이 접근 방식을 사용하기 전에 이를 Integer 개체 로 변환해야 합니다 . 사용자 정의 비교기를 사용하면 Java의 Arrays.sort 메소드 를 사용하여 배열을 내림차순으로 쉽게 정렬할 수 있습니다 .

Java로 자체 작성된 고전 정렬 알고리즘

컴퓨터 공학을 독립적으로 공부하거나 대학에서 공부하고 있다면 이미 배열 정렬 과제를 본 적이 있을 것입니다 . 다양한 정렬 알고리즘이 있으며 이 기사에서는 그 중 일부를 구현하겠습니다. 일반적으로 알고리즘을 구현하기가 쉬울수록 효율성이 떨어집니다. 프로그래머는 알고리즘의 효율성을 작업 시간과 리소스에 사용되는 메모리로 측정합니다. 이것이 우리 기사의 주제는 아니지만 Java의 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은 배열의 크기입니다. 내부 루프는 인접한 요소를 비교합니다. 순서가 잘못된 경우 메서드는 순서를 바꿉니다. 이 절차는 전체 배열이 정렬될 때까지 반복됩니다. 다음은 우리 프로그램의 출력입니다:

선택 정렬

선택 알고리즘은 정렬되지 않은 부분에서 가장 작은 요소를 반복적으로 찾아 처음에 배치하여 배열을 정렬합니다. Java로 작성해 보겠습니다.

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)까지 반복됩니다. 이 루프는 Array 의 정렬되지 않은 부분의 시작점으로 각 요소를 하나씩 선택합니다 . 외부 루프 내에서 minIndex를 현재 인덱스 i 로 초기화하고 이를 Array 의 정렬되지 않은 부분에서 가장 작은 항목의 인덱스라고 가정합니다 . 내부 루프는 i+1 부터 시작하여 Array 의 마지막 요소까지 올라갑니다 . 각 요소를 현재 최소 요소( arr[minIndex] ) 와 비교하여 배열 의 정렬되지 않은 부분에서 가장 작은 항목의 인덱스를 검색합니다 . 현재 최소 요소보다 작은 요소를 찾으면 minIndex를 새 최소 요소의 인덱스로 업데이트합니다. 내부 루프가 완료된 후 Array 의 정렬되지 않은 부분에서 최소 요소의 인덱스를 찾았습니다 . 그런 다음 임시 변수 temp를 사용하여 최소 요소를 정렬되지 않은 부분의 첫 번째 요소와 교환합니다. 외부 루프는 모든 요소가 정렬될 때까지 계속되며 점차적으로 Array 의 정렬된 부분을 확장합니다 . 마지막으로, 정렬된 배열은 SelectionSort 메서드 호출 전후에 기본 메서드에서 인쇄됩니다 .

병합 정렬

병합 정렬은 배열을 더 작은 하위 배열로 재귀적으로 나누고, 정렬한 다음 병합하여 정렬된 배열을 얻는 분할 정복 알고리즘입니다 . 병합 정렬은 특히 안정성과 최악의 시간 복잡도 보장이 필요할 때 안정적이고 널리 사용됩니다.

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 + " ");
        }
    }
}

여기서의 출력은 다음과 같습니다. 어떻게 작동하는지 좀 더 자세히 설명해 보겠습니다. 알고리즘은 기본 사례에 도달할 때까지( 배열에 요소가 1개 또는 0개 있는 경우) 배열을 반복적으로 두 부분으로 나눕니다. 그런 다음 병합 방법을 사용하여 정렬된 절반을 다시 병합합니다. 병합 메서드는 원본 배열 과 왼쪽 및 오른쪽 하위 배열(왼쪽 및 오른쪽)의 세 가지 배열을 입력으로 사용합니다. 왼쪽 및 오른쪽 하위 배열의 요소를 비교하여 정렬된 순서로 원본 배열 에 병합합니다.

삽입 정렬

삽입 정렬은 정렬되지 않은 부분의 요소를 정렬된 부분의 올바른 위치에 반복적으로 삽입하는 방식으로 작동합니다. 작은 데이터 세트나 거의 정렬된 데이터에 대해 잘 수행됩니다.

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 + " ");
        }
    }
}

프로그램의 출력은 평소와 같습니다: 여기서 insertSort 메소드는 삽입 정렬 알고리즘을 구현합니다. 배열을 반복 하고 각 요소를 키로 간주합니다. 키를 이전 요소와 비교하고 더 큰 경우 한 위치 앞으로 이동하여 요소를 효과적으로 이동하여 올바른 위치에 키를 위한 공간을 만듭니다. 외부 루프는 두 번째 요소( i = 1 )부터 배열의 마지막 요소까지 반복됩니다. 내부 루프는 현재 요소( arr[i] )에서 시작하여 키의 올바른 위치를 찾거나 Array 의 시작 부분에 도달할 때까지 뒤로( j = i - 1 ) 이동합니다 . 내부 루프 내에서 요소( arr[j] )가 키보다 큰 경우 키를 위한 공간을 만들기 위해 한 위치 앞으로 이동합니다( arr[j + 1] = arr[j] ). 이 프로세스는 키의 올바른 위치를 찾을 때까지 계속됩니다. 내부 루프가 완료된 후 키는 올바른 위치( arr[j + 1] = key )에 배치됩니다. 기본 메서드에서는 insertSort 메서드를 사용하여 정렬하기 전과 후에 예제 배열을 만들고 인쇄합니다.

빠른 정렬

Quick Sort는 피벗 요소를 선택하고 피벗 주위에 배열을 분할하는 분할 정복 알고리즘입니다. 일반적으로 Quick Sort는 낮은 상수 요소로 인해 중소 규모 데이터 세트의 경우 Merge Sort보다 빠릅니다.

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 메서드 는 정렬할 배열, 하위 배열의 낮은 인덱스, 하위 배열의 높은 인덱스라는 세 가지 매개 변수를 사용합니다 . 처음에는 하위 배열에 요소가 두 개 이상 있는지 확인합니다. 그렇다면 파티션 방법을 사용하여 피벗을 선택하고 피벗 이전에 하위 배열을 재귀적으로 정렬하고 피벗 이후에 하위 배열을 재귀적으로 정렬합니다. 분할 방법은 피벗을 하위 배열( arr[high] ) 의 마지막 요소로 선택합니다 . 파티션 인덱스(i)를 낮은 인덱스에서 1을 뺀 값으로 설정합니다. 그런 다음 낮은 인덱스에서 높은 인덱스(1)까지 반복하고 각 요소가 피벗보다 작거나 같은지 확인합니다. 그렇다면 요소를 파티션 인덱스(i)의 요소와 교환하고 파티션 인덱스를 증가시킵니다. 마지막으로 피벗 요소를 파티션 인덱스 + 1의 요소와 교환하고 파티션 인덱스를 반환합니다. 분할 방법은 피벗을 하위 배열( arr[high] ) 의 마지막 요소로 선택합니다 . 파티션 인덱스(i)를 낮은 인덱스에서 1을 뺀 값으로 설정합니다. 그런 다음 낮은 인덱스에서 높은 인덱스(1)까지 반복하고 각 항목이 피벗보다 작거나 같은지 확인합니다. 그렇다면 요소를 파티션 인덱스(i)의 요소와 교환하고 파티션 인덱스를 증가시킵니다. 마지막으로 피벗 요소를 파티션 인덱스 + 1의 요소와 교환하고 파티션 인덱스를 반환합니다. swap 메소드는 Array 의 두 요소를 교환하는 데 사용되는 유틸리티 메소드입니다 . 기본 메서드 에서는 QuickSort 메서드 를 사용하여 정렬하기 전과 후에 예제 배열을 만들고 인쇄합니다 .

결론

이 기사에서 당신은 Java 언어로 배열을 정렬하는 방법을 알아냈습니다. 내장된 Arrays.sort 메소드를 사용하거나 버블 정렬, 병합 정렬 등과 ​​같은 널리 사용되는 정렬 메소드의 구현을 직접 작성할 수 있습니다. 또한 자신만의 정렬 방법을 침입해 볼 수도 있습니다. 그것은 당신의 임무에 달려 있습니다. 정렬 문제를 빨리 해결해야 한다면 미리 작성된 방법을 사용하면 됩니다. 프로그래밍을 배우고 더 잘하려고 노력한다면 스스로 몇 가지 정렬 방법을 작성하는 것이 정말 좋은 생각입니다.