[JAVA] 정렬 여러가지

1. 버블 정렬
2. 선택 정렬
3. 삽입 정렬
4. 퀵 정렬
5. 병합 정렬
6. 기수 정렬

---

1. 버블 정렬

두 인접한 데이터의 크기를 비교하여 정렬.

간단한 구조, 느린 속도. 시간복잡도 : O(n^2)

int[] n = {5,4,3,2,1,1,2,3,4,5};

// 버블 정렬
for (int i = 0; i < n.length; i++) {
    for (int j = 0; j < n.length - 1; j++) {
        if (n[j] > n[j+1]) {
            int temp = n[j];
            n[j] = n[j+1];
            n[j+1] = temp;
        }
    }
}

결과 : [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]

 

인접한 데이터끼리 자리교체가 이루어지기 때문에 맨 마지막 부터 정렬되기 시작한다 -> 길이를 줄여나간다.

더 이상 자리교체가 이루어지지 않는다면 while문을 종료한다.

이를 통해 약간의 성능 개선이 가능...

boolean swap = true;
int length = n.length;
while (swap) {
    swap = false;
    for (int i = 0; i < length - 1; i++) {
        if (n[i] > n[i+1]) {
            int temp = n[i];
            n[i] = n[i+1];
            n[i+1] = temp;
            swap = true;
        }
    }
    length--;
}

---

2. 선택 정렬

최소 또는 최댓값을 찾고 남은 데이터와 비교하여 자리 교체를 하는 알고리즘.

구현 방법이 약간 복잡. 속도 느림. 시간복잡도 : O(n^2)

for (int i = 0; i < n.length; i++) {
    int min = i;
    for (int j = i + 1; j < n.length; j++) {
        if (n[j] < n[min]) {
            min = j;
        }
    }

    if (n[i] > n[min]) {
        int temp = n[i];
        n[i] = n[min];
        n[min] = temp;
    }
}

가장 낮은 숫자의 index 번호를 min으로 설정.

i번째 n이 min번째 n보다 크다면 자리 교체

---

3. 삽입 정렬

정렬된 데이터 범위 내에서 정렬되지 않은 선택된 데이터를 적절하게 삽입해야하는 알고리즘.

시간 복잡도는 O(n^2)

for (int i = 0; i < n.length; i++) {
    int insert_index = i;
    int insert_value = n[i];
    for (int j = i - 1; j >= 0; j--) {
        if (n[j] < insert_value) {
            insert_index = j + 1;
            break;
        }
        if (j == 0) {
            insert_index = 0;
        }
    }
    for (int j = i; j > insert_index; j--) {
        n[j] = n[j-1];
    }
    n[insert_index] = insert_value;
}

---

4. 퀵 정렬

pivot (기준값)을 선정하여 pivot의 왼쪽과 오른쪽을 분할과 정복해 나가며, pivot 값보다 작은값과 큰 값을 분류하여 정렬하는 알고리즘.

pivot을 잘 선택해야한다. pivot값에 따라 시간 복잡도가 느려지거나 빨라진ㅈ다. 평균 시간 복잡도는 O(nlogn)

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

public static void quickSort(int[] n, int left, int right) {
    if (left < right) {
        int pivot = partition(n, left, right);
        quickSort(n, left, pivot - 1);
        quickSort(n, pivot + 1, right);
    }
}

public static int partition(int[] n, int left, int right) {
    int pivot = n[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (n[j] < pivot) {
            i++;
            swap(n, i, j);
        }
    }
    swap(n, i + 1, right);
    return i + 1;
}

private static void swap(int[] n, int i, int j) {
    int temp = n[i];
    n[i] = n[j];
    n[j] = temp;
}

---

5. 병합 정렬

분할 정복 방식을 사용해 정렬하는 알고리즘. 평균 시간복잡도는 O(nlogn)

mergeSort(n);

public static void mergeSort(int[] n) {
    if (n.length < 2) {
        return;
    }
    int mid = n.length / 2;
    int[] left_n = new int[mid];
    int[] right_n = new int[n.length - mid];
    for (int i = 0; i < mid; i++) {
        left_n[i] = n[i];
    }
    for (int i = mid; i < n.length; i++) {
        right_n[i - mid] = n[i];
    }
    mergeSort(left_n);
    mergeSort(right_n);
    merge(n, left_n, right_n);
}

private static void merge(int[] n, int[] left_n, int[] right_n) {
    int i = 0, j = 0, k = 0;
    while (i < left_n.length && j < right_n.length) {
        if (left_n[i] <= right_n[j]) {
            n[k++] = left_n[i++];
        } else {
            n[k++] = right_n[j++];
        }
    }
    while (i < left_n.length) {
        n[k++] = left_n[i++];
    }
    while (j < right_n.length) {
        n[k++] = right_n[j++];
    }
}

---

6. 기수 정렬

0-9 까지의 값을 놓고 자릿수에 따라 값을 비교하여 정렬

945와 623을 비교한다면, 1의 자리부터 5와 3, 10의 자리 4와 2, 100의 자리 9와 6을 비교.

int[] n = {331, 75, 65, 90, 802, 524, 2, 66};

radixSort(n);

public static void radixSort(int[] n) {
    int max = getMax(n);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(n, exp);
    }
}

private static void countSort(int[] n, int exp) {
    int[] output = new int[n.length];
    int[] count = new int[10];

    for (int i = 0; i < n.length; i++) {
        count[(n[i] / exp) % 10]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n.length - 1; i >= 0; i--) {
        output[count[(n[i] / exp) % 10] - 1] = n[i];
        count[(n[i] / exp) % 10]--;
    }

    for (int i = 0; i < n.length; i++) {
        n[i] = output[i];
    }
}

private static int getMax(int[] n) {
    int max = n[0];
    for (int i = 1; i < n.length; i++) {
        if (n[i] > max) {
            max = n[i];
        }
    }
    return max;
}

결과 : [2, 65, 66, 75, 90, 331, 524, 802]