자바에서 정렬에 대해

유명한 정렬 알고리즘

 

시간복잡도 N^2 알고리즘

Bubble Sort (버블 정렬)

• 버블 정렬은 배열의 인접한 요소를 비교하고, 필요한 경우 위치를 바꾸는 방식으로 정렬을 수행합니다.
• 이 과정은 배열의 모든 요소가 올바르게 정렬될 때까지 반복됩니다.

 

Selection Sort (선택 정렬)

• 선택 정렬은 배열을 반복적으로 탐색하여 가장 작은(또는 가장 큰) 요소를 찾아, 정렬되지 않은 부분의 첫 번째 위치와 교환하는 방식으로 작동합니다.
• 이 과정은 배열의 모든 요소가 정렬될 때까지 반복됩니다.
• 선택 정렬은 버블 정렬보다 일반적으로 더 효율적이지만,
• 큰 데이터 세트에 대해서는 여전히 비효율적입니다.

 

Insertion Sort (삽입 정렬) 

출처 : 위키피디

• 삽입 정렬은 배열의 각 요소를 이미 정렬된 부분에 적절한 위치에 삽입하는 방식으로 정렬을 수행합니다.
• 새로운 요소를 정렬된 배열 부분에 삽입하기 위해, 이미 정렬된 부분의 적절한 위치가 나타날 때까지 요소들을 오른쪽으로 이동시킵니다.
• 삽입 정렬은 일반적으로 작은 데이터 세트에 효율적이며, 거의 정렬된 데이터에 대해 빠르게 작동합니다.

 

시간복잡도 NlogN 알고리즘

Quick Sort (퀵 정렬)

• 퀵 정렬은 분할 정복 알고리즘의 한 예로, 배열을 두 부분으로 나누고 각 부분을 재귀적으로 정렬합니다.
• 기준점(pivot)을 선택하고, 이 기준점보다 작은 요소들은 기준점의 왼쪽으로, 큰 요소들은 오른쪽으로 이동시킵니다.
• 이 과정을 반복하여 전체 배열을 정렬합니다.
• 퀵 정렬은 평균적으로 매우 빠른 성능을 보이지만, 최악의 경우 시간 복잡도는 O(n^2)이 될 수 있습니다.

 

Merge Sort (병합 정렬)

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

• 병합 정렬도 분할 정복 방법을 사용합니다.
• 배열을 더 이상 나눌 수 없을 때까지 두 부분으로 분할한 후, 분할된 각 부분을 재귀적으로 정렬하고,
• 다시 병합하면서 전체 배열을 정렬합니다.
• 병합 과정에서 두 부분 배열의 요소들을 순서대로 비교하며 새 배열에 삽입합니다.
• 병합 정렬은 모든 경우에 O(nlogn)의 시간 복잡도를 가지며, 대규모 데이터에도 효율적입니다.

 

Heap Sort (힙 정렬)

• 힙 정렬은 완전 이진 트리 구조인 힙을 사용하여 배열을 정렬합니다.
• 먼저 모든 요소를 힙에 삽입하여 최대 힙(또는 최소 힙)을 구성합니다.
• 그런 다음 힙의 루트(가장 큰 또는 가장 작은 값)를 배열의 마지막 요소와 교환하고, 힙의 크기를 줄입니다.
• 이 과정을 반복하여 전체 배열을 정렬합니다.
• 힙 정렬은 평균 및 최악의 경우 모두 O(nlogn)의 시간 복잡도를 가집니다.

 

자바의 Sort 메소드

자바에는 Arrays.sort가 존재합니다. 이 메소드를 사용하면 편하게 배열을 정렬할 수 있습니다.

int[] numbers = {6,5,4,2,3,1};
Arrays.sort(numbers); // 오름차순 정렬

String[] names = {"Park", "Lee", "Song"};
Arrays.sort(names); // 사전순 정렬

• boolean[], byte[], short[], int[], long[], float[], double[], char[] 모두 값이 작은 순서대로 오름차순 정렬 입니다.

 

신기한건 int[]을 정렬한 sort와 String[]을 정렬한 sort가 다른 정렬 알고리즘을 사용한다는 것 입니다.

• int[]

 

• String[]

int 배열은 DualPivotQuickSort를 사용했고 String 배열은 ComparableTimSort를 사용했습니다!!

 

DualPivotQuickSort	TimSort
boolean[], byte[], short[], int[], long[], float[], double[], char[] primitive type 배열의 정렬	Integer[], Double[] 과 같은 Wrapper Class, String[], 직접 정의한 CustomClass[] 와 같은 Object type 배열의 정렬

찾아보니 위의 표처럼 primitive type은 QuickSort를 Object type은 TimSort를 사용합니다.

 

Dual-Pivot Quick Sort와 Tim Sort의 차이점

둘의 차이점은 stable 하냐 안하냐 입니다.

Dual-Pivot Quick Sort은 stable 하지 않습니다. 즉, 들어 온대로 정렬이 되지 않습니다. 

예를 들어 5 1 5 2 3 이라면 1 2 3 5 5 로 정렬이 되지만 첫번째 5가 나중에 들어온 5 일 수 있습니다.

반대로 Tim Sort는 stable이 보장 됩니다.

	Dual-Pivot Quick Sort	Tim Sort
평균 시간 복잡도	O(NlogN)	O(NlogN)
최악 시간 복잡도	O(N^2)	O(NlogN)
stable 보장 유무	X	O

그러므로 문제에 따라 다르지만 왠만하면 Object를 사용해 배열을 만들고 정렬하는 식이 더 빠르게 정렬을 할 수 있습니다.

 

하나 더 궁금한점 그럼 Collections.sort는 어떤 것을 쓸까??

들어가서 찾아보니 TimSort를 사용하는 것을 알 수 있습니다. ArrayList<Integer> 이렇게 Object로 선언을 하니 당연한 결과 입니다. 이렇게 보면 배열을 만들어 정렬을 하는 것보니 ArrayList를 만들어 정렬하는게 더 편할 것 같습니다. 

 

Comparable을 사용하여 정렬

public static class Student implements Comparable<Student> {
    String name; int age; 
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public int compareTo(Student s) {
        if(this.age == s.age) return name.compareTo(s.name);
        return s.age - this.age;
    }
}

이렇게 implements를 사용하여 Comparable을 받아와 compareTo를 오버라이딩하여 정렬을 할 수 있습니다.

위의 예시는 학생들을 나이가 같을 경우 이름 가나다 순, 나이는 내림차순으로 정렬한 것 입니다.

 

Collections.sort(students, (s1, s2) -> {
    if(s1.age == s2.age) return s1.compareTo(s2);
    return  s2.age - s1.age;
});

이렇게 student 클래스를 그냥 받아와 람다식으로 정렬을 할 수도 있습니다!!