선택정렬

정렬

데이터를 특정 기준에 따라 순서대로 나열하는 것

선택 정렬

검색 대상 배열에서 가장 작은 데이터를 선택해 맨 앞의 원소와 바꾸기

여기서 핵심은, 매번 가장 작은 것을 선택하는것

정렬 과정

1. 입력된 배열을 쭉 돌면서
2. 현재 원소 뒤의 원소들 중 가장 작은 원소를 찾아
3. 현재 원소와 가장 작은 원소의 위치 교환

for i in range(len(arr)):
	min_idx = i
    for j in range(i+1, len(arr)):
    	if arr[min_idx] > arr[j]:
        	min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

예시

1. 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로 전체 중에서 가장 작은 데이터를 선택합니다.
   맨 앞 3 <-> 가장 작은 0

2. 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 1을 선택해 처리되지 않은 데이터 중 가장 앞에 있는 데이터 4와 바꿉니다.
   두번째 4 <-> 두번째로 작은 1
   

3. 정렬된 데이터 제외하고 이후 데이터 중에서 가장 작은 데이터인 2를 선택해 처리되지 않은 데이터 중 가장 앞의 데이터 4와 바꿉니다.
   세번째 4 <-> 세번째로 작은 2
   

4. 마지막까지 이와 같은 방식으로 반복합니다.
   

완료!

시간 복잡도

N-1번 만큼 가장 작은 수를 찾기 + 매번 가장 작은 수 찾기 위한 배교 연산
=> N + (N-1) + (N-2) + ... + 2
= N(N+1)/2
-> O(N^2)

장단점

장점

• 구현이 간단하고 이해하기 쉽습니다.
• 작은 배열에서는 다른 복잡한 정렬 알고리즘보다 빠를 수 있습니다.
• 원소의 이동 횟수가 비교적 적기 때문에 데이터가 많이 이동해야 하는 경우에는 다른 알고리즘(ex 삽입정렬)보다 효율적입니다.

단점

• 최악의 경우에는 O(n^2)의 시간 복잡도를 가지며, 배열의 크기가 커질수록 다른 효율적인 알고리즘보다 느립니다.
• 안정성을 보장하지 않습니다. 즉, 동일한 값이 여러 개 있는 경우, 이 값들의 순서가 바뀔 수 있습니다.
• 불필요한 비교가 많아서 데이터 비교 횟수가 많아지기 때문에, 정렬이 불필요하게 길어질 수 있습니다.