[알고리즘] 선택 정렬 정리

선택 정렬(Selection Sort)은 주어진 List  맨 앞의 인덱스를 기준값으로 하여 최소값을 찾아 순회하며 비교, 교체를 하는 방식이다. 이 과정을 한번 실행 하면 맨 앞의 인덱스 값을 앞으로 옮겨 순회를 하면서 비교, 교체를 반복하게 된다.

시간복잡도는 O(n^2)

 

예시:

[90,27,22,28,20,18] 정렬되지 않은 데이터가 있다.

선택 정렬을 하여 정렬을 하면 아래와 같다.

 

먼저 기준점이 되는 인덱스는 맨 앞의 0번째 인덱스로 하여 순회를 한다.

기준점의 값은 90이고 최소값 18과 자리를 교체 한다.

[90, 27, 22, 28, 20, 18]

과정 1 [18, 27, 22, 28, 20, 90]

 

인덱스에 +1을 하여 1번째 인덱스로 하여 또 순회를 한다. 기준점의 값은 27이고 최소값은 20

[90, 27, 22, 28, 20, 18]

과정 1 [18, 27, 22, 28, 20, 90]

과정 2 [18, 20, 22, 28, 27, 90]

 

이와같이 기준이되는 인덱스를 +1씩하여 최소값을 찾으면 자리를 바꿔주면 오름차순으로 정렬 되게 된다.

 

정렬 과정:

[90, 27, 22, 28, 20, 18]
[18, 27, 22, 28, 20, 90]
[18, 20, 22, 28, 27, 90]
[18, 20, 22, 28, 22, 90]
[18, 20, 22, 22, 28, 90]
[18, 20, 22, 22, 28, 90]
[18, 20, 22, 22, 90, 90]

 

python 코드 참고:

 

#랜덤 리스트 생성
data_list = random.sample(range(100), 10)

def selection(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[stand] > data[index]:
                lowest = index
                data[stand], data[lowest] = data[lowest], data[stand]
    return data
print(selection(data_list))