Arrays.sort() 및 Collections.sort()의 시간 복잡도는 무엇입니까

시간 복잡성을 아는 것은 모든 소프트웨어 엔지니어, 특히 최고의 기술 회사에서 일하고 싶은 사람들에게 중요합니다. 정렬 알고리즘의 시간 복잡성은 다른 많은 알고리즘의 기반이기 때문에 특히 중요합니다. 이 기사에서는 Arrays.sort 및 Collections.sort 의 시간 복잡도를 살펴보므로 저처럼 인터뷰하는 동안 놀라지 않을 것입니다.

후드 아래의 동일한 논리

Collections.sort는 List에서 작동하고 Arrays.sort는 배열에서 작동합니다. 소스를 검사하면 Collections.sort가 전달된 List를 배열로 변환하는 것으로 나타납니다. 변환 후 새로 할당된 배열에서 Arrays.sort가 호출됩니다.

{"title": "Collections.sort"}
default void sort(Comparator << ? super E > c) {
  // Convert list into array
  Object[] a = this.toArray();
  // Call Arrays.sort on newly allocated array
  Arrays.sort(a, (Comparator) c);
  ListIterator < E > i = this.listIterator();
  for (Object e: a) {
    i.next();
    i.set((E) e);
  }
}

시간 복잡도

Java 8Arrays.sort부터 두 가지 정렬 알고리즘을 사용합니다. 하나는 dual-pivot quicksort라는 이름의 Quicksort의 변형이고, 다른 하나는 Timsort라는 MergeSort의 변형입니다. 둘 다 시간 복잡도는 O(n log n)이며, 여기서 n는 배열의 총 항목 수입니다.

비교기로

비교기를 포함한 시간복잡도는 O(n * (log n) * c)이며, 여기서 c는 비교기의 시간복잡도이다. 기본적으로 Arrays.sort는 O(1) 시간 복잡도에 대해 콘텐츠의 natural ordering 다음에 비교기를 사용합니다. 계산 작업이 거의 없는 프로그래머 정의 비교기도 시간 복잡도O(1)로 해결됩니다.
O(f)의 시간 복잡도에 대해 파일을 검색해야 하는 비교기를 정의한다고 가정해 보겠습니다. 여기서 f는 파일 수입니다. 결과를 O(n * (log n) * (O(f) + O(f)) 또는 O(n * (log n) * O(f)) 로 정렬하기 위한 시간 복잡도는 각 비교에서 실행되는 O(f) 알고리즘을 설명합니다.

사용되는 알고리즘

매개변수 유형은 선택한 정렬 알고리즘을 결정합니다. 아래 Arrays.sort 의 메서드 서명을 기록해 두십시오.

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

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

public static void sort(float[] a) {
  DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
~~~{% endraw %}
{% raw %}


```java
{"title": "Timsort"}
public static void sort(T[] a, Comparator<? super T> c) {
  if (c == null) {
    sort(a);
  } else {
    if (LegacyMergeSort.userRequested)
      legacyMergeSort(a, c);
    else
      TimSort.sort(a, 0, a.length, c, null, 0, 0);
   }
}

Quicksort는 기본 데이터 유형을 허용하고 Timsort는 제네릭을 허용한다는 것을 배웁니다. Timsort는 안정적인 정렬 알고리즘이지만 Quicksort는 그렇지 않은 이유입니다. 안정적인 정렬 알고리즘은 동일한 값의 두 항목이 서로 옆에 있으면 정렬 후에도 동일한 순서를 유지함을 의미합니다.

기본 데이터 유형을 처리할 때 위치를 바꾸는 두 정수는 본질적으로 동일하고 차이점을 알 수 없기 때문에 중요하지 않습니다. 한편, 개체를 정렬할 때 동일한 개체가 불필요하게 위치를 바꾸면 유해한 효과가 발생할 수 있습니다. 말할 것도 없이 개체에는 교체가 이루어진 시기를 식별할 수 있는 고유한 속성이 포함될 수 있습니다.

결론

Arrays.sort는 배열에서 작동하고 Collections.sort는 List에서 작동합니다.

Collections.sort는 List를 배열로 변환한 다음 Arrays.sort를 호출합니다.

Arrays.sort에는 두 가지 정렬 알고리즘이 있습니다. 불안정한 알고리즘인 Quicksort와 안정적인 알고리즘인 Timsort가 있습니다. 둘 다 O(n log n)의 시간 복잡도를 공유합니다. 여기서 n는 배열의 총 항목 수입니다.

비교기를 포함하면 O(n * (log n) * c 가 됩니다. 여기서 c는 비교기의 시간 복잡도입니다.

Arrays.sort 전달된 매개변수의 유형에 따라 사용할 정렬 알고리즘을 결정합니다. 기본 데이터 유형에 대한 Quicksort 및 객체에 대한 Timsort.

안정적인 정렬 알고리즘은 동일한 값의 항목이 정렬 후에도 동일한 순서로 유지됨을 의미합니다.

이것이 도움이 되었으면 내 newsletter 또는 supporting me에 가입하는 것을 고려하십시오. 읽어 주셔서 감사합니다!

저자에 대해.

저는 Gregory Gaines , 블로깅, 컴퓨터 과학 공부, 리버스 엔지니어링을 좋아하는 소프트웨어 엔지니어입니다.