선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

기준 위치에 맞는 원소를 '선택'하여 자리를 교환하는 방식으로 정렬.

​

전체 비교 횟수는 n개의 원소에 대해 n(n-1)/2 이고, 어떤 경우에서나 비교 횟수가 같기 때문에 시간 복잡도는 O(n^2)이다.

​

예시)

{57, 16, 41, 2, 50, 6}

​

1. 첫 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다.

{57, 16, 41, 2, 50, 6}

기준 위치 가장 작은 원소 2

====>

{2, 16, 41, 57, 50, 6}

​

2. 두 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다.

{2, 16, 41, 57, 50, 6}

기준 위치 가장 작은 원소 6

====>

{2, 6, 41, 57, 50, 16}

​

3. 세 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다.

{2, 6, 41, 57, 50, 16}

기준 위치 가장 작은 원소 16

====>

{2, 6, 16, 57, 50, 41}

​

4. 네 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다.

{2, 6, 16, 57, 50, 41}

기준 위치 가장 작은 원소 41

====>

{2, 6, 16, 41, 50, 57}

​

5. 다섯 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다.

{2, 6, 16, 41, 50, 57}

기준 위치 겸 가장 작은 원소 50

====>

{2, 6, 16, 41, 50, 57} (제자리)

​

6. 마지막 남은 원소는 가장 큰 원소이므로 종료한다.

{2, 6, 16, 41, 50, 57}

​

프로그램 작성)

package test;

class Sort {
	public void selectionSort(int[] a) {
		int i, j, min;
		
		// 기준 위치 i
		for(i=0; i<a.length-1; i++) {
			min = i; // 우선 기준 위치를 최소 값 위치로
			
			// 기준 위치 다음 원소부터 비교
			for(j=i+1; j<a.length; j++) {
				if(a[j] < a[min]) {
					// 제일 작은 원소 찾기
					min = j;
				}
			}
			
			swap(a, min, i);
		}
	}
	
	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.selectionSort(a);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)