[Algorithm] 기본 정렬 알고리즘

선택 정렬(Selection Sort)

Logic

1. 주어진 배열의 요소 중 최소값을 찾는다.

2. 그 요소를 맨 앞에 위치한 요소와 교체한다.

3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

Algorithm

public void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int idxMin = i;
        for (int j = i + 1; j < nums.length; j++)
            idxMin = nums[j] < nums[i] ? j : i;
        int tmp = nums[i];
        nums[i] = nums[idxMin];
        nums[idxMin] = tmp;
    }
}

Complexixy Analysis

• Time Complexity

중첩된 for반복문 중 배열 nums의 길이(n)에 따른 내부 for반복문의 실행 횟수는 항상 (n - 1) + (n - 2) + … + 1 = n(n - 1) / 2이다. 따라서 모든 경우에 O(n²)의 시간 복잡도를 가진다.

• Space Complexity

배열 nums의 길이(n)에 따라 증가하거나 감소되어 할당받는 메모리 공간이 없으므로 모든 경우에 O(1)의 공간 복잡도를 가진다.

버블 정렬(Bubble Sort)

Logic

1. 배열의 첫 번째 요소가 두 번째 요소보다 클 경우 두 요소의 위치를 바꾼다.

2. 두 번째 요소와 세 번째 요소와 그 뒤에 위치한 요소 또한 동일한 과정을 거쳐 배열의 끝까지 비교를 진행한다.

3. 마지막 요소는 정렬이 된 상태이므로 남은 나머지 배열에 동일한 과정을 진행한다.

Algorithm

public void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++)
        for (int j = 1; j < nums.length - i; j++)
            if (nums[j] < nums[j - 1]) {
                int tmp = nums[j - 1];
                nums[j - 1] = nums[j];
                nums[j] = tmp;
            }
}

Complexixy Analysis

• Time Complexity

중첩된 for반복문 중 배열 nums의 길이(n)에 따른 내부 for반복문의 실행 횟수는 항상 (n - 1) + (n - 2) + … + 1 = n(n - 1) / 2이다. 따라서 모든 경우에 O(n²)의 시간 복잡도를 가진다.

• Space Complexity

배열 nums의 길이(n)에 따라 증가하거나 감소되어 할당받는 메모리 공간이 없으므로 모든 경우에 O(1)의 공간 복잡도를 가진다.

삽입 정렬(Insertion Sort)

Logic

1. 배열의 두 번째 요소를 해당 요소 앞의 배열내에 올바른 위치에 정렬시킨다.

2. 세 번째 요소부터 마지막 요소까지 동일한 과정을 수행한다.

Algorithm

public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int tmp = nums[i];
        int idx = i - 1;
        while (0 <= idx && tmp < nums[idx]) {
            nums[idx + 1] = nums[idx];
            idx--;
        }
        nums[idx + 1] = tmp;
    }
}

Complexixy Analysis

• Time Complexity

최악(Worst) : 배열 nums가 내림차순으로 정렬되어 있다면 배열 nums의 길이(n)에 따른 for반복문 내부의 while반복문의 실행 횟수가 (n - 1) + (n - 2) + … + 1 = n(n - 1) / 2가 된다. 따라서 O(n²)의 시간 복잡도를 가진다.

평균(Average) : 배열 nums가 오름차순으로 평균 정도로 정렬되어 있다면 nums의 길이(n)에 따른 for반복문 내부의 while반복문의 실행 횟수가 ((n - 1) + (n - 2) + … + 1) / 2 = n(n - 1) / 4가 된다. 따라서 O(n²)의 시간 복잡도를 가진다.

최선(Best) : 배열 nums가 오름차순으로 정렬되어 있다면 nums의 길이(n)에 따른 for반복문의 내부 while반복문의 실행 횟수가 n번이 되므로 O(n)의 시간 복잡도를 가진다.

• Space Complexity

배열 nums의 길이(n)에 따라 증가하거나 감소되어 할당받는 메모리 공간이 없으므로 모든 경우에 O(1)의 공간 복잡도를 가진다.