[JAVA]정렬(2) - 선택 정렬(Selection Sort)

1. 선택 정렬(Selection Sort)이란?

ㆍ대상 데이터에서 최대나 최소 데이터를 나열된 순으로 찾아가며 선택하는 방법

 

2. 정렬 과정

ㆍ최소값을 찾는다.

ㆍ가장 앞에 있는 데이터와 선택된 데이터를 swap

ㆍ남은 부분이 없을 때까지 반복

 

3. 시간복잡도

ㆍO(n²)

 

4. 코드예제

import java.util.Arrays;

public class SelectionSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		// 5개의 원소를 가지는 배열을 생성
		int[] arr = new int[5];

		// arr배열에 1~6까지의 난수를 넣는다. 
		for (int i = 0; i < arr.length; i++) {
			int n = (int) (Math.random() * arr.length) + 1;
			arr[i] = n;
		}

		System.out.println("정렬 전 : " + Arrays.toString(arr));

		for (int i = 0; i < arr.length; i++) {
			// arr배열의 0번째 원소를 초기값으로 설정한다.
			int minIdx = i;
			// 탐색을 진행하며 가장 작은 값을 찾는다.
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[minIdx] > arr[j]) {
					minIdx = j;
				}
			}
			// 탐색이 끝나면 가장 작은 값을 앞의 원소와 위치를 바꾸어준다.
			int tmp = arr[minIdx];
			arr[minIdx] = arr[i];
			arr[i] = tmp;
		}
		
		System.out.println("정렬 후 : " + Arrays.toString(arr));

	}

}

 

5. 선택 정렬의 장ㆍ단점

ㆍ장점

- 자료 이동 횟수가 미리 결정된다.

ㆍ단점

- 안정성을 만족하지 않는다.

- 즉, 값이 같은 레코드가 존재할 경우 상대적인 위치가 변경될 수 있다.