[알고리즘] 정렬

|  정렬이란

- 특정 값을 기준으로 데이터를 순서대로 배치하는 방법

- 기본 : 버블, 삽입, 선택

- 비교적 속도가 빠른 정렬 : 합병, 힙, 퀵, 트리

- 하이브리드 정렬 : 팀, 블록병합, 인트로

- 기타 : 기수, 계수(카운팅), 셸, 보고

 

|  정렬의 시간복잡도 요약

- 안정성이라는 것은, 어떤 데이터 { 1, 2, 3, 1, 1, 1 } 을 정렬한다고 할 때,

  같은 숫자 1에 대해서 { 1, 1, 1, 1 } 의 순서가 유지되도록 정렬되는 것을 '안정성이 있다'라고 한다.

- 아래의 보조 메모리는 추가적으로 드는 메모리를 이야기하는데,

  버블이나 삽입, 선택의 경우 swap시에 드는 변수 1개만 필요하기 때문에 보조메모리가 1개만 소요된다.

정렬 방법	시간 복잡도			보조 메모리	안정성
	Ω(n)	Θ(n)	O(n)
버블 정렬	n	n^2	n^2	1	o
삽입 정렬	n	n^2	n^2	1	o
선택 정렬	n^2	n^2	n^2	1	x
합병 정렬	n log⁡n	n log⁡n	n log⁡n	n	o
힙 정렬	n log⁡n	n log⁡n	n log⁡n	1	x
퀵 정렬	n log⁡n	n log⁡n	n^2	log⁡n	x
트리 정렬	n log⁡n	n log⁡n	n^2	n	x
기수 정렬	dn (*d:자릿수)	dn	dn	n+k	o
계수 정렬	n+k (*k:max)	n+k	n+k	n+k	o
셸 정렬	n log⁡n	gap에 따라 다름	n^2	1	x

 

|  버블정렬 / 삽입 정렬 / 선택 정렬

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

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

// 선택 정렬
private static void selectionSort(int[] arr) {
    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;
            }
        }
        swap(arr, i, min);
    }
}

 

|  합병정렬 / 힙 정렬 / 퀵 정렬 / 트리 정렬

1. 합병정렬

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 lCursor = left;
    int rCursor = mid + 1;
    int idx = left;

    while (lCursor <= mid || rCursor <= right){
        if (lCursor <= mid && rCursor <= right) {
            if (arr[lCursor] <= arr[rCursor]) {
                tmp[idx++] = arr[lCursor++];
            }else {
                tmp[idx++] = arr[rCursor++];
            }
        } else if (lCursor <= mid && rCursor > right) {
            tmp[idx++] = arr[lCursor++];
        } else {
            tmp[idx++] = arr[rCursor++];
        }
    }

    for (int i = left; i <= right; i++) {
        arr[i] = tmp[i];
    }
}

2. 힙 정렬

public static void heapSort(int[] arr) {
    // 가장 끝의 자식이 있는 부모노드를 잡아서 최대힙구조로 정렬
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }

    // 가장 앞의 노드가 최대값임을 이용하여 나머지 정렬
    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 = parentIdx * 2 + 1;
    int rightIdx = parentIdx * 2 + 2;
    int maxIdx = parentIdx;

    if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
        maxIdx = leftIdx;
    }

    if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
        maxIdx = rightIdx;
    }

    if (maxIdx != parentIdx) {
        swap(arr, parentIdx, maxIdx);
        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;
}

3. 퀵 정렬

- pivot 값은 처음값이거나 중앙값이 될 수 있다. (상황에 맞게 선택하면 된다)

- 퀵 정렬은 pivot을 기준으로 좌우 정렬을 하고, pivot의 양 옆을 다시 분할하여 정렬하는 것을 반복한다.

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) {
    // 피봇값과 양 옆의 커서를 지정
    int pivot = arr[left];
    int lCursor = left;
    int rCursor = right;

    // 1. 양 끝의 커서가 서로 같기 전까지
    // 우측은 피봇값보다 더 작은 값을 찾고
    // 좌측은 피봇값보다 같거나 더 큰 값을 찾아 swap
    // 2. 양 끝의 커서가 서로 같아지면
    // 한쪽 커서와 피봇을 swap
    while (lCursor < rCursor) {
    	while (arr[rCursor] > pivot && lCursor < rCursor) {
            rCursor--;
        }
    
        while (arr[lCursor] <= pivot && lCursor < rCursor) {
            lCursor++;
        }

        swap(arr, lCursor, rCursor);
    }
    swap(arr, left, lCursor);

    return lCursor;
}

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

4. 트리 정렬

- 이진탐색트리를 만들어 정렬하는 방식으로, 알고리즘 복잡도는 NlogN이다.

- 이 부분은 비선형구조 > 이진탐색트리 포스팅에 적은 AVL, Red-Black을 확인해주세요.

 

|  기수 정렬 / 계수 정렬 / 셸 정렬

1. 기수 정렬

- 기수 : 자릿수를 의미한다.

- 기수정렬 : 일의 자리, 십의 자리, 백의 자리.. 순으로 각 자릿수에 해당되는 수를 큐에 담은 후 기존 배열에 넣는 방식

public static void radixSort(int[] arr) {
    // 각 자리에 큐를 담은 배열
    ArrayList<Queue<Integer>> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) { // 10진수 기준으로 자리 수 0 ~ 9
        list.add(new LinkedList<>());
    }

    // 최대 자릿수
    int maxLen = getMaxLen(arr);
    // 나누는 수
    int div = 1;
    // 배열에 넣어줄 인덱스
    int idx = 0;

    // 기수 정렬에 대한 반복문
    for (int i = 0; i < maxLen; i++) {
        // 해당 자릿수의 큐에 데이터를 추가
        for (int j = 0; j < arr.length; j++) {
            list.get((arr[j] / div) % 10).offer(arr[j]);
        }

        // 해당 자릿수의 큐를 가져와서, 기존 배열(arr)에 넣는다.
        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]); // 자릿수
        if (maxLen < len) {
            maxLen = len;
        }
    }
    return maxLen;
}

2. 계수 정렬

- 계수 : 관계가 있는 수, 상수를 의미한다.

- 계수정렬 : 상수 data 수열에서 최대값 + 1을 size로 배열에 생성해, 카운트한 후 다시 기존 배열에 넣는 방식

public static void countingSort(int[] arr) {
    // 최댓값의 + 1 만큼 배열을 잡아둔다
    int max = Arrays.stream(arr).max().getAsInt();
    int[] cntArr = new int[max + 1];

    // 숫자데이터에 해당되는 인덱스의 cnt를 하나 늘린다.
    for (int i = 0; i < arr.length; i++) {
        cntArr[arr[i]]++;
    }

    // cntArr을 한바퀴씩 돌면서 기존 배열(arr)에 해당 인덱스의 갯수만큼 삽입
    int idx = 0;
    for (int i = 0; i < cntArr.length; i++) {
        while (cntArr[i] > 0) {
            arr[idx++] = i;
            cntArr[i] -= 1;
        }
    }
}

//최댓값 하나만 너무 크면 비효율적 -> HashMap을 통해 보완할 수 있다
public static void countingSort2(int[] arr) {
    // key : data, value : 갯수
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int item : arr) {
        map.put(item, map.getOrDefault(item, 0) + 1);
    }

    // key를 배열에 담아서 정렬한 후, 기존 배열(arr)에 해당인덱스의 갯수만큼 다시 삽입한다.
    ArrayList<Integer> keyList = new ArrayList<>(map.keySet());
    Collections.sort(keyList);
    int idx = 0;
    for (int key : keyList) {
        int cnt = map.get(key);
        while (cnt > 0) {
            arr[idx++] = key;
            cnt--;
        }
    }
}

3. 셸 정렬

- 삽입 정렬을 보완한 형태로 

- 삽입 정렬은 idx 1부터 arr.length-1까지 처음부터 좌측의 데이터를 확인했다면

- 셸 정렬은 간격을 두고 간격의 거리만큼 떨어진 데이터를 확인하는 것을 반복한다.

- 이렇게 하게 되면 기존의 삽입 정렬 보다는 교환 횟수가 감소할 수 있다.

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

    // 더 이상 간격이 없을 때까지 간격을 /2한다.
    for (int g = gap; g > 0; g /= 2) {
        // 초기 간격부터 간격의 길이만큼 증가하면서
        for (int i = g; i < arr.length; i++) {
            // 지정된 위치의 좌측 간격들의 데이터를 비교 & 교환한다.
            int tmp = arr[i]; // 짚은 데이터를 tmp에 넣고
            int j = 0; // 짚은 데이터의 좌측 데이터들을 확인
            for (j = i - g; j >= 0; j -= g) {
                // 큰 값이 나오면 좌측 데이터들을 하나씩 당긴다
                if (arr[j] > arr[j + g]) {
                    arr[j + g] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + g] = tmp;
        }
    }
}

 

 

[ 출처 ]

- 부트캠프 강의를 듣고 정리한 내용입니다.