정렬이라 하면 보통 엑셀이나 워드에서 사용하는 오름차순 내림차순 정렬 이런것들을 생각할것이다. 위대한 선배 프로그래머들이 미리 만들어두었기에 쓸때는 아무생각없이 사용했고 이게 얼마나 대단한 기능인지 잘 몰랐지만, 알고리즘을 배우고 직접 구현해보면 얼마나 어려운 작업인지 알 수 있을것이다.
사실 정렬을 구현하는것 자체는 굉장히 쉽다. bubble sort, insertion 같은 정렬을 사용하면 구현도 쉽고 그다지 어렵지 않게 할 수 있다. 하지만 시간복잡도를 보면 이렇게 하면 안되겠구나 알 수 있다.
물론 학생인 내가 다루는 데이터는 무슨 정렬을 써도 시간이 비슷하게 나와서 크게 문제를 못느끼지만
n log n 정렬과 n^2 정렬을 가지고 10억개의 데이터를 정렬한다고 생각하면 뭐가 정답인지 알 것이라 생각한다.
이렇게 중요한 정렬이지만 자꾸 까먹거나 구현방법을 잊어버린다는게 참 큰일이다. 그래서 한 번 정리해두기로 하였다.
시작하기전에...
-
실제로 정렬은 여기 적혀있는것보다 많은 종류가 있다. bogo sorting 이라는 가챠같은 정렬또한 존재한다.
-
다만 여기서는 학부에서 배운 정렬 알고리즘 그리고 파이썬, 자바에서 내장함수로 사용한다는 tim sorting에 대해 알아보려 한다.
-
우선 구현이 간단한 정렬부터 알아본 후 다음글에서 merge sorting 같은 어렵지만 시간복잡도가 좋은 정렬들에 대해 알아보려 한다.
Selection Sorting
선택 정렬이라고 부르는 정렬방식이다.
리스트에 숫자가 있다면 앞에서부터 하나를 고르고 리스트 뒤의 숫자들과 모두 비교하면서 더 크다면 둘의 위치를 바꿔주는 정렬방식이다.
- 장점 : 이해가 쉽다. 구현이 쉽다.
- 단점 : 비효율적이다 (O(n^2)의 시간복잡도를 가진다)
파이썬 코드
def selection(n): for i in range(len(n)): tmp = i for j in range(i + 1, len(n)): if (n[tmp] >= n[j]): tmp = j n[i], n[tmp] = n[tmp], n[i] return n
자바 코드
public static int[] Selection(int [] line) { int len = line.length; for (int i = 0; i < len; i++) { int tmp = i; for (int j = i+1; j < len; j++) { if (line[tmp] >= line[j]) { tmp = j; } } int temp = line[tmp]; line[tmp] = line[i]; line[i] = temp; } return line; }
자바는 내장된 swap 기능이 따로 없고 객체지향언어라서 단순히 swap 함수를 구현한다고 작동하지도 않는다. 이와 관련된 글을 구글에 검색하면 많이 나오니깐 한번 쯤 읽어보면 좋다고 생각한다.
Insertion Sorting
삽입 정렬이라고 부르는 정렬방식이다.
선택정렬과 비슷해보이지만 좀 다르다. 하나의 값을 선택하고 그 값을 다른값과 비교해가면서 있어야하는 자리, 즉 앞에 값은 자기보다 뒤에 값은 자기보다 큰 그 자리에 있게 만드는 정렬이다. 리스트를 한번 반복하면 끝나게 된다.
- 장점 : 선택정렬 대비 좋은 효율을 가지고 있다. (O(n)의 시간복잡도를 가진다). 대부분 정렬되어 있는 상황에서 높은 효율을 가진다.
- 단점 : 만약 데이터의 수가 많다면 O(n)의 시간복잡도는 너무 많은 시간을 소비하게 된다
파이썬코드
def insertion(n): for i in range(1, len(n)): j = i-1 nxt_ele = n[i] while (n[j]> nxt_ele) and (j >= 0): n[j+1]= n[j] j = j - 1 n[j+1] = nxt_ele return n
자바코드
public static int[] Insertion(int [] line) { int len = line.length; for (int i = 1; i < len; i++) { int j = i -1; int nxt_ele = line[i]; while (line[j] > nxt_ele && j >= 0) { line[j+1] = line[j]; //line[i] = line[j] (the one before i) j = j - 1; } line[j+1]= nxt_ele; } return line; }
두 코드 모두 특이한점은 0번 원소, 즉 첫번째 원소가 아니라 1번 원소, 두번째 원소부터 시작했다는 점이다. 만약 첫번째 원소를 고르면 이전값과 비교가 불가능해 코드가 복잡해 질 것이다.
Bubble Sorting
거품 정렬이라고 부르는 정렬방식이다.
거품이라하니깐 어감이 그다지 좋지 않은데 사실 원소의 이동이 거품이 떠오르는것 같다고 해서 지어진 이름이라고 한다. 두 원소를 비교해서 작은값을 앞으로 보내는 방식을 계속 반복해서 끝까지 가면 끝나게 된다. 이 정렬을 양방향으로 수행하면 칵테일 정렬이 된다.
-
장점 : 직관적이며 구현이 쉬워서 느린 코드에도 불구하고 많이 사용되고 있다.
-
단점 : O(n^2)의 시간복잡도로 매우 느리다.
-
특이하게도 bubble sorting 은 단순한 구현과 약간의 변형으로 성능이 개선된 enhanced bubble sorting 두가지가 존재한다.
def bubble(n): for i in range(len(n)-1,0,-1): for idx in range(i): if n[idx] > n[idx+1]: n[idx], n[idx+1] = n[idx+1], n[idx] return n
def improved_bubble(n): for i in range(len(n)-1,0,-1): sorted = True for idx in range(i): if n[idx] > n[idx+1]: n[idx], n[idx+1] = n[idx+1], n[idx] sorted = False if (sorted): break return n
public static int[] Bubble(int [] line) { int len = line.length; for (int i = len-1; i > 0; i--) { for (int j = 0; j < i; j++) { if (line[j] > line[j+1]) { int tmp = line[j+1]; line[j+1] = line[j]; line[j] = tmp; } } } return line; }
public static int[] Imp_Bubble(int [] line) { int len = line.length; for (int i = len-1; i > 0; i--) { Boolean TF = True; for (int j = 0; j < i; j++) { if (line[j] > line[j+1]) { int tmp = line[j+1]; line[j+1] = line[j]; line[j] = tmp; TF = False; } } if (TF == True) { break; } } return line; }
단순한 구현에서는 정렬되어 있는지 여부와 관계없이 무조건 끝까지 정리하고 함수를 종료했다.
하지만 개선된 방식에서는 boolean을 추가 끝까지 검사를 하고 만약 이미 정렬이 되어 있다면
break를 통해 함수를 끝내도록 되어있다.
물론 이게 큰 차이를 만들지는 않겠지만 스트라센 알고리즘처럼 이러한 작은 차이가 큰수에서는 유의미한 결과로 이어질지도 모르는 일이다.
이번 글에서는 간단한 정렬 3가지를 알아보았다. 이들은 모두 O(n) 과 같거나 큰 시간복잡도를 가지고 있어 빠른 코드라고는 할 수 없지만 구현이 쉽고 단순하여 실무 현장에서 자주 쓰인다고 한다. (글쓴이가 실무자가 아니라서 정확하지 않은 정보이다). 정렬의 기본 개념을 이해할 수 있고 기초가 되는 방식들이기에 잘 알아두면 좋다고 생각한다.
유튜브에 가서 영어로 정렬이름을 검색해보면 정렬을 시각화해둔 영상들이 굉장히 많다. 처음에는 이게 정렬을 이해하는데 도움이 많이 될수도 있다.
