정렬 알고리즘 :: 선택정렬(Selection Sort)

선택정렬 Selection Sort

 

 

최소값을 찾아서 가장 앞에부터 차곡차곡 위치시켜 정렬하는 방법으로,

최소값을 선택하기때문에 선택정렬이라고 한다.

 

---

~ 광고 타임 ~

---

 

예를 들어, 배열 { 5, 1, 7, 10, 3} 이 주어졌고 이를 선택정렬로 정렬하고자 한다면 다음과 같다.

 

5	1	7	10	3	최소값 1을 선택하여 첫번째 값과 자리를 바꾼다.
1	5	7	10	3	최소값 3을 선택하여 두번째 값과 자리를 바꾼다.
1	3	7	10	5	최소값 5를 선택하여 세번째 값과 자리를 바꾼다.
1	3	5	10	7	최소값 7을 선택하여 네번째 값과 자리를 바꾼다.
1	3	5	7	10	데이터 열 끝까지 정렬 했으므로 종료한다.
1	3	5	7	10	정렬이 완료되었다.

 

표와 같이 배열 내 최소값을 찾아서 앞으로 차곡차곡 보내는 방식을 반복하게 된다.

시간복잡도는 O(n^2)에 해당하며 데이터가 많아질수록 효율이 급격하게 떨어진다.

이에 대한 설명은 앞서 '정렬 알고리즘 :: 버블소트' 포스팅에서 했으므로 참고하길 바란다.

 

 

 

JAVA 코드

 

package tisory.blog.it_ing;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		System.out.println(" == 아이티-잉 정렬 알고리즘 == \n");
		int[] arr = {5, 1, 7, 10, 3};
		
		fn_SelectionSort(arr);
		
	}
	private static void fn_SelectionSort(int[] arr) {
		int min=0, temp=0, cnt=0;
		
		System.out.println("#3. 선택정렬");
		System.out.println("Input : " + Arrays.toString(arr));
		for(int i=0; i<arr.length-1; i++){
			min=i;
			for(int j=i+1; j<arr.length; j++){
				if(arr[min] > arr[j]){
					min = j;
				}
			}
			cnt++;
			temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
			System.out.println("STEP" + cnt+ " : " + Arrays.toString(arr));
		}
		System.out.println("Result : " + Arrays.toString(arr));
	}
}

 

결과

 

 

 

 

 

---

~ 광고 타임 ~

---

 

 

 

C/C++ 코드

 

#include <stdio.h>

//임시로 작성한 출력 함수
void printArr(int *arr, int len){
	int i=0;

	for(i=0; i<len; i++){
		printf(" %d", arr[i]);
	}
	printf("\n");
}

int main(void){
	int arr[5] = {5, 1, 7, 10, 3};
	int i, j, min=0, temp=0, cnt=0, len=sizeof(arr)/sizeof(int);

	printf("#3. 선택정렬\ninput : ");
	printArr(arr, len); // 출력

	for(i=0; i<len-1; i++){
		min = i;
		for(j=i+1; j<len; j++){
			if(arr[min] > arr[j]){
				min = j;
			}
		}
		cnt++;
		temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
		printf("STEP%d :", cnt);
		printArr(arr, len);
	}
	printf("Result : ");
	printArr(arr, len);
		
	return 0;
}

 

 

결과

 

 

 

 

 

 

 

끝.