선택정렬

선택정렬이란

현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘입니다.

데이터를 비교하면서 찾기 때문에 비교 정렬이라고도 불립니다.

 

특징

• O(n2)

---

사용법

1. 배열에서 최솟값을 찾는다
2. 최솟값을 맨 앞자리의 값과 교환한다.
3. 나머지 값들 중 최솟값을 찾아 위 1~2 과정을 반복한다.

그림으로 보자면 아래와 같습니다.

 

https://en.wikipedia.org/wiki/Selection_sort

 

추가적으로 공부했던 유튜브 주소입니다.

엔지니어 대한민국) 선택정렬

---

구현하기

public class Selection_Sort {

    public int[] solution(int N, int[] arr) {
        for (int i = 0; i < N - 1; i++) {

            int index = i;

            for (int j = i + 1; j < N; j++) { // 최솟값 찾기
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            swap(arr, index, i);
        }
        return arr;
    }

    public void swap(int[] arr, int index, int i) { // i번째 값과 찾은 최솟값을 서로 교환
        int tmp = arr[i];
        arr[i] = arr[index];
        arr[index] = tmp;

    }
}