[Java] 정렬 알고리즘 정리

정렬

• 선형 자료구조는 순서가 중요하다.
• 정렬이란 순서를 바꾸는 것
  • 오름차순 정렬 ascending
  • 내림차순 정렬 descending
    
    
  • 알고리즘 별 성능표
    

    name	best	average	worst
    bubble	n	n^2	n^2
    insertion	n	n^2	n^2
    selection	n^2	n^2	n^2
    quick	nlogn	nlogn	n^2
    merge	nlogn	nlogn	nlogn

---

1) bubble sort 버블정렬

개념

• for문을 통해 가장 작은 값을 찾고, 맨 앞자리와 교환
• 다음 for문에선 맨 앞자리 값을 제외한 값 중 가장 작은 값을 찾고, 두번째 앞자리와 교환
• 이 작업을 최대 n - 1 번 반복하면 정렬 완료
• 시간복잡도 : O(n^2)

ex) 3 1 5 2 4 를 정렬한다고 가정

• 1번째 loop ⇒ 31524 / 13524 / 13524 / 13524 1확정
• 2번째 loop ⇒ 13524 / 13524 / 12534 2확정
• 3번째 loop ⇒ 12534 / 12354 3확정
• 4번째 loop ⇒ 12354 / 4확정
• 5번째 loop ⇒ 12345

    private static void bubbleSort(int[] array) {
         for(int i=0; i<array.length-1; i++){
            for(int j=0; j< array.length-1-i; j++){
                if(array[j] > array[j+1]) swap(array, j, j+1);
            }
        }
    }

---

 

2) Insertion sort 삽입정렬

개념

1. 가장 처음 값은 자리를 확정해둔다.
2. 왼쪽 자리들과 값을 비교해나간다.
3. (자신보다 작은 값이 나오기 전까지 자리를 바꿔나간다.)
4. 작은 값이 나왔을 경우 다음 분기로 넘어간다.

• 시간복잡도 : O(n^2)

ex) 3 1 5 2 4 를 정렬한다고 가정

• 3은 확정하고 시작
• 1번째 loop ⇒ 3 1 5 2 4 / 1 3 5 2 4
• 2번째 loop ⇒ 1 3 5 2 4
• 3번째 loop ⇒ 1 3 5 2 4 / 1 3 2 5 4 / 1 2 3 5 4
• 4번째 loop ⇒ 1 2 3 5 4 / 1 2 3 4 5

    private static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (array[j] < array[j+1]) break;
                else swap(array, j, j+1);
            }
        }
    }

---

3) Selection sort 선택정렬

개념

• 최소 값을 찾아 가장 왼쪽에 두는 방법
• 범위 내의 최소 값을 찾아 가장 왼쪽 값과 자리를 바꾼다
• 시간복잡도 : O(n^2)

ex) 3 1 5 2 4 를 정렬한다고 가정

• 1번째 loop ⇒ 3 1 5 2 4 → 1 3 5 2 4
• 2번째 loop ⇒ 1 3 5 2 4 → 1 2 5 3 4 / 가장 왼쪽인 3과 자리바꿈
• 3번째 loop ⇒ 1 2 5 3 4 → 1 2 3 5 4
• 4번째 loop ⇒ 1 2 3 5 4 → 1 2 3 4 5
• 5번째 loop ⇒ 1 2 3 4 5 → 1 2 3 4 5

    private static void selectionSort(int[] array) {
        for(int i=0; i< array.length-1; i++){
            int min = i;
            for(int j=i+1; j< array.length; j++){
                if(array[min] > array[j]) {
                    min = j;
                }
            }
            swap(array, i, min);
        }
    }

---

 

4) Quick sort 퀵 정렬

개념

• 큰거는 큰것끼리 작은거는 작은 것끼리 구분해서 처리한다
• Pivot을 설정하고 이보다 큰 값과 작은 값을 설정
• 시간복잡도 : O(nlogn) 회를 거듭할 수록 범위가 절반씩 줄어든다
• ex) 3 1 5 2 4 를 정렬한다고 가정
  • 숫자 하나를 pivot으로 설정 → 5
  • [3 1 2 4] [5] [] pivot을 기준으로 분리
  • [1] [2] [3 4] 양쪽 값에서 pivot을 설정하고 또 나눔
  • [][1][] 확정 / [3] [4] [ ] 숫자가 하나 뿐이라면 확정
  • [] [3] [] 확정 합치기 시작

---

4) Merge sort 병합정렬

개념

• 원소가 하나가 될때까지 나누고 병합한다.
• 하나씩 병합하며 정렬해나간다. 병합 시 작은 값을 먼저 삽입한다
• 시간복잡도 : O(nlogn)
• ex) 3 1 5 2 4 를 정렬한다고 가정
  • [3 1 5 2 4] → [3 1] [5 2 4] → [3] [1] [5] [2 4] → [3] [1] [5] [2] [4]
  • [1 3] [5] [2 4] → [1 3] [2 4 5] → [1 2 3 4 5]
  • 왼쪽부터 순서대로 값을 비교하며 삽입
    • 한쪽 값이 비었다면 반대쪽 값 모두 삽입