[Java] 정렬 - 선택, 버블, 삽입

1. 선택 정렬 Selection sort

맨 앞 인덱스부터 전체를 탐색하여, 가장 작은 값을 찾아 앞으로 옮겨 오는 방법 (현재 값과 변경)
가장 작은 값부터 고정 됨 (앞에서부터)

- 시간복잡도: O(n²) (전체 탐색해야 함)

int arr1 [] = { 5, 7, 1, 2, 4, 3, 8, 9, 6, 10 };

for (int i = 0; i < arr1.length - 1; i++) {
    int min_idx = i;
    // 현재 위치 + 1 부터 끝까지 가장 작은 값의 인덱스 저장
    for (int j = i + 1; j < arr1.length; j++) {
        if (arr1[j] < arr1[min_idx]) {
            min_idx = j;
        }
    }
    
    // 가장 작은 값과 현재 값 바꾸기
    int temp = arr1[i];
    arr1[i] = arr1[min_idx];
    arr1[min_idx] = temp;
}

 

2. 버블 정렬 Selection sort

앞에서부터 두 값씩 비교하며 작은 값을 앞으로, 큰 값을 뒤로 보냄
가장 큰 값부터 고정 됨

- 시간복잡도: O(n²) (전체 탐색해야 함)

int arr2 [] = { 5, 7, 1, 2, 4, 3, 8, 9, 6, 10 };

for (int i = arr2.length - 1; i > 0; i--) {
    for (int j = 0; j < i; j++) {
        if (arr2[j] > arr2[j + 1]) { // 여기서 부등호 반대로 하면 큰것부터 정렬 가능
            int temp = arr2[j];
            arr2[j] = arr2[j + 1];
            arr2[j + 1] = temp;
        }
    }
}

3. 삽입 정렬 Selection sort

특정한 원소에서 앞의 원소들을 살펴보며 알맞은 위치에 들어감
앞으로 하나씩 이동하면서 더 작은 경우 값 변경

- 시간복잡도: O(n²) 

int arr3 [] = { 5, 7, 1, 2, 4, 3, 8, 9, 6, 10 };

for (int i = 1; i < arr3.length; i++) {
    while (i > 0 && arr3[i] < arr3[i - 1]) {    // 두 조건 순서 바꾸면 에러
        int temp = arr3[i];
        arr3[i] = arr3[i - 1];
        arr3[i - 1] = temp;
        i--;
    }
}