BubbleSort

인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식
O(n^2)

Selection Sort

최소/최대값을 선택하는 정렬
최소값을 선택하여, 맨 앞으로 swap한다.
O(n^2)

Insertion Sort

앞은 이미 정렬된 상태, 자신의 위치를 찾아서 삽입한다.
O(n^2)

void insertionSort(int arr[], int size) {
    int i, j,key;
 
    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0&&arr[j]>key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

MergeSort

• divide and conquer
  • 원소가 1개될 때까지 divide한다.
  • divide할 때 종료 조건!! (left <= right : 더이상 쪼갤 것 없음)
  • left, mid, right
  • 별도의 temp 배열에 정렬한 후 재복사

class Main {

    static class Sort {
        public void merge(int[] numbers, int startIndex, int midIndex, int lastIndex) {
            int s = startIndex;
            int l = midIndex + 1;

            int index = startIndex;
            int[] temp = new int[numbers.length];
            while (s <= midIndex && l <= lastIndex) {
                if (numbers[s] < numbers[l]) {
                    temp[index] = numbers[s];
                    s++;
                } else {
                    temp[index] = numbers[l];
                    l++;
                }
                index++;
            }

            for (; s <= midIndex; s++) {
                temp[index] = numbers[s];
                index++;
            }
            for (; l <= lastIndex; l++) {
                temp[index] = numbers[l];
                index++;
            }

            for (int i = startIndex; i <= lastIndex; i++) {
                numbers[i] = temp[i];
            }
            System.out.println();
        }

        public void mergeSort(int[] numbers, int leftIndex, int rightIndex) {
            if (leftIndex >= rightIndex) {
                return;
            }

            int mid = (leftIndex + rightIndex) / 2;
            mergeSort(numbers, leftIndex, mid);
            mergeSort(numbers, mid + 1, rightIndex);
            merge(numbers, leftIndex, mid, rightIndex);
        }
    }
    public static void main(String[] args) {
        int[] numbers = {1, 4, 9, 1, 2};
        new Sort().mergeSort(numbers, 0, numbers.length - 1);
        System.out.println();
    }
}

QuickSort

• divide and conquer
• pivot을 기준으로 정렬한다.
  • (왼: pivot보다 작음) (pivot) (오: pivot보다 크다.)
  • 정렬 방법: 왼쪽에 pivot보다 큰 애 & 오른쪽에 pivot보다 작은 애 swap
    • left에서
  • 마지막에 left Index + 1과 left를 바꾼다.
• 정렬된 왼, 오를 다시 quick sort한다.
• 최악의 경우
  • 왼, 오 배열이 쪼개지지 않을 때
  • 데이터들이 정렬되어있거나 역순으로 정렬되어 있을 때
  • [1, 2, 3, 4, 5, 6, 7] : pivot을 첫번째로 잡을 때

시간복잡도

시간복잡도는 트리를 생각하면 된다.
배열을 처음부터 끝까지 비교할 때
for (int i ... n) : O(N)

Merge Sort

요 배열을 처음부터 끝까지 비교하는 것을 절반만 수행한다.
N * logN : O(NlogN)

Quick Sort

최악: O(n^2)

Heap 정렬

Heap 자료 구조를 활용한 정렬
Heap

• 완전 이진 트리
  • left 부터 꽉 채워나간다.
• 반정렬
  • 부모는 자식보다 크다.
  • 자식간에 정렬을 보장하지 않는다.

방법

1. max/min heap을 만든다.
2. delete하며 정렬한다.

• O(NlogN)
  Tree의 높이 : logN
  개수: N
• 1) max heap에서 root는 최대값을 의미한다.
• 2) root ↔ 맨 마지막 swap한다.
• 3) max heap으로 만들어준다.
  • 맨 뒤에 있던 놈을 기준으로 비교한다.

O(NlogN)

https://zeddios.tistory.com/56