선택정렬(Selection Sort)- java, python

가장 작은 요소를 골라 맨 앞으로 보내자!

 

🦋 핵심
 장점: 데이터 양이 적을 때 성능이 좋음
        작은 값을 선택하기 위해서 비교는 여러번 수행되지만 교환횟수가 적음
 단점: 100개 이상의 자료에 대해서는 속도가 급격히 떨어짐
시간복잡도: 0(n^2)

 

과정

(오름차순으로 정렬한다고 가정)

1. 주어진 리스트에서 최솟값을 찾음

2. 최솟값을 맨 처음 위치한 값과 swap

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 반복함

 

 

그림으로 쉽게 이해하기

 

<JAVA>

public class A01_selection_sort {
	public static void main(String[] args) {
		int[] a = {5,9,2,4,15,6,1,20,3,10,14,0}; //임의로 넣음!
		//루프를 돌면서 최솟값을 찾고 기준이 되는 지점과 swap
	
		for(int i=0; i<a.length-1; i++) {  //여기에 a.length-1해줘야하는거 유의
			int min = i; //최소값 초기화
			
			for(int j=i; j<a.length; j++) {
				if(a[min]>a[j])
					min = j;
				//만약 min보다 작은 a[j]번째 원소가 있으면 min을 업데이트
				//j번째 인덱스에 최소값이 있는거라 j를 min에 대입시켰다.
				//루프를 한번 돌때 나온 min이 현재 루프에서의 최소값
			}
			//위 루프가 끝나면 최솟값 추출이 끝난것이므로 swap시킴
			
			int temp = a[i];//i번째 원소를 temp에 저장
			a[i] = a[min];
			a[min] = temp;
			//swap완료
			
		}
		for(int i=0; i<a.length; i++) {
			System.out.print(a[i]+" ");
		}
	}
}

 

<Python>

a = [5, 9, 2, 4, 15, 6, 1, 20, 3, 10, 14, 0]    # a를 임의로 정의

for i in range(0, len(a)-1):  # 첫번째 루프
    min_index = i  # i번째 인덱스
    for j in range(i, len(a)):
        if a[min_index] > a[j]:
            min_index = j  # min 업데이트
    # 루프 끝나면 swap 시켜줘야함
    temp = a[i]
    a[i] = a[min_index]
    a[min_index] = temp

print(a)