자료구조_정렬 ① 선택정렬

 

 

[1] 선택정렬

---

(1) 선택정렬 개념 

selection 정렬

처음 데이터를 기준으로 하여 나머지 모든 데이터와 비교 후 가장 작은 값을 처음 기준이 되는 데이터 위치로 이동하는 과정을 반복하여 정렬함

1회전이 끝나면 두번째 데이터를 기준으로 모두 비교하여 최소값을 두번째 위치로 이동하는 과정을 반복함 

 

(2) 선택정렬 과정 

1번째 패스쓰루에서 최소값 찾기  + 그 최소값을 인덱스 0 위치에 넣기

2번째 패스쓰루에서 0인덱스를 제외한 나머지에서 최소값찾기 + 그 최소값을 인덱스 1 위치에 넣기

3번째 패스쓰루에서 0, 1 인덱스를 제외한 나머지에서 최소값찾기 + 그 최소값을 인덱스 2위치에 넣기

...

마지막 패스쓰루에서 마지막 인덱스와 최소값이 동일할때 종료

 

(3) 시간복잡도 O(N⌒2)

public class Selection_Sort {
 
	public static void selection_sort(int[] a) {
		selection_sort(a, a.length);
	}
	
	private static void selection_sort(int[] a, int size) {
		
		for(int i = 0; i < size - 1; i++) {
			int min_index = i;	
			
			// 최솟값을 갖고있는 인덱스 찾기 
			for(int j = i + 1; j < size; j++) {
				if(a[j] < a[min_index]) {
					min_index = j;
				}
			}
			
			// i번째 값과 찾은 최솟값을 서로 교환 
			swap(a, min_index, i);
		}
	}
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
}

버블정렬 O(N⌒2)

선택정렬 O(N⌒2 / 2)  

이지만 빅오 표기법은 상수는 무시하기 때문에 선택정렬은 버블 정렬보다는 조금 더 빠르지만

빅오표기법으로 하면 O(N⌒2)  이기에 똑같다고는 표현한다