[Java] 코딩 테스트 주요 알고리즘 (1) - 버블, 선택, 삽입, 셀, 병합, 퀵 정렬

복잡도

1. 시간 복잡도

• 알고리즘이 실행되는 데 걸리는 시간의 상한을 입력 크기(n)에 따라 표현한 것
• 빅오 표기법(O)으로 나타냄
  • O(1) : 입력 크기와 무관하게 일정한 시간이 걸림 (상수 시간)
  • O(log n) : 입력 크기가 증가해도 수행 시간이 천천히 증가 (로그 시간)
  • O(n) : 입력 크기에 비례해 수행 시간이 증가 (선형 시간)
  • O(n^2) : 이중 반복문 등에서 나타나는 시간 (제곱 시간)
  • O(2^n) : 재귀 호출 등이 많은 경우 발생 (지수 시간)

2. 공간 복잡도

• 알고리즘이 실행될 때 사용되는 메모리 공간의 양을 입력 크기(n)에 따라 표현한 것
  • 고정 공간 : 알고리즘에서 사용하는 상수 크기의 메모리
  • 가변 공간 : 입력 크기에 따라 달라지는 메모리

 

---

정렬 알고리즘

원소들을 일정한 순서대로 나열하는 알고리즘으로, 주어진 상황과 기준에 따라 알고리즘을 선정해서 사용한다.

알고리즘	평균 시간복잡도	최악 시간복잡도	공간복잡도	특징
버블 정렬	O(n^2)	O(n^2)	O(1)	단순, 매우 비효율적
선택 정렬	O(n^2)	O(n^2)	O(1)	단순, 비효율적
삽입 정렬	O(n^2)	O(n^2)	O(1)	거의 정렬된 데이터에 적합
셀 정렬	O(n log n)	O(n^1.5)	O(n^2)	삽입 정렬 개선, 대량 데이터에서 비효율적
병합 정렬	O(n log n)	O(n log n)	O(n)	안정 정렬, 대량 데이터 정렬에 적합
퀵 정렬	O(n log n)	O(n^2)	O(log n)	평균적으로 빠름, 불안정 정렬
힙 정렬	O(n log n)	O(n log n)	O(1)	최악의 경우에도 효율적
계수 정렬	O(n + k)	O(N + k)	O(n + k)	특정 범위의 정수 정렬에 적합
기수 정렬	O(n * d)	O(n * d)	O(n + k)	범위가 큰 정수나 문자열에 적합

• 정렬에서는 원소의 순서를 많이 바꾸기 때문에 swap() 함수를 구현하는 경우가 많음

public static void swap(int[] arr, int idx1, int idx2) {
	int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

 

 

1. 버블 정렬 (Bubble Sort)

• 인접한 두 요소를 비교하며 정렬
• 시간복잡도 : 이미 정렬된 경우 O(n), 평균/최악 O(n^2)

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

2. 선택 정렬 (Selection Sort)

• 가장 작은 값을 찾아 정렬된 부분에 추가하는 방법
• 맨 앞 인덱스부터 차례대로 그 자리에 들어갈 원소를 선택하여 정렬하는 알고리즘
• 시간복잡도 : 평균/최악 O(n^2) 교환 횟수가 O(n)으로 적어 버블 정렬보다는 성능이 좋음
  • 인덱스 0부터 시작하여 가장 작은 값을 찾아 해당 인덱스와 swap, 마지막 인덱스까지 반복

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

3. 삽입 정렬 (Insertion Sort)

• 새로운 요소를 이미 정렬된 부분에 삽입하는 방법
• 인덱스 1의 원소부터 앞 방향으로 들어갈 위치를 찾아 교환하는 정렬 알고리즘
• 시간복잡도 : 거의 정렬된 경우 O(n), 평균/최악 O(n^2) 정렬되어 있을 수록 성능이 좋음
  • 인덱스 1번부터의 원소들을 순차적으로 자신이 들어갈 위치에 넣기

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

4. 셀 정렬 (Shell Sort)

• 삽입 정렬의 단점(n-1번째 인덱스가 가장 작은 원소라면 많은 swap이 필요)은 보완한 알고리즘
• 배열을 일정 간격에 따라 부분 배열로 나누어 정렬하고, 다시 간격을 줄여 정렬하는 것을 반복
  • 초기 단계에서 데이터를 일부 정렬된 상태로 만들어 삽입 정렬의 성능을 향상시키는 것
• 간격은 총 데이터를 2로 나눈 값에서 시작해 간격을 2로 나누다 최종적으로 1이 되도록 조정함
• 시간복잡도 : 간격 감소 방식에 따라 최선에서 O(n log n), 평균 O(n^1.5), 최악 O(n^2)

import java.util.Arrays;

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;

        // 초기 간격은 배열 길이의 절반
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 간격별 삽입 정렬 수행
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;

                // 간격(gap) 단위로 비교하여 정렬
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 8, 3, 7, 5, 6, 4, 1};
        shellSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Knuth의 간격 수열 사용 방식

• Knuth 간격 수열은 gap = gap * 3 + 1 방식으로 계산되며, 간격 감소 방식이 더 세밀함

import java.util.Arrays;

public class ShellSortKnuth {
    public static void shellSort(int[] arr) {
        int n = arr.length;

        // Knuth 간격 수열 생성
        int gap = 1;
        while (gap < n / 3) {
            gap = gap * 3 + 1;
        }

        // 간격(gap) 감소하며 정렬
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;

                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap /= 3; // Knuth 수열 감소
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 8, 3, 7, 5, 6, 4, 1};
        shellSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

 

5. 병합 정렬 (Merge Sort)

• 배열을 재귀적으로 나누고 병합하면서 정렬하는 분할 정복 알고리즘
  • 배열의 길이가 1이 될 때까지 2개의 부분 배열로 분할 → 분할 완료 시 다시 2개의 부분 배열을 합병하고 정렬
    → 모든 부분 배열이 합병될 때까지 반복
• 시간 복잡도 : 항상 O(n log n)으로 빠르지만, 제자리 정렬보다 O(n)만큼의 추가적인 메모리를 사용
  • 우측 부분배열이 다 들어가고 좌측 부분배열만 남은 경우 : 좌측 부분 배열만 넣으면 됨
  • 좌측 부분배열이 다 들어가고 우측 부분배열만 남은 경우 : 이미 배열이 다 정렬된 것
• System.arraycopy() : for문을 사용하여 배열을 수동으로 복사하는 것보다 더 빠름
  • 네이티브 코드 : OS와 하드웨어에서 직접 실행되는 바이너리 코드로, Java의 JNI(Java Native Inferface; 네이티브 코드와 Java 코드 간 인터페이스 역할)를 통해 실행됨. Java는 JVM 위에서 실행되어 대부분의 기능이 플랫폼 독립적이지만 arraycopy()와 같은 일부 함수는 플랫폼에 최적화된 네이티브 코드로 구성되어 있어 성능이 중요한 작업에서 사용하기 좋음
  • System.arraycopy(원본 배열, 원본 시작 인덱스, 대상 배열, 대상 시작 인덱스, 인덱스 개수)

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) { // 재귀(분할)
        if (left < right) { // 시작과 끝 인덱스
            int mid = (left + right) / 2; // 배열을 반으로 분할하기 위해 중간 인덱스 구하기

            mergeSort(arr, left, mid); // 왼쪽 끝 ~ 중간 배열
            mergeSort(arr, mid + 1, right); // 중간 ~ 오른쪽 끝 배열
            merge(arr, left, mid, right); // 분할-정렬 결과를 다시 병합
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) { // 합병
    	// 두 부분 배열의 인덱스를 비교하며 정렬
        int[] temp = new int[right - left + 1]; // 임시 배열
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2};
        mergeSort(arr, 0, arr.length - 1); // 정렬할 배열, 시작과 끝 인덱스를 넘겨줌
        System.out.println(Arrays.toString(arr)); // 배열 출력. Arrays.toString 미사용시 배열 객체의 메모리 주소를 해시코드 형태로 출력함
    }
}

 

6. 퀵 정렬 (Quick Sort)

• 피벗(pivot)을 기준으로 배열을 분할하며 정렬하는 분할 정복 알고리즘
  • 병합 정렬은 일정한 부분 리스트로 분할하지만, 퀵 정렬은 피벗이 들어가는 위치에 따라 불균형하게 분할됨
  • 피벗보다 작은 요소는 왼쪽, 피벗보다 큰 요소는 오른쪽 / 재귀적으로 왼쪽, 오른쪽 부분 배열에 대해 퀵 정렬 수행
• 합병 정렬과 속도가 비슷하고 힙 정렬보다 빠르지만 최악의 경우(피벗을 최솟값이나 최댓값으로 선택하여 부분 배열이 한쪽으로 쏠리는 경우) O(n^2)만큼 걸리고, 재귀로 구현하여 메모리를 많이 사용할 수 있다는 단점이 존재한다.
• 시간 복잡도 : 최선/평균 O(n log n), 최악 O(n^2)

import java.util.Arrays;

public class QuickSort {

    // 퀵 정렬 메서드
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 분할 기준 인덱스 찾기
            int pivotIndex = partition(arr, low, high);

            // 왼쪽 부분 배열 정렬
            quickSort(arr, low, pivotIndex - 1);

            // 오른쪽 부분 배열 정렬
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 분할 메서드 (Lomuto 분할 방식)
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 피벗: 마지막 요소 선택
        int i = low - 1; // 작은 요소의 끝 위치

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) { // 피벗보다 작은 경우
                i++;
                swap(arr, i, j);
            }
        }

        // 피벗을 올바른 위치로 이동
        swap(arr, i + 1, high);

        return i + 1; // 피벗의 최종 위치 반환
    }

    // 배열의 두 요소를 교환하는 메서드
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 메인 메서드
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("Original array: " + Arrays.toString(arr));

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

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}