버블정렬에 이어 선택정렬에 대해 알아보자.
이번에도 역시 코드를 직접 보지 않고 개념을 먼저 익혀봤다.
선택정렬이 구현되는 원리를 그림으로 묘사한 것을 보고 일단 스스로 구현해보는 접근법이다.
구현 후,
예제 코드를 확인했고 거기엔 아주 사소한 차이지만
엄청난 차이를 불러온 부분이 있었으니......
1. 선택정렬이란?
시간복잡도(빅 오) 표기법에 의하면, 두 정렬의 시간복잡도는 같다.
하지만 '빅 오'로는 판별해낼 수 없는 곳에서 효율성이 판가름 된다.
선택정렬 원리 (오름차순 정렬)
1) 배열의 첫번째 원소를 기준(시작)으로, 다음 인덱스의 값과 대소비교를 한다.
2) 다음 인덱스의 값이 더 작다면, '일단' 그 인덱스 값을 기억해 둔다.(현재 최소값)
3) 이제, 좀전에 기억해둔 최소값과 그 다음 배열 값을 다시 비교한다.
4) 반복문의 첫 번째 루프가 완료되면, 그 최소값과 배열의 첫번째 값을 교환한다.
5) 다시 1) ~4) 반복 (배열의 두번째 원소를 기준으로, 배열의 세번째 원소를 기준으로 -> 쭉쭉)
2. 혼자 작성해 본 선택정렬 코드(오류 발견 이전)
# 선택정렬 구현해보기
def selective_sort(list):
length = len(list) # 리스트 길이
for i in range(length):
if i == length - 1:
break
for j in range(i+1, length):
if list[i] < list[j]:
continue
else:
temp = list[i]
list[i] = list[j]
list[j] = temp
list = [4, 5, 8, 1 , 7, 2, 5, 5, 3, 0 ,-1]
selective_sort(list)
print(list)결과
결과가 잘 나왔기에, 정말 제대로 구현된 줄 알았다.
하지만, 엄청난 착각이었다ㅎㅎㅎㅎ
3. 선택정렬 코드 수정
# 선택정렬 수정
def selective_sort(list):
length = len(list)
for i in range(length): # 0, 1, 2, 3
minimal_index = i
for j in range(i+1, length):
if list[minimal_index] > list[j]:
minimal_index = j
list[i], list[minimal_index] = list[minimal_index], list[i]
if i == j:
break
list = [4, 5, 8, 1 , 7, 2, 5, 5, 3, 0 ,-1]
selective_sort(list)
print(list)결과
4. 코드 리뷰
결론부터 말하자면, 배열값의 '교환' 부분을 수정한 것이다.
1. '비교' 횟수는 시그마 (n-1)로써, 버블정렬과 선택정렬 모두 동일하다.
2. 둘 다 이중 loop(nested loop)구조다.
3. '교환' 횟수가 다르다.
- [1] 버블정렬(시그마(N-1))
- [2] 선택정렬(약 N/2)
[1] 버블정렬은 '대소비교'와
그에따른 데이터 교환이 '매번' 이뤄진다.
즉, 대소 비교를 할때마다 교환이 일어난다는 것이다.
[2] 선택정렬은 '대소비교'를 진행하며 최솟값만 저장해둔다.
한 텀의 loop가 끝날때!
그제서야 교환을 진행한다.
아래와 같이 잘못된 코드를 보면,
for i in range(length): if i == length - 1: break # 아래 반복문과 같이, 대소 비교할 때마다 값을 '교환'하고 있었다. for j in range(i+1, length): if list[i] < list[j]: continue else: temp = list[i] list[i] = list[j] list[j] = tempelse:
부분에서 값의 '교환'이 이루어 지고 있다. 그것도 '비교'를 할 때마다....
껍질은 선택정렬의 모습을 하고 있으나, 속은 완전 버블정렬인 녀석이다.
이번엔, 수정된 코드를 다시 살펴보자.
for i in range(length): # 0, 1, 2, 3
minimal_index = i
# 이중 loop인건 동일하다
# 아래 loop에서는 '비교'만 하고 있고,
# 한 텀의 비교가 끝난 이후에야 for문 밖에서
# 데이터 교환 1회가 진행되고 있다.
for j in range(i+1, length):
if list[minimal_index] > list[j]:
minimal_index = j
list[i], list[minimal_index] = list[minimal_index], list[i]보다시피, 선택정렬이 버블정렬보다 '교환'을 하는 단계가 적은 것이 확실하고
그렇기에 더 효율적인 알고리즘이다.
마지막으로, 배열의 값을 좀 더 넣은 다음 Run을 해보자.
# 다음의 배열을 '선택정렬'을 사용해서 오름차순으로 정리해보자.
list = [4, 5, 8, 1 ,199, 20000,3432, 23446, 2001, 1992, 3, 233, 50000, 342, 123, 234, 321, 111, 7, 2, 5, 5, 3, 0 ,-1]
selective_sort(list)
print(list)결과
1. 구현하려는 프로그램의 의도(목적 : 오름차순 정렬)
2. 자료구조와 알고리즘을 정하고(방법 : '배열의 선택정렬')
-> 1, 2를 통해 결과가 잘 나오는 모습을 보며
가슴 벅찬 감정을 느낀다ㅎㅎㅎㅎㅎㅎㅎ
- One step at a time - 