[Java] 배열 정렬(Sorting)

JTI·2022년 11월 21일

Java

☕️ Java

목록 보기

26/59

💡 정렬 알고리즘 비교

컴퓨터에서 정렬을 수행하는 이유 중 가장 큰 이유는 이진탐색이 가능한 데이터를 만들기 위해서이다. 하지만 정렬된 데이터만 이진탐색이 가능하다.
정렬되어있는 데이터는 안정감을 느낀다.

오른쪽으로 갈수록 메모리가 젤 크다.
오른쪽으로 갈수록 비용이 많이 들고 느리고 안좋다.

🤔 자바는 머지솔트였는데 다른 걸로 바뀐 것 같다.

💡 Arrays.sort()

대부분의 경우 배열에 저장된 값은 랜덤 순서로 나타난다.
Java의 Arrays 클래스를 사용하면 배열을 조작하는 데 사용할 수 있는 다양한 방법을 액세스할 수 있다.

❗️ 배열 기본 정렬
Arrays.Sort()

기본적으로 객체는 Comparable 이 구현되어있다.
sort() 는 Comparable 에 의해 리턴되는 값을 비교하여 오름차순 또는 내림차순으로 배열을 정렬한다.

📎 Arrays.sort() 사용법

int 배열 정렬 int 배열 정렬 (오름차순, 내림차순)

int 배열, 부분 정렬

String 배열 정렬

String 배열, 문자 길이 순서로 정렬

객체 배열 정렬

1차원 배열은 Sort에 해당 배열을 인자로 넣어 기본적으로 오름차순 정렬을 하는데, 내림차순 정렬을 하기 위해서는 두번째 인자로 Collections.reverOrder()를 사용한다.

💡 int 배열 정렬 (오름차순, 내림차순)

아래와 같이 int 배열이 있다.
Arrays.sort()의 인자로 이 배열을 전달하면 오름차순으로 정렬해 준다.
sort() 함수 내부에서 변수 arr의 순서를 변경해주기 때문에 따로 arr에 할당해줄 필요가 없다.

int[] arr = {2,	6, 7, 3, 9}; // 그냥 정렬은 오름차순

Arrays.sort(arr);

System.out.println(Arrays.toString(arr));

[결과값]
[2, 3, 6, 7, 9]

✏️ 내림차순 정렬

내림차순으로 정렬하려면 sort() 의 인자에 추가로 Collections.reverseOrder() 를 전달해야 한다.

Integer[] arr = {1, 26, 17, 25, 99, 44, 303};

Arrays.sort(arr, Collections.reverseOrder());

System.out.println(Arrays.toString(arr));

[결과값]
[303, 99, 44, 26, 25, 17, 1]

❗️ 사실 Collections.reverseOrder()는 Comparator 객체이다.
Comparator 는 직접 구현해야하지만, 내림차순은 자주 사용되기 때문에 Collections 에서 기본으로 제공해주고 있다.

💡 int 배열, 부분 정렬

배열의 일부분만 정렬할 수 있다.
sort(int[] a, int fromIndex, int toIndex)

조심해야 되는 것은, 어떤 것에서 어떤 것까지의 개념이 나라마다 다르다.

fromIndex: 포함한다.
toIndex: 포함안한다.

예를 들어 2 ,3 ,4라고 되어있으면 우리나라는 2, 3, 4가 다 포함인 것이 익숙하지만, 외국에서는 2, 3만 포함한다.

int[] arr = {2,	10, 7, 3, 9, 4};

Arrays.sort(arr, 1, 4);

System.out.println(Arrays.toString(arr));

[결과값]
[2, 3, 6, 7, 9]

9는 정렬되지 않은 것으로 확인할 수 있다.

💡 String 배열 정렬

String 배열도 Int와 동일하다.
아래처럼 구현하면, 알파벳의 아스키 값으로 비교하여 정렬한다.

String[] strs = {"Banana", "Orange", "Cherry", "Kiwi", "Apple"};

Arrays.sort(strs);

System.out.println(Arrays.toString(strs));

[결과값]
[Apple, Banana, Cherry, Kiwi, Orange]

내림차순도 위와 마찬가지이다.

String[] strs = {"Banana", "Orange", "Cherry", "Kiwi", "Apple"};

Arrays.sort(strs, Collections.reverseOrder());

System.out.println(Arrays.toString(strs));

[결과값]
[Orange, Kiwi, Cherry, Banana, Apple]

✏️ String 배열, 문자열 길이 순서로 정렬

만약 문자열 길이 순서로 정렬을 하고 싶을 때가 있다.
이럴 때는 직접 Comparator 를 구현해야 한다.

다음과 같이 문자열 길이를 비교하는 Comparator 를 구현할 수 있다.

String[] arr = {"Apple", "Kiwi", "Orange", "Banana", "Watermelon", "Cherry"};

Arrays.sort(arr, new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
});

System.out.println(Arrays.toString(arr));

[결과값]
[Kiwi, Apple, Orange, Banana, Cherry, Watermelon]

💡 객체 배열 정렬

객체를 갖고 있는 배열도 정렬할 수 있다.
이 경우에는 클래스에 Comparable 을 구현하여 비교할 수 있게 해야 한다.

다음과 같이 Fruit라는 클래스를 만들었다.
이 클래스는 Comparable<Fruit> 를 구현하고 있다.

public static class Fruit implements Comparable<Fruit> {
    private String name;
    private int price;
    public Fruit(String name, int price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "{name: " + name + ", price: " + price + "}";
    }

    @Override
    public int compareTo(@NotNull Fruit fruit) {
        return this.price - fruit.price;
    }
}

위의 클래스에서 Comparable 은 자기 자신의 클래스와 인자로 전달되는 Fruit의 price를 비교한다.

이제 다음과 같이 Fruit 배열을 sort() 로 정렬할 수 있다.

Fruit[] arr = {
        new Fruit("Apple", 100),
        new Fruit("Kiwi", 500),
        new Fruit("Orange", 200),
        new Fruit("Banana", 50),
        new Fruit("Watermelon", 880),
        new Fruit("Cherry", 10)
};

Arrays.sort(arr);

System.out.println("Sorted arr[] : " + Arrays.toString(arr));

[결과값]
Sorted arr[] : [{name: Cherry, price: 10}, {name: Banana, price: 50}, {name: Apple, price: 100}, {name: Orange, price: 200}, {name: Kiwi, price: 500}, {name: Watermelon, price: 880}]

결과를 보면 오름차순으로 정렬된 것을 볼 수 있다.

클래스 내부에 Comparable 이 구현되었기 때문에 sort() 는 이 객체를 다른 객체와 비교할 수 있었다. 그리고 Comparable 은 오름차순으로 비교하도록 구현하였기 때문에 Fruit 객체들이 오름차순으로 정렬되었다.