선택정렬, 삽입정렬
#코딩테스트 #선택정렬 #삽입정렬 #알고리즘
정렬Sorting**이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 **이진탐색(Binary Search)가 가능해진다. 따라서 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 정렬 알고리즘은 굉장히 다양한데, 먼저 선택정렬과 삽입정렬을 설명하겠다.
설명에 앞서, 정렬은 모두 오름차순 정렬을 수행하겠다. 내림차순 정렬은 오름차순 정렬에서 크기 비교를 반대로 수행하면 되고, 혹은 오름차순 정렬된 리스트를 O(N)의 복잡도로 간단히 뒤집거나 파이썬의 경우 특정한 리스트의 원소를 뒤집는 기본 메서드를 쓰면 된다.
선택정렬은 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬Selectioin Sort 알고리즘이라고 한다. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그렇게 채운 맨 앞의 데이터는 고정한다. 고정한 데이터 외의 정렬해야하는 데이터 중에서 또 다시 작은 데이터를 선택해서 맨 앞의 것과 바꾸는 과정을 반복한다. 데이터의 개수가 N개 있을 때, 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
# Python code
# 선택 정렬
array = [5, 2, 1, 6, 3, 4, 9, 7, 8, 0]
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) #->[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
선택 정렬은 N-1번 동안 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 이 N-1번 동안 매번 가장 작은 수를 찾기 위한 비교연산을 한다. 따라서 총 연산횟수는 N + (N-1) + (N-2) + … + 2 로 볼 수 있다. 따라서 근사치로 N(N+1)/2번의 연산을 수행한다고 볼 수 있고, 빅오 표기법으로는 간단히 O(N2)이다. 직관적으로 이해하자면 이중for문이 들어가기 때문에 그렇다. 선택 정렬은 데이터긔 개수가 10,000개 이상이면 급격히 느려지는 매우 비효율적인 정렬알고리즘이다. 그러나 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택정렬 소스코드를 자주 작성해서 익숙해야 한다고 한다.
삽입정렬Insertion Sort은 '데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입'하는 알고리즘이다. 삽입정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다. 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다. 삽입정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다. 특정한 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 이 과정을 N-1번 반복하게 된다.
1
2
3
4
5
6
7
8
# Python code
# 삽입 정렬
array = [5, 2, 1, 6, 3, 4, 9, 7, 8, 0]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입정렬의 시간 복잡도도 O(N2)인데, 선택정렬과 마찬가지로 반복문이 2번 중첩되었다. 다만, 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 따라서 최선의 경우는 O(N)의 시간 복잡도를 가진다.
이 글의 내용이 많은 도움이 된다면 아래 책을 사서 읽어보고 공부하는 것을 추천한다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
1
2
3
4
5
6
저자
나동빈
출판
한빛미디어
발매
2020.08.05.