[Python, Java] 팀 정렬(Tim sort) : 내장 정렬 함수

정렬 별 시간 복잡도

정렬 알고리즘	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도
버블 정렬 (Bubble Sort)	O(n)	O(n^2)	O(n^2)
선택 정렬 (Selection Sort)	O(n^2)	O(n^2)	O(n^2)
삽입 정렬 (Insertion Sort)	O(n)	O(n^2)	O(n^2)
합병 정렬 (Merge Sort)	O(n log n)	O(n log n)	O(n log n)
퀵 정렬 (Quick Sort)	O(n log n)	O(n log n)	O(n^2)
힙 정렬 (Heap Sort)	O(n log n)	O(n log n)	O(n log n)
셸 정렬 (Shell Sort)	O(n log n)	O(n^(3/2))	O(n^2)
기수 정렬 (Radix Sort)	O(nk)	O(nk)	O(nk)
계수 정렬 (Counting Sort)	O(n + k)	O(n + k)	O(n + k)
버킷 정렬 (Bucket Sort)	O(n + k)	O(n + k)	O(n^2)

• 버블 정렬 (Bubble Sort): 최선의 경우는 이미 정렬된 경우로 한 번의 패스에서 아무 교환도 일어나지 않는다.
• 선택 정렬 (Selection Sort): 항상 𝑂(n^2)시간 복잡도를 가진다.
• 삽입 정렬 (Insertion Sort): 최선의 경우는 이미 정렬된 경우로 O(n)이다.
• 합병 정렬 (Merge Sort): 항상 O(nlogn) 시간 복잡도를 가진다.
• 퀵 정렬 (Quick Sort): 평균적으로 O(nlogn)이지만, 최악의 경우 O(n^2)이다.
• 힙 정렬 (Heap Sort): 항상 O(nlogn) 시간 복잡도를 가진다.
• 셸 정렬 (Shell Sort): 시간 복잡도는 간격 시퀀스에 따라 다르다. 평균적으로 O(n^3/2)로 추정된다.
• 기수 정렬 (Radix Sort): d는 자릿수, k는 기수이다. 주로 O(nk)로 표현된다.
• 계수 정렬 (Counting Sort): k는 값의 범위다. O(n+k) 시간 복잡도를 가진다.
• 버킷 정렬 (Bucket Sort): 평균적으로 O(n+k)이지만, 최악의 경우 O(n^2)이다.
  
  

팀 정렬

Timsort는 실제 데이터에서 매우 효율적이며, 특히 거의 정렬된 데이터에 대해 뛰어난 성능을 발휘한다. 또한, Timsort는 안정 정렬(Stable Sort)이므로 동일한 값의 요소들이 원래의 순서를 유지한다.

팀소트(Timsort)는 수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘의 하나이다. 합병 정렬과 삽입 정렬이 기원이다. 2002년 파이썬 프로그래밍에 사용하기 위해 팀 피터스가 구현했다. 팀소트는 버전 2.3부터 파이썬의 표준 정렬 알고리즘이다.

장점

• 효율성: 다양한 종류의 데이터에서 효율적으로 동작하며, 특히 거의 정렬된 데이터에서 성능이 뛰어남.
• 안정성: 같은 값이 있을 때 원래 순서가 유지.
• 일관된 성능: 최악의 경우에도 O(nlogn)의 시간 복잡도를 보장.

언어 별 사용 예제

Python

내장 정렬 함수인 sorted()와 list.sort()를 사용

# 정렬할 리스트
array = [5, 2, 9, 1, 5, 6]

# list.sort() 사용
array.sort()
print(array)  # [1, 2, 5, 5, 6, 9]

# 또는 sorted() 사용
sorted_array = sorted(array)
print(sorted_array)  # [1, 2, 5, 5, 6, 9]

Java

Java의 Arrays.sort() 및 Collections.sort()를 사용

Arrays.sort()

• Primitive Types
  Arrays.sort() 메서드는 기본 데이터 타입(예: int, char)에 대해 Dual-Pivot Quick Sort 알고리즘을 사용한다. 이는 평균적으로 O(nlogn)의 시간 복잡도를 가지며, 최악의 경우 O(n^2)이지만, 일반적으로 매우 효율적이다.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));  // [1, 2, 5, 5, 6, 9]
    }
}

• Object Types: 객체 배열에 대해 Arrays.sort()는 Timsort 알고리즘을 사용하며, 최악의 경우 시간 복잡도는 O(nlogn)입니다. Timsort는 객체 배열을 정렬할 때 안정 정렬을 제공합니다.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Integer[] array = {5, 2, 9, 1, 5, 6};
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));  // [1, 2, 5, 5, 6, 9]
    }
}

Collections.sort()

• Collections.sort()는 내부적으로 List를 배열로 변환한 다음 Arrays.sort()를 호출하여 정렬합니다. 따라서 객체 타입에 대해서는 Timsort를 사용하여 O(nlogn)의 시간 복잡도를 가집니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, 5, 2, 9, 1, 5, 6);
        Collections.sort(list);
        System.out.println(list);  // [1, 2, 5, 5, 6, 9]
    }
}