[알고리즘] 선택정렬

 

 

선택정렬

선택정렬은 배열 내 요소 하나마다 나머지 요소들 중 최소값을 찾아 해당 위치에 배치하는 방식의 정렬 알고리즘이다,

이 방식은 배열의 첫 번째 요소부터 마지막 요소까지 반복하면서, 각 위치에 맞는 최소값을 찾아 배열 앞부분부터 정렬해 나간다.

 

배열 내 요소 1개당 n개의 배열 모두를 탐색하고,

n개의 요소들에 대해 반복해야하므로  시간복잡도는 N^2 이다.

따라서 배열의 크기가 커질수록 비효율적이지만 구현은 단순하다는 특징이 있다.

 

 

 

int n = Integer.parseInt(sc.next());
int[] arr = new int[n];
for(int i=0; i<n; i++){
    arr[i] = sc.nextInt();
}

//선택정렬 알고리즘 구현
for(int i=0; i<n-1; i++){
    int idx = i;
    for(int j=i+1; j<n; j++){
        if(arr[j] < arr[idx]) idx = j;
    }
    int tmp = arr[i];
    arr[i] = arr[idx];
    arr[idx] = tmp;
}

//정렬된 배열 출력
for(int i=0; i<n; i++){
    System.out.print(arr[i] + " ");
}