정렬이란
정렬이란 데이터를 특정한 기준에 따라서 순서대로 정렬하는 것이다.
우리가 흔히 말하는 버블정렬이나, 퀵정렬, 선택정렬에서 들어본 정렬이
이에 속한다.
데이터를 정렬하면 이진탐색이 가능해진다. 이진탐색을 하기 위해서는 정렬과정이
필수이기 때문이다.
정렬 알고리즘 시각화 사이트
시각화 사이트 이 곳을 클릭하면,
각 정렬 알고리즘이 어떻게 동작하는지 눈으로 확인할 수 있다.
✏️선택정렬
선택정렬은, 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸고
그 다음 작은 데이터를 선택해 두 번째 데이터와 바꾸는 과정을 반복하는 것이다.
7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 | 순으로 있을 때,
0 | 5 | 9 | 7 | 3 | 1 | 6 | 2 | 4 | 8 |
0 | 1 | 9 | 7 | 3 | 5 | 6 | 2 | 4 | 8 |
-- 중략 --
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
이런식으로 앞자리부터 제일 작은 수, 그 다음 제일 작은 수
순서대로 바꿔가는 것이다.
선택정렬 코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for in in range(len(arra)):
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)선택정렬 시간 복잡도
선택 정렬의 시간 복잡도는, 자릿수를 선택하는 for문 안에서, 가장 작은수, 그 다음 작은 수를 찾는 for문이 내장에서 또 돌아간다. 따라서 2중 for문이 돌아가는 형태로
n^2의 연산횟수라고 생각하면 된다.
(책에서는 N + (N - 1) + (N - 2) + --중략-- + 2라서 N X (N + 1)/2의 연산이라고 설명되어 있다.)
따라서 빅오 표현법으로
O(N^2)이다.
선택정렬은 정렬을 배우지 않은 사람도 쓸 수 있을 만큼
가장 기본적이고 간단하지만, 실제 코딩테스트에서는 시간을 많이 잡아먹으니
추후에 나오는 다른 정렬법을 사용하는 것을 추천한다.
해당 포스팅의 개념, 코드, 이미지는 밑 책을 바탕으로 작성되었습니다.
