Skip to content

java basic

Jump to bottom
baksakcci edited this page Aug 30, 2023 · 1 revision

정렬하는 법

java에서는 다양한 정렬 방법을 제시한다.

  • 직접 구현
  • Arrays.sort()
  • Collections.sort()
  • Comparator 구현

직접 구현

직접 정렬 알고리즘을 구현한다. 이는 다른 파트에서 설명하기 때문에 생략한다.

Arrays.sort()

[JAVA]Arrays.sort()의 내부 동작(1) - 자바니또 참조

primitive type의 배열일 때와 object type의 배열일 때 각각 내부 동작이 다르다.

  • primitive: DualPivotQuicksort
  • collection(object): TimSort

primitive

대표적인 배열인 int[]의 경우 내부에서 DualPivotQuicksort.sort()를 호출한다.

public static void sort(int[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

즉, pivot을 2개 사용하는 quick sort를 사용하는 것을 확인할 수 있다.

quick sort는 평소엔 O(nlogn)을 보장하지만, 정렬이 거의 다 된 상태라면 최악의 경우로써 O(n^2)이 될 수 있다. pivot을 2개 사용하면 quick sort보다 O(nlogn)을 더욱 보장할 수 있다. (하지만 이 경우도 완전히 보장하진 않는다.)

collection

collection의 경우 각 내부에서 sort() 함수를 자체적으로 지원하는 경우가 많다. 이는 대부분 Arrays util 라이브러리를 사용한다.

제일 많이 사용하는 List의 경우 각 sort() 함수 내부에 Arrays.sort()를 호출하는 것을 확인할 수 있다.

@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
  final int expectedModCount = modCount;
  Arrays.sort((E[]) elementData, 0, size, c);
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
  modCount++;
}

Arrays.sort() 내부는 tim sort로 구현되있는 것을 알 수 있다. TimSort는 binary search(이진삽입정렬) + merge sort로 이루어져있고, 정렬이 거의 다 된 상태라면 O(n)을 정렬이 안 된 상태라도 O(nlogn)의 시간복잡도를 보장한다.

public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                Comparator<? super T> c) {
  if (c == null) {
    sort(a, fromIndex, toIndex);
  } else {
    rangeCheck(a.length, fromIndex, toIndex);
    if (LegacyMergeSort.userRequested)
      legacyMergeSort(a, fromIndex, toIndex, c);
    else
      TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
  }
}

Collections.sort()

또다른 java util 라이브러리인 Collections에서 지원하는 정렬이다. 이름 그대로 Collection들의 sort를 지원한다.

당연하게도 Collection 중에 순서가 있는 저장 공간인 List 인터페이스를 상속한 자료구조만 가능하다. 대표적으로 LinkedList, Stack, Vector, ArrayList 등이 있다.

Collections.sort() 내부는 마찬가지로 Arrays.sort()를 호출하는 것을 확인할 수 있다.

public static <T extends Comparable<? super T>> void sort(List<T> list) {
  list.sort(null);
}

매개변수로 Comparator를 넣었을 때 내부 코드이다.

default void sort(Comparator<? super E> c) {
  Object[] a = this.toArray();
  Arrays.sort(a, (Comparator) c);
  ListIterator<E> i = this.listIterator();
  for (Object e : a) {
    i.next();
    i.set((E) e);
  }
}

결국 위 Arrays.sort()와 같은 원리로 동작하게 된다.

정렬 방식 커스텀

정렬 방식을 맘대로 구성할 수 있는 방법이 존재한다.

  • Comparator 구현체
  • Comparable 구현

Comparator 구현

primitive type, collection 둘 다 사용 가능하다.

primitive type이 아닌 Object type으로 직접 만들어서 Collection을 사용하여 자료구조를 만드는 경우가 많다.

  • 좌표 객체 생성
  • 사람의 신체
  • ...

이러한 경우에 이 Comparator를 구현하면 입맛에 맞게 커스텀할 수 있다.

❗Collection 정렬일 경우 무조건 구현해야 한다!

직접 Comparator객체를 생성하여 매개변수로 전달해야 하는데 필수적으로 compart() 함수를 다음과 같이 override해야한다.

persons.sort(new Comparator<Person>() {
  @Override
  public int compare(Person o1, Person o2) {
    return o2.height - o1.height;
  }
});

이 때 compare 함수의 return으로 사용되는 값은 o2를 기준으로 비교한다. return의 값이 양수냐 음수냐에 따라 오름차순, 내림차순이 결정된다.

  • 오름차순: 첫번째 인자가 두번째 인자보다 작다면 음수, 같다면 0, 크다면 양수를 리턴하도록 구현
  • 내림차순: 위와 반대로 구현

본 예제는 내림차순으로 구현한 예이다.

lambda 함수를 사용하여 코드를 간단하게 만들 수 있다.

persons.sort((o1, o2) -> o2.height - o1.height);
Clone this wiki locally