1. 선택정렬

다음 숫자를 오름차순으로 나열하고 싶다면?

10 9 8 7 6 5 4 3 2 1

 

첫 번째로 가장 직관적인 생각은  가장 작은 것을 선택해서 앞으로 보내는 방법은 어떨까?

이 방법을 바로 "선택 정렬" 알고리즘이라고 합니다.

 

package algorithm;

public class algorithm01 {

	public static void main(String[] args) {
		int min =0 , 
			temp =0,
			index = 0;
			
		int[] array = {10,9,8,7,6,5,4,3,2,1};//index배열을 크기값10으로 초기화.및 선언
		
		for(int i =0; i <10; i++) {
			min = 9999;
			for(int j =i; j <10; j++) {
				if (min > array[j]) {
					min = array[j];
					index = j;
				}
			}
			temp = array[i];
			array[i]=array[index];
			array[index] = temp;
		}
		
		for(int i =0; i<10; i++)
		System.out.printf("%d" , array[i]);
	}
}


//

이해하기 위해 말로 풀어 보겠습니다.

먼저 10개의 숫자가 있습니다.

min변수에 가장 큰 9999 값을 넣고 무조건 첫 번째 값을 min이라는 변수에 담습니다.

이후 두 번째 반복문에서 첫 번째 인덱스에 가장 작은 값을 넣기 위해 10번의 반복을 하면서

최솟값을 정하고 그 최솟값이 있던 인덱스를 확인합니다.

 

첫 번째 반복문에서 임시변수 temp에 첫 번째 배열 값을 담은 뒤

첫 번째 배열 값에 최솟값을 담습니다.

그 이후 최솟값이 있던 배열에 첫 번째 배열 값을 담습니다.

 

그리고 첫 번째 값으로 가장 작은 최솟값이 왔으므로 반복에서 제외 후

2번째부터 똑같은 방식으로 반복문을 돌아서 최솟값을 구해줍니다.

 

min이란 변수는 최소값을 저장하기 위한 변수이며

index는 그 최솟값을 찾은 인덱스입니다.

temp는 배열에서 두 숫자를 바꾸기 위한 변수입니다.

 

 

public class SelectionSort {

    public static void main(String[] args) {

        int[] arr = {3,2,5,1,6};

        for(int i = 0; i < arr.length-1; i++){
            int min = i;
            for(int j =i+1; j <arr.length; j++){
                if( arr[min] > arr[j]){
                    min = j;
                    int temp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = temp;
                }

            }
        }
        System.out.println(Arrays.toString(arr));
    }

}

 

성능은 입력 크기 n에 대한 선택 정렬 알고리즘은 이중 루프로 구성되며, 바깥 루프는 0...(n-2)까지 n-1번 반복하면서 배열의 자리-1(마지막은 정렬됐다는 생각)만큼 반복하며, 최솟값을 찾기 위한 안쪽 루프는 i값에 따라 (n-1), (n-2)... 1까지 비교를 수행한다.

 

선택 정렬은 대략 N * (N-1) /2번가량의 연산을 수행합니다.

컴퓨터는 가장 큰 차수인 N^2만 보고 O(N^2)라고 표현하기도 합니다.

 

즉 선택 정렬의 시간 복잡도는  O(N^2)입니다.

 

 

 

특징 

 

 - 데이터의 입력 상태에 민감하지 않다. 입력 데이터가 어떤 상태의 순서를 갖는지 무관하게 언제나 동일한 수행시간 O(N²)를 갖는다. 

 

- 제자리 정렬 알고리즘이다.

 알고리즘을 보면 입력 데이터가 저장된 공간 이외에 별도의 공간을 상수개(루프 제어 변수 i, j와 임시 변숫값, 최소 변숫값)만을 사용한다. 이것은 전체적으로 아주 작은 공간이므로 제자리 정렬로 취급한다.

 

 - 안정적이지 않은 정렬 알고리즘이다.

 정렬이 이루어질 때 정렬 전의 순서가 유지되지 못하기 때문에 불안정정렬이다.