알고리즘 / 선택 정렬

학습 도서

이것이 코딩테스트다 with 파이썬 (한빛미디어, 나동빈 저)

 

 

정렬(Sorting)

 

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

- 예시 : 오름차순, 내림차순

- 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 

 

선택 정렬(Selection Sort)

 

- 컨셉 : 매 번 가장 작은 것을 선택해서 맨 앞에 놓는다.

- 알고리즘

 1) 가장 작은 데이터를 선택한다.

 2) 맨 앞에 있는 데이터와 바꾼다.

 3) 남은 데이터 중에서 가장 작은 데이터를 선택한다.

 4) 맨 앞에서 두 번째에 있는 데이터와 바꾼다.

 ...

 

 

전체 소스 코드

array = [ 7,5,9,0,3,1,6,2,4,8 ]

for i in range(len(array)):
	min_index = i
    for j in range(i+1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i]
    
    
print(array)

 

 

해설

 

코드를 차근차근 살펴보자.

 

array = [ 7,5,9,0,3,1,6,2,4,8 ]

- Goal : 위의 데이터들을 오름차순으로 나열하자.

 

for i in range(len(array)):
	min_index = i

- len(array) = 9 (array 리스트의 길이)

- range(len(array)) = [0,1,2,3,4,...,9]

  0에서부터 9까지의 정수가 담긴 리스트 생성

  헷갈린다면 아래 포스팅 참고

  1y9u9j2in.tistory.com/152?category=910442

- for 구문에서 리스트의 원소가 차례대로 i 값이 된다. 

- i 는 0부터 시작한다.

- 우선은 i를 제일 작은 변수를 담고 있는 인덱스(min_index)라고 하자.

  (다시 말해 첫 번째 인덱스 값이 가장 작다고 가정하는 것이다.)

 

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

 

- for 구문 안에 있는 for 구문을 보자.

- 여기서 j 가 담긴 리스트는 [1, 2, 3,..., 8, 9]

- j 는 1부터 시작한다.

- 만약에 array[0] > array[1] 이라면 min_index = 1이된다.

  array[0] = 7

  array[1] = 5

  따라서, min_index = 1

- 위의 로직을 j = 2, 3, ..., 9까지 실행해본다.

- 해당 루프가 끝났을 때 min_index 는 '0'을 담고 있는 인덱스 '3'이 될 것이다.

  min_index = 3

 

    array[i], array[min_index] = array[min_index], array[i]

- 각 자리의 값을 서로 바꿔주는 구문

- array [0], array[3] = array[3], array[0]

- array [0] = 0, array [3] = 7

- array = [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]

 

여기까지 i = 0 일때 실행한 결과, 제일 작은 값이 리스트의 첫 번째 자리에 왔다.

다음으로 i =1, i= 2, ..i = 9까지 실행하면 다음으로 작은 값들이 순서대로 맨 앞 자리에 오게 된다.

 

i = 1, array = [0, 1, 9, 7, 3, 5, 6, 2, 4, 8]

i = 2, array = [0, 1, 2, 7, 3, 5, 6, 9, 4, 8]

i = 3, array = [0, 1, 2, 3, 7, 5, 6, 9, 4, 8]

i = 4, array = [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]

i = 5, array = [0 ,1, 2, 3, 4, 5, 6, 9, 7, 8]

i = 6, array = [0, 1, 2, 3, 4, 5, 6, 9, 7, 8]

i = 7, array = [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]

i = 8, array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

i = 9, array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

print(array)

결과를 출력하면 아래와 같이 오름차순으로 정리된 리스트가 출력된다.