[알고리즘] 정렬 알고리즘

정렬 알고리즘에 대해 알아보자 (feat. 선택정렬, 삽입정렬, 버블정렬, 합병정렬, 퀵정렬, 힙정렬)

정렬 정리

시간복잡도

안정정렬

• 중복된 값이 존재할때 입력순서를 반영하여 동일하게 정렬함
• 삽입정렬, 버블정렬, 병합정렬

불안정정렬

• 중복된 값이 존재할때 입력순서와 동일하지 않게 정렬됨
• 선택정렬, 퀵정렬, 힙정렬

선택정렬 (Selection sort)

• 변경할 인덱스를 고정하고, 뒷부분에서 최소값을 찾아 교체하는 방식
  1. i=1 부터 최소값을 찾고 i=0 값과 바꿈
  2. i=2 부터 최소값을 찾고 i=1 값과 바꿈
  3. 반복
• 장점
  • 제자리정렬이라 추가 메모리 사용 X
  • 비교는 많고 교환은 적음
• 단점
  • 불안정 정렬임
  • 모든 상황에서 시간 복잡도가 O(N^2)

public static int[] selectionSort(int[] arr){

    int len = arr.length;

    for(int i=0; i<len; i++){
        int min = i;
        for(int j=i+1; j<len; j++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
    
    return arr;
}

삽입정렬 (Insertion sort)

• 앞쪽의 정렬된 배열 부분과 그 뒤 원소를 비교해서 앞 배열에 삽입하는 방식
  1. i=0~0 배열과 i=1을 비교하여 i=1이 작다면 앞 배열에 삽입
  2. i=0~1 배열과 i=2를 비교하여 i=2가 작다면 앞 배열에 삽입
  3. 반복
• 장점
  • 제자리정렬이라 추가 메모리 사용 X
  • 안정 정렬임
  • 이미 정렬되어있는 경우 시간복잡도 O(N)
• 단점
  • 삽입시 배열을 시프트하기 때문에 변경이 많음

public static int[] insertionSort(int[] arr){

    int len = arr.length;

    for(int i=1; i<len; i++){
        int key = arr[i];
        int j = i- 1;
        
        while(j >= 0 && key<arr[j]){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
    
    return arr;
}

버블정렬 (Bubble sort)

• 인접한 두 원소를 비교하여 큰 원소를 뒤로 보내는 방식
  1. i=0과 i=1 원소를 비교 -> i=0>i=1 이라면 서로 교체, 아니면 멈춤
  2. 반복
• 장점
  • 제자리정렬이라 추가 메모리 사용 X
  • 안정 정렬임
• 단점
  • 비교 + 교환이 매우 많이 일어남
  • 모든 상황에서 시간 복잡도가 O(N^2)

public static int[] bubbleSort(int[] arr){

    int len = arr.length;

    for(int i=0; i<len; i++){
        for(int j=0; j<len-i-1; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    
    return arr;
}

합병 정렬 (Merge sort)

• 분할-정복 알고리즘 사용
  • 재귀호출을 통해 구현함
  • 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다
    • 이 때 두 배열을 비교하여 정렬하는 작업이 일어난다.
• 장점
  • 안정 정렬임
  • 데이터 분포에 영향을 받지 않음
• 단점
  • 분할된 배열을 합치며 정렬해야 할때 추가 메모리가 필요
    • 단 연결리스트 사용시 제자리 정렬로 구현가능

public static int[] mergeSort(int[] arr){
    
    reculsive(arr, 0, arr.length - 1);

    return arr;
}

public static void reculsive(int[] arr, int left, int right){

    if(left < right){
        int mid = (left + right)/2;

        // 분할
        reculsive(arr, left, mid);
        reculsive(arr, mid+1, right);

        // 정복 - 합치면서 정렬
        int[] sorted = new int[right-left+1];
        int index = 0;
        int L = left;
        int R = mid+1;
        while(L <= mid && R <= right){
            if(arr[L] < arr[R]){
                sorted[index] = arr[L];
                L++;
            }
            else{
                sorted[index] = arr[R];
                R++;
            }
            index++;
        }

        // 남아있다면 추가해줌
        for(int i=L; i<mid+1; i++){
            sorted[index] = arr[i];
            index++;
        }
        for(int i=R; i<=right; i++){
            sorted[index] = arr[i];
            index++;
        }

        // 정렬된것 원본에 반영
        for(int i=0; i<sorted.length; i++){
            arr[i+left] = sorted[i];
        }
    }
}

퀵 정렬 (Quick sort)

• 분할-정복 알고리즘 사용
  1. i=0의 원소를 pivot으로 설정
  2. i=1을 left 포인터, i=len-1을 right 포인터로 설정
  3. left 포인터 원소가 pivot보다 작을땐 건너 뛰고, right 포인터가 pivot보다 클땐 건너뜀
  4. left 포인터 원소가 pivot보다 크다면 잠시 멈추고 right 포인터가 pivot보다 작을때 서로 원소를 바꾼다
  5. left > right가 되면 i=0의 원소를 left 위치와 바꿈
• 장점
  • 제자리정렬이라 추가 메모리 사용 X
• 단점
  • 불안정 정렬임
  • pivot이 랜덤하게 선정되기에 데이터 분포에 영향받음

public static int[] quickSort(int[] arr){

    reculsive(arr, 0, arr.length-1);

    return arr;
}

public static void reculsive(int[] arr, int left, int right){
    
    if(left < right){
        // 피봇정하고 피봇 기준으로 정렬
        int pivot = left;
        int pivotNum = arr[pivot];
        int L = left;
        int R = right;

        while(L < R){
            while(arr[L] < pivotNum){
                L++;
            }
            while(arr[R] > pivotNum){
                R--;
            }
            if(L < R){
                int temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
        }
        
        // 분할하여 반복
        reculsive(arr, left, R-1);
        reculsive(arr, R+1, right);
    }
}

힙 정렬 (Heap sort)

• 불안정 + 제자리정렬

public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

public static void heapify(int arr[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    
    if (l < n && arr[p] < arr[l]) {
        p = l;
    }
    
    if (r < n && arr[p] < arr[r]) {
        p = r;
    }
    
    if (i != p) {
        swap(arr, p, i);
        heapify(arr, n, p);
    }
}
    
public static int[] heapSort(int[] arr) {
    int n = arr.length;
    
    // 최대힙 만들기
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 최대힙으로 배열 정렬하기
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }

    return arr;
}