[JAVA] 선택 정렬 ( Selection Sort )

학습 내용

• Big-O
• 선택 정렬 구현

---

Big-O

 

• O(1) : 입력 데이터의 크기에 상관없이 일정한 연산 시간이 걸리는 알고리즘.

• O(n) : 입력 데이터의 크기에 비례하여 연산 시간이 걸리는 알고리즘.

• O(n^2) : 입력 데이터의 크기에 제곱하여 연산 시간이 걸리는 알고리즘.

이외의 여러 종류들이 있습니다.

---

선택 정렬 구현

 

1. 자리 바꿈

public static void swapElement(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    // test 성공
}

입력받은 배열의 요소를 자리 바꿈을 하는 로직입니다.

입력 받은 데이터의 크기에 상관없이 일정한 연산 시간을 갖는 로직이여서 O(1) 의 시간 복잡도를 가집니다.

 

 

2. 요소들 중에 작은 값의 인덱스를 반환

public static int indexLowest(int[] arr, int start) {
    int lowIndex = start;
    for (int i = start; i < arr.length; i++) {
        if (arr[i] < arr[lowIndex]) {
            lowIndex = i;
        }
    }
    return lowIndex;

    // test 성공
}

입력받은 배열의 요소를 서로 비교하여 작은 값을 반환 하는 로직입니다.

입력받은 데이터로 루프를 돌기 때문에 O(n) 의 시간 복잡도를 가집니다.

 

 

3. 선택 정렬

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int j = indexLowest(arr, i);
        swapElement(arr, i, j);
    }
    // test 성공
}

입력 받은 배열의 요소중 작은 값을 입력 받고 자리 바꿈을 하는 로직입니다.

루프를 2번 돌기 때문에 O(n^2) 의 시간 복잡도를 가집니다.

 

---

정리

선택 정렬은 N개의 요소들에 대해 N개의 메모리를 사용하여 데이터를 비교합니다.

비교하는 횟수는 많으나 교환 횟수는 적다는 장점을 가지고 있습니다.

내림차순으로 정렬되어 있는 요소들을 오름차순으로 정렬하는데에 좋은 효율을 보여줍니다.