[알고리즘] 선택정렬(Selection Sort) - Java(자바)

선택정렬(Selection Sort)

• 원소를 넣을 위치를 이미 정하고, 그 위치에 최솟값을 찾아서 넣는 정렬 방법이다.
  
  • 첫번째 위치에는 배열의 모든 원소를 비교한 뒤, 최솟값을 그자리에 넣는다.
  • 두번째 위치에는 첫번째 자리를 제외한 모든 원소를 비교한 뒤, 최솟값을 그자리에 넣는다.
  • 이과정을 반복하며 정렬한다.
• 시간복잡도는 O(n²)이 걸리며 효율적이지 않다. 
  • 정렬할 때마다 남은 모든 원소를 봐야한다.
  • -> n개라면 첫번째자리 n-1번, 두번째 자리는 n-2번이 반복된다.
• 제자리 정렬(=입력받은 배열외에 다른 메모리가 필요하지 않은 정렬)
• 불안정 정렬(=동일한 값에 대해서도 순서가 변경된다.)
• 구현 방법은 단순해서 쉬운 편이다.

 

 

배열 [6,3,4,1,5,2]이 있을 때, 선택정렬로 정렬하는 과정

 

 

[구현 코드 - JAVA]

public class SelctionSort {
	public static void main(String[] args) {
		int[] arr = {6,3,4,1,5,2};
		
		for(int i=0; i<arr.length; i++) { //원소를 넣을 위치 선택
			int min = i; //최솟값 위치를 저장할 변수
			
			//최솟값 찾기
			for(int j=i+1; j<arr.length; j++) { 
				if(arr[min]>arr[j]) min = j;

			}
			//swap 자리변경
			//arr[i]에 최솟값 저장 
			//arr[min]에 arr[i]에 있던 값 저장
			int temp = arr[min];
			arr[min] = arr[i];
			arr[i] = temp;
		}
		
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
}