선택정렬 (selection sort) 을 간단하게 알아보자.

 

선택 정렬을 간단하게 설명하면?

가장 작은 숫자를 선택하는 방식으로 정렬을 진행하기 때문에 선택 정렬!

 

1. 배열의 최솟값을 찾아 첫 번째 인덱스부터 차례대로 그 자리에 스왑 합니다. 
2. 최솟값이 들어간 배열은 더 이상 건들지 않습니다. 이미 정렬이 된 인덱스들이기 때문이죠.
3. 정렬이 안된 인덱스들 중에서 다시 최솟값을 알아내 정렬이 된 인덱스 다음 인덱스에 넣습니다.

 

 

구현 과정

import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		
		for(int i=0; i<A.length-1; i++) {          // n-1까지 정렬하면 자동으로 n번째 인덱스는 정렬됨.  
			int min=i;                             // i를 최소값으로 가정.
			 for(int j=i+1; j<A.length; j++) {     // i번째 인덱스를 최소값으로 가정하고 그 다음 인덱스부터 비교.
				 if(A[min]>A[j]) {                 // A[min]보다 작으면 j가 min이 된다. 
					 min=j;
				 }
			 }
			 int temp=A[min];
			 A[min]=A[i];
			 A[i]=temp;
		}
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

 

시간 복잡도 

• Worst : O(n^2)
• Average : O(n^2)
• Best : O(n^2)