선택 정렬 과 시간 복잡도

선택 정렬 알고리즘은 가장 원시적인 방법이다.

데이터가 무작위로 여러 개 있다고 가정하자. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,

그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.

 

다음은 선택 정렬을 사용하여 데이터를 오름차순으로 정렬한 코드다.

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        
        int []arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        
        int Index = 0; //가장 적은 원소의 인덱스
        
        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                if(arr[Index] > arr[j])
                    Index = j;
            }
            
            //swap
            int temp = arr[i];
            arr[i] = arr[Index];
            arr[Index] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

 


선택 정렬 결과

선택 정렬의 시간 복잡도

 

선택 정렬은 N-1 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

또한 매번 가장 작은 수를 찾기 위해 비교 연산이 필요하다.

즉, 연산 횟수는 N + (N-1) + (N-2) + … + 2 이고, 근사치로 N x (N + 1) /2번의 연산을 수행한다.

 

빅오 표기법으로 간단히 O(N²)로 표현할 수 있다.

 

참조:https://scshim.tistory.com/267