정렬 알고리듬(1)

목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리듬
기본적으로 퀵 정렬 사용을 권장한다

버블 정렬

---

평균 : O(n2), 최악 : O(n2), 메모리 : O(1), 안정성 : O
이웃 요소 둘을 비교해서 올바른 순서로 고치는 과정을 반복
한번 목록을 순회할 때마다 가장 큰 값이 제일 위로 올라감

for (int i = 0; i < intArr.length - 1; ++i) {
    for (int j = 0; j < intArr.length - i - 1; ++j) {
        if (intArr[j] > intArr[j + 1]) {
            int temp = intArr[j];
            intArr[j] = intArr[j + 1];
            intArr[j + 1] = temp;
        }
    }
}

선택 정렬

---

평균 : O(n2), 최악 : O(n2), 메모리 : O(1), 안정성 : X
가장 큰 값, 가장 작은 값을 선택하여 정렬

        for (int i = 0; i < intArr.length - 1; ++i) {
            for (int j = i; j < intArr.length; ++j) {
                if (intArr[i] > intArr[j]) {
                    int temp = intArr[i];
                    intArr[i] = intArr[j];
                    intArr[j] = temp;
                }
            }
        }

삽입 정렬

---

평균 : O(n2), 최악 : O(n2), 메모리 : O(1), 안정성 : O
목록을 차례대로 훑으면서 아래와 같은 과정 반복
현재 위치 요소 선택
앞서 방문했던 요소들을 확인하여 넣어야 할 위치 확인 후 삽입
삽입으로 인해 다른 요소가 오른쪽으로 밀릴 수 있음

for (int i = 0; i < intArr.length; ++i) {
    int target = intArr[i];
    int j = i - 1;
    while (j >= 0 && target < intArr[j]) {
        intArr[j + 1] = intArr[j];
        j--;
    }
    intArr[j + 1] = target;
}