: 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
EX) 0-9까지 10장의 숫자카드 순서대로 정렬하기
default 숫자카드
전체 데이터 중 가장 작은 '0'을 선택하여 맨 앞의 데이터 '7'과 자리를 바꾼다.
'7'과 자리를 바꾼 '0'을 제외한 나머지 데이터 중에서, 가장 작은 '1'을 선택하여 맨 앞 데이터인 '5'와 자리를 바꾼다.
마찬가지로 이미 정렬이 끝난 '0'과 '1'을 제외한 나머지 데이터 중에서, 가장 작은 '2'를 맨 앞 데이터인 '9'와 자리를 바꾼다.
이를 파이썬으로 구현해보면,
cards= [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(cards)):
min= i
for j in range(i+1,len(cards)):
if cards[min] > cards[j]:
min= j
cards[i], cards[min]= cards[min], cards[i]
이에 대한 시간 복잡도를 계산해보자.
선택정렬은 N개의 요소가 있는 리스트가 있을 때, N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2 가 되고 이는 ( N^2 + N - 2 ) / 2 로 표현할 수 있는데, 빅오 표기법에 따라서 O(N^2)라고 작성한다. (계수를 제외한 차수가 높은 항으로 따진다)
> 왜 꼭 위치를 바꿔야 하지?
삽입 정렬
: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
선택 정렬에 비해 구현난이도가 높지만, 더 효율적으로 동작한다.
앞의 예시로 다시 보면,
첫번째 숫자를 기준으로 두번째 숫자부터 바꿀지 말지 결정했던 선택정렬과 유사하게,
첫번째 숫자를 기준으로 두번째 숫자부터 어디에 들어가야 할지를 결정한다고 보면 된다.
두번째 숫자인 '5'가 기준이 되는 첫번째 숫자 '7'의 왼쪽에 올 것인가 오른쪽에 올 것인가 > 작으므로 왼쪽
다음 숫자인 '9'가 바로 앞의 '7'과 비교했을 때 크므로 오른쪽에 온다
다음 숫자인 '0'은 바로 앞의 '9'보다 작으므로 '9'의 왼쪽, 그 앞의 '7'보다 작으므로 '7'의 왼쪽, 그 앞의 '5'보다 작으므로 '5'의 왼쪽으로 오게 된다.
이러한 과정을 반복하면 0부터 9까지의 숫자 정렬이 완성된다.
이를 파이썬으로 구현해보면,
cards= [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(cards)):
for _ in range(i):
if cards[i-1] > cards[i]:
cards[i-1], cards[i]= cards[i], cards[i-1]
i-= 1
else:
break
print(cards)
이에 대한 시간복잡도 또한 이중 반복문이기 때문에 O(N^2)이 된다. 삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 예를 들어, 0부터 9까지의 숫자가 이미 정렬되어 있는 상태라면 상수시간 복잡도를 따르기 때문에(?) O(N)의 시간복잡도를 가진다.
퀵 정렬
: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
일반적으로 데이터의 특성과 관련없이 사용할 수 있는 정렬 알고리즘이기도 하다.
병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. (자바, c언어, 파이썬)
가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot) 로 설정한다.
앞선 숫자카드 예시로 보면,
첫번째 데이터인 '5'가 기준데이터(Pivot)이 되고, 나머지 데이터에서 왼쪽부터는 pivot보다 큰 값을, 오른쪽부터는 pivot보다 작은 값을 찾는다. 그러면 왼쪽부터 찾은 큰 값은 '7'이 되고, 오른쪽부터 찾은 작은 값은 '4'가 된다. 이때 이 두 숫자의 위치를 바꾼다.
그럼 위와 같이 바뀌게 되고, 계속해서 이어가면 왼쪽에서부터 찾은 큰 값은 '9', 오른쪽에서 찾은 작은 값은 '2' 가 된다.
그럼 '2' 와 '9'의 위치를 바꾸면 된다.
그 다음으로 이어가서 왼쪽에서부터 'pivot'보다 큰값을 찾으면 '6'이 되고, 오른쪽에서부터 'pivot'보다 작은 값을 찾게 되면 '1'이 된다.
그러나 이처럼 위치가 엇갈려지게 되는 경우에는 선택된 값 중 'pivot'보다 작은 값과 'pivot'데이터의 위치를 바꾼다.
5보다 작은 값 - 5 - 5보다 큰 값
그럼 위 그림과 같이 되는데, 이렇게 'pivot'을 기준으로 데이터 묶음을 나누는 작업을 분할이라고 한다.
그럼 이 두 개의 분할마다 다시 각각 정렬을 수행한다. 5보다 작은 데이터끼리, 5보다 큰 데이터끼리 정렬을 수행한다.
만약 위 예시와 같이 첫번째 피봇(pivot)이 가운데 크기의 숫자라면 분할이 절반씩 일어나 전체 연산 횟수로 O(NlogN)을 기대할 수 있다. 그래서 위 그림과 같이 재귀함수의 동작처럼 사용할 수 있다.
그러나 이미 잘 정렬된 데이터라면, 오히려 O(N^2)의 시간 복잡도를 가지게 되어 큰 값을 가지게 된다.
표준 라이브러리를 사용하면 시간복잡도가 NlogN의 값으로 보장된다.
알고리즘 구현 방식을 그대로 코드화한 결과훨씬 간단한 파이썬 코드
> 약간 이게 되네..? 이런느낌의 코드다,,
계수정렬
: 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용가능하다.
위에서 예시로 봤던 데이터와 약간 다르게 15개의 값으로 이루어진 데이터를 사용하였다.
정렬할 데이터를 앞에서부터 해당하는 인덱스의 개수 +1을 해준다.
결과
그럼 다음과 같이 인덱스에 따른 개수를 구할 수가 있게 되고, 이를 첫번째 데이터부터 하나씩 그 개수만큼 반복하여 출력한다.
그러면 다음과 같은 출력결과를 만들 수 있다.
즉, 계수정렬은 각각의 데이터가 몇번 등장했는지 count하는 방식으로 정렬한다.
따라서 정수형의 데이터만 가질 수 있으며, 반복적으로 사용되는 정수가 있을 때 유리하게 사용할 수 있다.
그러나 데이터가 만약 0과 999,999 단 2개만 존재하는 경우에는 100만개의 공간이 필요하게 되고, 이는 심각한 비효율성을 초래할 수 있다.
이를 파이썬으로 구현하면,
cards= [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 20, 20]
count_lst= [0] * (max(cards) + 1)
for card in cards:
count_lst[card] += 1
for i in range(len(count_lst)):
for _ in range(count_lst[i]):
print(i, end= ' ')
> 이 경우에도 0부터 9까지의 인덱스에 해당하는 count_lst는 값이 채워지지만, 10부터 19까지는 채워지지 않은 채 0으로 되어있을 것이다. 이처럼 공간의 비효율성이 생길 수 있다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때, 최악의 경우에도 시간복잡도 O(N+K)를 보장한다. 첫번째 반복문에서 N번, 두번째 이중 반복문에서 (K+N)이므로 전체 시간복잡도는 O(N+K)가 된다.
