위키에 있는 이미지인데 보면서 뭔가 뿌듯하다
정렬 알고리즘 비교
| 정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
| 선택 정렬 | O(N^2) | O(N) | 아이디어가 간단함 |
| 삽입 정렬 | O(N^2) | O(N) | 데이터가 거의 정렬되어 있을 때 가장 빠름 |
| 퀵 정렬 | O(NlogN) | O(N) | 대부분의 경우 가장 적합함 충분히 빠름 |
| 계수 정렬 | O(N+K) | O(N+K) | 데이터 크기가 한정된 경우에만 사용 가능 매우 빠름 |
알고리즘 코딩테스트를 준비하면서 기본이 되는 정렬 알고리즘을 비교해 보았다.
선택 정렬은 O(N^2)의 시간 복잡도이므로 N이 증가할수록 제곱으로 증가한다
- 장점: 구현이 쉽고, 데이터가 이미 정렬된 경우 빠르게 정렬
- 단점: 입력 데이터가 역순으로 정렬되어 있을 때, 최악의 경우 O(N^2)의 성능
(딱 봐도 실무에선 안쓰일거 같지만.. 구현이 쉽다는 게 매우 큰 장점이다)
로직
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞 데이터와 바꾸는 것을 반복
for문을 돌면서 제일 작은 수를 처리 안된 맨 앞과 바꿈
구현이 쉬운 대신 비효율 적인 건 알겠는데, 왜 이름이 선택 정렬인지는 모르겠으니 그냥 외우자.
구현 (전체 코드)
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)1. 0번째 부터 마지막까지 for문으로 전체를 탐색.
i번째 <=> i번째 이후 최소값
서로 교체를 해줘야 하기 때문에 i를 min_index로 잡고 시작한다
for i in range(len(array)):
min_index = i2. i 번째 이후부터 마지막까지 for문으로 탐색
j번째 요소가 min_index번째 요소보다 작으면 j를 min_index로 변경
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j3. 내부 for문이 끝나서 i번째 탐색을 완료하면
i번째 <=> i번째 이후 최솟값
위치 스왑을 실행
array[i], array[min_index] = array[min_index], array[i]4. 이때 파이썬에서 지원하는 특수한 문법으로 직관적으로 변수 교환이 가능하다.
a = 3
b = 5
print(a,b) # 3 5
a, b = b, a
print(a,b) # 5 3기존에 자바스크립트에서는 temp라는 변수를 따로 선언하여 임시로 저장하여 옮겼지만,
파이썬에서는 이와 같이 직관적이고 간단하게 사용이 가능하다
댓글