[알고리즘] 선택 정렬

목차

1. 선택정렬의 방식
2. 선택정렬의 장단점
3. 선택정렬의 코드구현(JAVA)

선택정렬의 개념

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 말한다.

선택정렬의 방식

• 1회전
  • 첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
• 2회전
  • 두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
• 3회전
  • 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
• 4회전
  • 네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

선택정렬의 장단점

장점

• 구현이 쉽다.
• 내림차순으로 정렬되어있는 요소를 오름차순으로 재정렬할 때 효율이 좋다.
• 비교 횟수는 많지만, 실제로 교환하는 횟수는 적다. 교환이 많이 일어나는 자료상태라면 효율적이다.

단점

• 서로 떨어져 있는 요소를 교환하기 때문에 안정적이지 않다
• 이미 정렬된 상태에서 소수의 자료가 추가된 후 재정렬 하면 비효율적이다.
• 시간복잡도 O(n2) 로 인하여 정렬 시간이 오래 걸림.

버블정렬의 구현(JAVA)

public class SelectSort {
	
	static void swap(int[]arr,int num1,int num2) {
		int tmp = arr[num1];
		arr[num1] = arr[num2];
		arr[num2] = tmp;
	}
	
	static void selectSort(int[]arr,int size) {

		for(int i=0;i<size-1;i++) {
			int  min = i;
			for(int j=i+1; j<size; j++) {
				if(arr[j]<arr[min]) {
					min =j;
				}
			}		
			swap(arr,min,i);
		}
		
	}
	public static void main(String[] args) {
		
		int[] number = {5,2,1,3,4,5};

		selectSort(number, number.length);
		
		System.out.println(Arrays.toString(number));
		
	}
}