알고리즘 분류/정렬

[정렬]역정렬하기

728x90

이번 포스트에서는 요소를 역정렬 하는 방법에 대해서 살펴보자.

Comparator.reverseOrder()

객체형 배열의 역정렬

객체형 배열을 역정렬하기 위해서는 Comparator가 자기는 static 메서드인 reverseOrder를 사용하면 간단히 해결할 수 있다.

public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
    return Collections.reverseOrder();
}

다음은 주어진 Integer의 배열에 대한 역 정렬 활용 예이다.

Integer [] ints = {9,5,3,2,8,1,7,0};

Arrays.sort(ints, Comparator.reverseOrder() );
System.out.println(Arrays.toString(ints));        //[9, 8, 7, 5, 3, 2, 1, 0]

기본형의 역정렬

하지만 기본형에서는 Comparator를 사용할 수가 없기 때문에 당연히 위의 방법을 사용할 수 없다.

이런 경우 JavaStream API의 boxing을 통해 기본형을 객체형으로 변경한 후 무언가 처리할 수는 있지만 당연히 비용이 어마어마하다.

int [] pints = {9,5,3,2,8,1,7,0};
Arrays.stream(pints).boxed().sorted(Comparator.reverseOrder())
                            .mapToInt(Integer::intValue)
                            .toArray();
     
System.out.println(Arrays.toString(pints));    //[9, 5, 3, 2, 8, 1, 7, 0]

좀 더 쉽게 생각해보면 기본형 배열을 일단 정렬 후 다시 역순으로 swap 하는 방법이 훨씬 효과적이다.

Arrays.sort(pints);

for (int i = 0, j = pints.length - 1; i < j; i++, j--) {
    int temp = pints[i];
    pints[i] = pints[j];
    pints[j] = temp;
}

모든 정렬 결과를 역정렬하는 경우

만약 어떤 정렬된 결과가 있고 그것의 역 정렬 결과가 필요한 경우도 위의 기본형에 대한 역정렬을 이용하는 것이 효과적이다. 왜냐하면 아무리 빠른 정렬 알고리즘도 O(nlogn)의 시간 복잡도를 가지기 때문이다. 위와 같이 그냥 반복만을 통해서 위치만 바꾸면 O(n)에 작업을 완료될 것이다.

728x90