1.1 정렬_선택정렬

 

 

선택정렬 : 가장 작은 값을 선택해서 제일앞으로 보내는 알고리즘(오름차순)

• 시간복잡도 : O(N^2)

ex)

int[] arr = {1, 3, 4, 5, 6, 2, 8, 7}; - 오름차순 정렬

1. arr[0]~arr[arr.lenth-1] 까지 최소 값을 찾아서 arr[0]와 스와프
2. arr[1]~arr[arr.lenth-1] 까지 최소 값을 찾아서 arr[1]와 스와프

                                        .

                                        .

                                        .

                                        .

                                      반복

arr = {1, 2, 3, 4, 5, 6, 7, 8}

public class Blog {
 
    public static void main(String[] args) {
        int[] arr = { 1, 3, 4, 5, 6, 2, 8, 7 };
        int temp;
        for (int i = 0; i < arr.length; i++) {
            int min = 99999;
            int index = 0;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < min) {
                    temp = min;
                    min = arr[j];
                    index = j;
                }
            }
            arr[index] = arr[i];
            arr[i] = min;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ", ");
        }
    }
}
 

선택정렬의 연산은 배열의 길이 N에 대히여

N * { ( N + 1 ) / 2 } 번 연산 하므로

시간복잡도는 O(N^2)이다.