정렬 공부를 하면서 얻은 모든것을 정리한다.
정렬(sorting)이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
정렬을 배워야만 다음 장의 이진탐색을 진행할 수 있기 때문에 정렬에 대한 정리를 하려고 한다.
0. 들어가기전에
정렬을 배우기 전에 알아둬야 할 코드는 스와프 코드가 있다.
다른언어(특히 c언어)는 구조적인 특성상 두 변수의 위치를 스왑하려면 별도의 함수가 필요하다.
하지만, 파이썬에서는 아주 간단하게 스왑을 할 수 있다.
///C언어에서 구현한 스왑 함수
include <stdio.h>
void Swap(int &a,int &b){
int temp = *a;
*a = *b;
*b = temp;
}
int main(){
x = 1;
y = 2;
Swap(1,2);
printf("%d, %d",x,y);
return 0;
}#파이썬에서 구현한 스왑함수
x,y = 1,2
x,y = y,x
print(x,y)
한눈에 보기에도 확연한 차이가 있다.
1. 선택정렬
선택정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는것이다.
가장 원시적인 방법으로, 매번 '가장 작은 것을 선택'한다는 의미에서 선택정렬 알고리즘이라고 한다.
array = [7,5,9,0,,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)
선택정렬의 시간 복잡도는 Nx(N-1)/2의 연산을 진행해 O(N^2)의 시간 복잡도를 가진다.
2. 삽입정렬
선택정렬은 알고리즘 문제풀이에 사용하기에는 느린 편이다.
삽입정렬은 다음과 같은 생각에 기초해 만들어졌다.
'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?'
삽입정렬은 선택정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다.
특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라고 부른다.
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(array)):
for j in range(i, 0, -1):#인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else:
break # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
print(array)삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지한다는 특징을 가지고 있다.
또한, 삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
시간복잡도는 O(N^2)의 시간 복잡도를 가지는데, 최선의 경우 O(N)의 시간복잡도를 갖는다.
3. 퀵 정렬
가장 많이 사용되는 알고리즘으로 병합정렬과 비슷한 빠르기를 제공한다.
'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자'
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
기준은 피벗이라고 하며, 이번 설명에서는 구역들 중 첫번째 원소를 피벗으로 둔다.
array = [5,7,9,0,3,1,6,2,4,8]
def Quick_Sort(array,start,end):
if start >= end: #데이터가 하나일경우 종료
return
pivot = start
left = start + 1
right = end
while left <= right:
#피봇보다 큰 수를 찾을 때까지 진행
while left <= end and array[left] <= array[pivot]:
left += 1
#피봇보다 작은 수를 찾을 때까지 진행
while right > start and array[right] >= array[pivot]:
right -= 1
if left > right: #인덱스가 엇갈렸다면 작은 데이터와 피봇을 교체
array[right], array[pivot] = array[pivot], array[right]
else: #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
Quick_Sort(array, start, right + 1)
Quick_Sort(array, right - 1, end)
Quick_Sort(array, 0, len(array) - 1)
print(array)
퀵정렬은 O(NlogN)의 시간복잡도를 갖는다. 앞의 두 알고리즘에 비하면 매우 빠른 편이다.
다만, 평균적으로 O(NlogN)의 시간복잡도를 가지지만, 최악의 경우 O(N^2)의 복잡도를 가진다. 데이터가 무작위로 입력되는경우 퀵정렬은 빠르지만, 위의 예제처럼, 가장 왼쪽의 데이터를 피봇으로 삼고, 이미 데이터가 정렬되어있는 경우'는 매우 느리게 동작한다.
4. 계수 정렬
매우 빠른 정렬 알고리즘이다! 하지만 제약조건이 있다.
데이터의 크기 범위가 제한되어 정수형태로 표현할 수 있을때
가장 큰 데이터와 가장 작은 데이터 차이가 1000000(백만)을 넘지 않을 때 효과적이다.
계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에 위와 같은 특징을 가진다.
또한, 비교기반 정렬 알고리즘이 아니다.
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0] * (max(array) + 1) #0까지 세어야 한다.
for i in range(len(array)):
count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 크기 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end = ' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
데이터의 범위만 한정되어 있다면 효율적으로 사용할 수 있으며 항상 빠르게 동작한다.
리스트에 각 데이터가 몇번 등장했는지 그 횟수가 기록되고, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.
때에 따라서 비효율성을 초래할 수 있다. 왜냐면 0과 999999 단 두개의 데이터만 존재한다고 해도 리스트의 크기가 1000000이 되어야 하기 때문이다.
5. 파이썬에서 제공하는 정렬 알고리즘
파이썬은 기본 정렬 라이브러리인 sorted()함수를 제공한다. 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데 병합정렬은 일반적으로 퀵 정렬보다 느리지만 파이썬에서는 병합정렬과 삽입정렬의 아이디어를 더한 하이브리드식 정렬 알고리즘을 따른다.
