알고리즘 - 정렬 (1)

정렬

• 특정 값을 기준으로 데이터를 순서대로 배치하는 방법
• 구현 난이도는 쉽지만, 속도는 느린 알고리즘
  • 버블 정렬, 삽입 정렬, 선택 정렬
• 구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘
  • 합병정렬, 힙 정렬, 퀵 정렬, 트리 정렬
• 하이브리드 정렬
  • 팀 정렬, 블록 병합 정렬, 인트로 정렬
• 기타 정렬 알고리즘
  • 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬

 

 

버블 정렬(Bubble Sort)

• 인접한 데이터를 비교하며 자리 바꾸는 방식
• 알고리즘 복잡도: O(n^2)

 

 

버블 정렬 과정

 

step1 에서 맨 앞부터 두 인접한 수를 비교하여 작은 값이 뒤에 있으면 서로 위치를 바꿔줌

가장 큰 수 7이 맨 뒤에 위치하게 되면서 step1 종료됨

(비교 4회 진행)

 

step2 에서는 가장 큰 수가 7인 채, 다시 수를 비교하게 되므로 마지막 수(7) 앞까지만 비교하면 됨

(비교 3회 진행)

 

 

step3 에서도 6과 7은 정렬이 되었으므로 6 앞자리 까지만 비교하면 됨

(비교 2회 진행)

 

step4 까지 인접한 두 수의 비교를 끝내면 오름차순 정렬이 완성됨

(비교 1회 진행)

 

5개의 수를 버블 정렬 진행 시, 총 10번의 진행을 하게 됨

4 + 3 + 2 + 1 = 10 

 -> 5 ( 5 - 1 ) / 2 = 10

 

n ( n - 1 ) / 2 를 풀어보면 => n^2 - n / 2

알고리즘 복잡도는 최악의 케이스를 나타내므로 가장 큰 n^2를 표기함

=> O(n^2) : (n-1) + (n-2) + ... + 2 + 1

 

 

 

버블 정렬 구현

 

자바 코드

// 버블 정렬
public static void bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    for (int i = arr.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

// Test code
int[] arr = {3, 5, 2, 7, 1, 4};
bubbleSort(arr);
System.out.println("버블 정렬: " + Arrays.toString(arr));

 

 

삽입 정렬(Insertion Srot)

• 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식
• 알고리즘 복잡도: O(n^2)

 

 

삽입 정렬 과정

 

step1 은 3을 앞 데이터 5와 비교했을 때 값이 더 작기 때문에 5 앞으로 삽입

 

step2 는 7을 앞의 수 5와 비교했을 때 앞의 수보다 큰 값이므로 5 앞의 3과의 비교를 stop

 

step3 은 1이 앞의 수 7과 비교했을 때 값이 작기 때문에 7과 1의 자리 바뀜

          -> 그 앞의 5와 비교했을 때 5보다도 작은 값이므로 5와 1의 자리 바뀜

          -> 맨 앞의 수 3과 비교하였을 때 1이 더 작은 값이므로 3과 1의 자리 바뀜

 

step4 는 마지막 값 6이 앞의 7보다 값이 작기 때문에 7과 6의 자리가 바뀜, 6은 앞의 수 5보다는 값이 크므로 비교를 stop

 

버블 정렬과 마찬가지로 worst case의 경우를 기준으로 보기 때문에 O(n^2) 의 복잡도를 가지게 됨

하지만 버를 정렬과 달리 모두 비교하는 것이 아니라 다음 비교로 넘어가는 케이스가 있으므로 비교적 빠른 편

 

 

삽입 정렬 구현

 

자바 코드

// 삽입 정렬
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            } else {
                break;
            }
        }
    }

}

arr = new int[]{3, 5, 2, 7, 1, 4};
insertionSort(arr);
System.out.println("삽입 정렬: " + Arrays.toString(arr));

 

 

선택 정렬(Selection Sort)

• 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식
• 알고리즘 복잡도: O(n^2)

 

 

선택 정렬 과정

 

step1 는 최소값을 찾아 가장 앞의 값과 자리를 교환 => 최소값 1과 가장 앞자리의 5와 교환

 

step2 는 정렬된 가장 첫 번째 값을 제외한 데이터에서 최소값을 찾아 자리 교환 => 자리교환 없음

 

step3 은 이전까지 정렬된 값을 제외한 데이터들 중에서 최소값을 찾아 자리 교환 => 5와 7 자리 교환

 

step4 도 앞의 방식으로 진행

 

 

 

선택 정렬 구현

 

자바 코드

// 선택 정렬
private static void selectionSort(int[] arr) {
    // 최솟값을 찾아서 정렬하는 방식
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }

    //최댓값을 찾아서 정렬하는 방식
    for (int i = arr.length - 1; i > 0; i--) {
        int max = i;
        for (int j = i - 1; j >= 0; j--) {
            if (arr[j] > arr[max]) {
                max = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[max];
        arr[max] = tmp;
    }
}

arr = new int[]{3, 5, 2, 7, 1, 4};
selectionSort(arr);
System.out.println("선택 정렬: " + Arrays.toString(arr));