선택 정렬

선택 정렬은 현재의 값과 최솟값을 비교하고 교환한다. 버블정렬은 값을 하나씩 이동하며 올바른 순서로 맞췄지만, 선택은 인덱스를 통해 멀리 있는 값과도 교환할 수 있어 이동이 적다.

소스코드

import random 

arr2 = random.sample(range(0,100),40)
step = 0

for i in range(len(arr2)) : 
    min_idx = i
    for j in range(i+1,len(arr2)) :
        step +=1
        if arr2[j] < arr2[min_idx] :
            min_idx = j
            
    if min_idx != i : 
        arr2[i], arr2[min_idx] = arr2[min_idx], arr2[i]
        step +=1
        
print("list :",arr2, "\n\nstep :", step)

코드 설명

import random 

arr2 = random.sample(range(0,100),40)

random.sample(population, k) : 0부터 99까지의 모집단에서, 40개의 표본을 무작위로 꺼낸다.

for i in range(len(arr2)) : 
    min_idx = i

• 바깥 for 문 : arr2의 개수만큼 반복한다. 현재의 인덱스 i를 min_idx 에 저장하고 안쪽 for문을 실행한다.

​``` for j in range(i+1,len(arr2)) : step +=1 if arr2[j] < arr2[min_idx] : min_idx = j

<br>

- 안쪽 for문 : 그전에 비교했던 인덱스와 현재의 인덱스는 비교할 필요 없다. range(i+1, len(arr2))로 i 인덱스 그 다음부터의 인덱스와 비교한다.
- step : 비교 횟수를 실행 횟수에 추가한다.
- arr2[j] < arr2[min_idx] : 만약 j 인덱스의 값이 min_idx 인덱스의 값보다 작다면, j를 최솟값의 인덱스로 저장한다.
- 안쪽의 for문을 반복하면 최종적인 최솟값의 인덱스가 min_idx에 저장된다.

<br>
<br>

​```
    if min_idx != i : 
        arr2[i], arr2[min_idx] = arr2[min_idx], arr2[i]
        step +=1

• 다시 바깥 for문 : 안쪽 for문을 빠져나온 후, min_idx 가 현재 인덱스와 같은 게 아니라면(즉, 현재 인덱스의 값보다 더 작은 값이 있었다면), 그 값들을 교환해준다.
• step : 교환이 일어나면 교환 횟수를 실행 횟수에 추가한다.

버블 정렬과 비교

최악의 시나리오로 한 건 아니고, 난수로 무작위 배열된 시퀀스를 기준으로 측정했다.

버블 정렬