정렬

정렬

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

버블 정렬 (Bubble Sort)

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

버블 정렬 과정 (1)

버블 정렬 과정 (2)

버블 정렬 구현

알고리즘 flow 파악 용 (실제 돌아가는 코드 X) 의사 코드 (Pseudocode)

bubbleSort(arr[]) {
    arr[SIZE]
    for i = 1 to SIZE - 1 {
        for j = 0 to SIZE - i {
            if (arr[j] > arr[j + 1])
                swap (arr[j], arr[j + 1])
        }
    }
}

삽입 정렬 (Insertion Sort)

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

삽입 정렬 과정

삽입 정렬 구현

의사 코드 (Pseudocode)

insertionSort(arr[]) {
    arr[SIZE]
    for i = 1 to SIZE {
        for j = i to 0 (j--) {
            if (arr[j] < arr[j - 1])
                swap (arr[j], arr[j - 1])
        }
    }
}

선택 정렬 (Selection sort)

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

선택 정렬 과정

선택 정렬 구현

의사 코드 (Pseudocode)

selectionSort(arr[]) {
    arr[SIZE]
    for i = 0 to SIZE - 1 {
        min = i
        for j = i + 1 to SIZE {
            if (arr[j] < arr[min])
                min = j
        }
        swap (arr[i], arr[min])
    }
}

알고리즘 - 정렬_1

// 알고리즘 - 정렬_1

import java.util.Arrays;

public class Main {
    // 오름차순 기준 정렬 알고리즘

    // 버블 정렬
    public static void bubbleSort(int[] arr) {
        // 1.
        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;
                }
            }
        }

        // 2. (1과 2 같은 방식인데 i 인덱스 사용 다르게 참고)
        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;
                }
            }
        }
    }
    
    // 삽입 정렬
    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;
                }

            }
        }
    }

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

        // 2. 최대 값을 찾아 뒤 쪽부터 교환하는 방식
        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;
        }
    }

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

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

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

버블 정렬: [1, 2, 3, 4, 5, 7]
삽입 정렬: [1, 2, 3, 4, 5, 7]
선택 정렬: [1, 2, 3, 4, 5, 7]

합병 정렬 (Merge Sort)

배열을 계속 분할해서 길이가 1 이 되도록 만들고,인접한 부분끼리 정렬하면서 합병하는 방식
알고리즘 복잡도: O(nlogn)

합병 정렬 과정

힙 정렬 (Heap Sort)

힙 자료구조 형태의 정렬 방식
기존 배열을 최대 힙으로 구조 변경 후 정렬 진행
알고리즘 복잡도: O(nlogn)

퀵 정렬 (Quick Sort)

임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식
기준 값이 최소값 또는 최대값으로 지정되는 경우
알고리즘 복잡도: O(𝑛^2)

퀵 정렬 과정 (1)

퀵 정렬 과정 (2)

트리 정렬 (Tree Sort)

이진 탐색 트리(BST) 를 만들어 정렬하는 방식
알고리즘 복잡도: O(nlogn)

합병 정렬

// 알고리즘 - 정렬_2
// 합병 정렬

import java.util.Arrays;

public class Main {
    
    // 합병 정렬
    public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, tmp, left, mid);
            mergeSort(arr, tmp, mid + 1, right);
            merge(arr, tmp, left, right, mid);
        }
    }

    public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
        int p = left;
        int q = mid + 1;
        int idx = p;
        // p, q 둘 중 하나는 해당 배열 범위 안에 있는 동안
        while (p <= mid || q <= right) {
            if (p <= mid && q <= right) {   // 둘 다 범위 안인 경우
                if (arr[p] <= arr[q]) { // 값 비교하여 정렬
                    tmp[idx++] = arr[p++];
                } else {
                    tmp[idx++] = arr[q++];
                }
            } else if (p <= mid && q > right) { // 왼쪽만 남은 경우 이어주기
                tmp[idx++] = arr[p++];
            } else {                            // 오른쪽만 남은 경우 이어주기
                tmp[idx++] = arr[q++];
            }
        }

        for (int i = left; i <= right; i++) {   // 정렬된 부분 데이터 arr 쪽으로
            arr[i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4, 6};
        int[] tmp = new int[arr.length];
        mergeSort(arr, tmp, 0, arr.length - 1);
        System.out.println("합병 정렬: " + Arrays.toString(arr));
    }
}

합병 정렬: [1, 2, 3, 4, 5, 6, 7]

힙 정렬

// 힙 정렬

import java.util.Arrays;

public class Main2 {
    
    // 힙 정렬
    public static void heapSort(int[] arr) {
        // 힙으로 재구성 (maxHeap 기준, 마지막 부모 노드부터)
        for(int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        // maxHeap 기준 root 쪽을 끝 쪽으로 보내면서 재정렬 -> 오름차순
        for(int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }

    public static void heapify(int[] arr, int parentIdx, int size) {
        // 자식 노드 위치
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;

        // 왼쪽 자식 노드가 크면 maxIdx 를 해당 인덱스로 교체
        if(leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
            maxIdx = leftIdx;
        }

        // 오른쪽 자식 노드가 크면 maxIdx 를 해당 인덱스로 교체
        if(rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
            maxIdx = rightIdx;
        }

        // maxIdx 가 바뀐 경우, 부모 노드가 교체되는 것을 의미
        // 교체하고 서브 트리 검사 하도록 재귀 호출
        if(parentIdx != maxIdx) {
            swap(arr, maxIdx, parentIdx);
            heapify(arr, maxIdx, size);
        }
    }

    public 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) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4, 6};
        heapSort(arr);
        System.out.println("힙 정렬: " + Arrays.toString(arr));
    }
}

힙 정렬: [1, 2, 3, 4, 5, 6, 7]

퀵 정렬

// 퀵 정렬

import java.util.Arrays;

public class Main3 {

    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        
        // 분할
        int pivot = partition(arr, left, right);
        
        // 기준값 중심으로 좌우 재귀 호출
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        // 가장 좌측 값을 기준값으로 설정
        // 이외에 기준 값은 배열에서 중간에 있는 값을 고르거나, 임의의 수를 3개 선정 후 중앙 값을 고르는 등의 방법이 있음
        int pivot = arr[left];
        int i = left;
        int j = right;

        while(i < j) {
            while (arr[j] > pivot && i < j) {
                j--;
            }

            while(arr[i] <= pivot && i < j) {
                i++;
            }

            swap(arr, i, j);
        }
        swap(arr, left, i);

        return i;
    }

    public 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 = {6, 2, 7, 9, 4, 5, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("퀵 정렬: " + Arrays.toString(arr));
    }
}

퀵 정렬: [2, 4, 5, 6, 7, 8, 9]

기수 정렬 (Radix Sort)

낮은 자리 수부터 정렬하는 방식
각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요
알고리즘 복잡도: O(dn)
d: 최대 자릿수

기수 정렬 과정 (1)

기수 정렬 과정 (2)

계수 정렬 (Counting Sort)

숫자 끼리 비교하지 않고 카운트를 세서 정렬하는 방식
카운팅을 위한 메모리 필요
알고리즘 복잡도: O(n + k)
k: 정렬 대상 데이터 중 최대 값

계수 정렬 과정

셸 정렬 (Shell Sort)

삽입 정렬의 약점 보완한 정렬 방식
삽입 정렬의 약점
오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는
앞의 데이터와 하나씩 비교하며 모두 교환 필요
이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교
알고리즘 복잡도: O(𝑛^2)
간격 설정에 따라 Worst case는 삽입 정렬과 동일
일반적인 산포 데이터 기준으로는 삽입 정렬에 비해 빠르다.

셸 정렬 과정 (1)

셸 정렬 과정 (2)

정렬 알고리즘 복잡도 Summary

기수 정렬

// 알고리즘 - 정렬_3
// 기수 정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void radixSort(int[] arr) {
        // 기수 테이블 생성
        ArrayList<Queue<Integer>> list = new ArrayList<>();
        for (int i = 0; i < 10; i++)
        {
            list.add(new LinkedList());
        }

        int idx = 0;
        int div = 1;
        int maxLen = getMaxLen(arr);
        // 자리수 만큼 기수 정렬 반복
        for (int i = 0; i < maxLen; i++)
        {
            // 각 자리수에 맞는 큐 위치에 데이터 삽입
            for (int j = 0; j < arr.length; j++) {
                list.get((arr[j] / div) % 10).offer(arr[j]);
            }

            // 다시 순서대로 가져와서 배치
            for (int j = 0; j < 10; j++) {
                Queue<Integer> queue = list.get(j);

                while (!queue.isEmpty()) {
                    arr[idx++] = queue.poll();
                }
            }

            idx = 0;
            div *= 10;
        }
    }

    public static int getMaxLen(int[] arr)
    {
        // 배열에 숫자들 중 가장 긴 자리수 구하기
        int maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            int len = (int)Math.log10(arr[i]) + 1;
            if (maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }


    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
        radixSort(arr);
        System.out.println("기수 정렬: " + Arrays.toString(arr));
    }
}

기수 정렬: [10, 17, 27, 32, 48, 52, 56, 99]

계수 정렬

// 계수 정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class Main2 {
    public static void countingSort(int[] arr) {
        // # 1 일반 배열 사용
        // 최대값 구해서 배열 설정
        int max = Arrays.stream(arr).max().getAsInt();
        int[] cntArr = new int[max + 1];

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

        int idx = 0;
        for (int i = 0; i < cntArr.length; i++) {
            while (cntArr[i] > 0) {
                arr[idx++] = i;
                cntArr[i] -= 1;
            }
        }

        // # 2 Hashmap 사용
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int item: arr) {
            map.put(item, map.getOrDefault(item, 0) + 1);
        }

        int idx2 = 0;
        ArrayList<Integer> list = new ArrayList(map.keySet());
        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            int cnt = map.get(list.get(i));
            while (cnt > 0) {
                arr[idx2++] = list.get(i);
                cnt--;
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 10, 27, 32, 17, 99, 56};
        countingSort(arr);
        System.out.println("계수 정렬: " + Arrays.toString(arr));
    }
}

계수 정렬: [10, 10, 17, 27, 32, 32, 56, 99]

셸 정렬

// 셸 정렬

import java.util.Arrays;

public class Main3 {

    public static void shellSort(int[] arr) {
        // 초기 간격
        int gap = arr.length / 2;

        // 초기 간격부터 간격 반씩 줄여가면서 진행
        for (int g = gap; g > 0; g /= 2) {
            for (int i = g; i < arr.length; i++) {
                int tmp = arr[i];

                int j = 0;
                for (j = i - g; j >= 0; j -= g) {
                    if (arr[j] > tmp) {
                        arr[j + g] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + g] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
        shellSort(arr);
        System.out.println("셸 정렬: " + Arrays.toString(arr));
    }
}

셸 정렬: [10, 17, 27, 32, 48, 52, 56, 99]

출처 : 제로베이스