버블 정렬 , 선택 정렬 , 삽입 정렬

참고

@minji0801 : 버블 정렬 vs 선택 정렬 vs 삽입 정렬 차이

shinsunyoung : 기본적인 정렬 방법들(선택, 삽입, 버블)에 대해 알아보자

---

요약

모두 O(n²)

버블 정렬

• 인접한 두 데이터만 비교하면서 정렬
• 오름차순 정렬 시 데이터 집합의 끝에 큰 수를 위치 시키면서 정렬 됨

선택 정렬

• 0번 인덱스부터 key로 두어 데이터 집합에서 최소값을 찾아 key와 교환하며 정렬
• 오름차순 정렬 시 데이터 집합의 앞에 작은 수를 위치 시키면서 정렬 됨

삽입 정렬

• 1번 인덱스부터 key로 두어 탐색을 시작하며,
  key 왼쪽 구간에 있는 데이터와 비교하여
  왼쪽 구간의 데이터들 중
  key보다 큰 값들의 앞에 삽입하여 정렬

코드

버블정렬

public int[] 버블정렬(int n, int[] arr) {

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }

    return arr;
}

선택정렬

public int[] 선택정렬(int n, int[] arr) {

    for (int key = 0; key < n - 1; key++) {
        int min = key;
        for (int i = key + 1; i < n; i++) {
            if (arr[min] > arr[i]) {
                min = i;
            }
        }

        int tmp = arr[min];
        arr[min] = arr[key];
        arr[key] = tmp;
    }

    return arr;
}

삽입정렬

public int[] 삽입정렬(int n, int[] arr) {

    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            if (key >= arr[j])
                break;

            arr[j + 1] = arr[j];
        }

        arr[j + 1] = key;
    }

    return arr;
}