정렬 알고리즘
정렬 알고리즘은 데이터셋이 주어졌을 때 이를 정해진 순서대로 나열하여 재배치하는 것이다.
이때 불규칙한 데이터들을 정렬 후 탐색해야하는 경우가 있는데 이때 상황에 맞는 알고리즘을 사용하여 효과적으로 문제를 해결하는 것이 중요하다.
대표적인 정렬 알고리즘은 다음과 같다.
1. 선택 정렬 2. 삽입 정렬 3. 버블 정렬 4. 병합 정렬 5. 퀵 정렬
1. 선택 정렬(Selection sort)
선택정렬은 주어진 데이터 중 현재 위치에 맞는 데이터를 찾아 선택하여 위치를 교환하는 알고리즘이다. 한번 순회를 돌면 알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하게 되므로 그 다음 순회부터는 1번 인덱스부터 순회를 돌며 반복한다.
선택정렬은 다음과 같은 순서로 작동한다.
0번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 0번째 인덱스와 swap한다
1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 1번째 인덱스와 swap한다
…
n-1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 n번째 인덱스와 swap한다
선택정렬은 주어진 데이터가 정렬이 되어있던말던 무조건 전체 리스트를 순회해가며 검사하기 때문에 최선의 경우든 최악의 경우든 모두 O(n^2)의 시간복잡도를 가지고 있다.
2. 삽입 정렬(Insertion Sort)
삽입 정렬은 주어진 데이터의 모든 요소를 앞에서부터 차례대로 자신의 위치를 찾아 삽입하는 정렬이다.
삽입 정렬은 다음과 같은 순서로 작동한다.
0번 인덱스는 건너뛴다.
0~1번 인덱스 중 1번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
0~2번 인덱스 중 2번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
…
0~n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
삽입정렬은 최선의 경우 전체 자료를 한번만 순회하면 되기때문에 O(n)의 시간복잡도를 가지지만 최악의 경우 O(n^2)의 시간복잡도를 가진다.
3. 버블정렬(Bubble sort)
버블정렬은 거의 모든 상황에서 최악의 성능을 보여주지만, 이미 정렬된 데이터인 경우에는 1번만 순회하면 되기 때문에 최선의 성능을 보여주는 알고리즘이다. 이미 정렬되어 있는 데이터를 왜 정렬하냐는 의문이 들 수 있지만, 정렬 알고리즘 자체는 데이터가 정렬되어 있는지 아닌지 모르고 작동하는 것이기 때문에 의미는 있다.
버블 정렬은 다음과 같은 순서로 작동한다.
0번째 원소와 1번째 원소를 비교 후 정렬
1번째 원소와 2번째 원소를 비교 후 정렬
…
n-1번째 원소와 n번째 원소를 비교 후 정렬
한번 순회할 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여서 버블정렬이라고 부른다. 원리도 직관적이라서 구현하기 편하긴 하지만 비효율적인 정렬 방식이다.
4. 병합정렬(Merge sort)
병합정렬은 일종의 분할 정복법 중 하나로 큰 문제를 작은 여러 개의 문제로 쪼개서 각각을 해결한 후 결과를 모아서 원래의 문제를 해결하는 방법이다. 병합이라는 이름 그대로 주어진 자료를 잘게 쪼갠 뒤 합치는 과정에서 정렬을 하는 알고리즘이다.
병합 정렬은 다음과 같은 순서로 작동한다.
위에서 설명한 정렬들에 비해서 조금 복잡하므로 예를 들어서 최대한 차근차근 설명해보겠다.
[4, 1, 3, 2]라는 데이터로 예를 들자
우선 length가 1이 될때까지 리스트를 반으로 쪼갠다
[4, 1], [3, 2]가 된다.
[4], [1], [3], [2]가 된다.각 리스트의 길이가 1이 되었으므로 병합을 시작한다.
왼쪽의 0번 인덱스값과 오른쪽의 0번 인덱스 값을 비교하여 적은 값을 먼저 병합
[4]와 [1] 중 1이 더 작으므로 새로운 리스트에 1을 먼저, 그 다음 4를 병합하면
[1, 4] 생성왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[3]과 [2] 중 2가 더 작으므로 새로운 리스트에 2를 먼저, 그 다음 3을 병합하면
[2, 3] 생성이제 새롭게 생성된 [1, 4]와 [2, 3]을 병합한다. 이 새로운 리스트들은 병합 과정에서 정렬되었기 때문에 작은 인덱스일 수록 작은 값을 가진다는 것이 보장되어있다.
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[1] 생성. [4]와 [2, 3]이 남았다
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[1, 2] 생성. [4]와 [3]이 남았다
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[1, 2, 3] 생성. [4]가 남았다
나머지를 병합해준다.[1, 2, 3, 4] 정렬완료
위 과정 중에서 볼드 처리된 왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합 과정이 계속 반복되고 있는 것을 볼 수 있다.
같은 방식으로 계속 반복하여 병합하고 있기 때문에 병합정렬은 보통 재귀> 함수로 구현한다. 또한 병합정렬은 항상 O(nlogn)의 시간복잡도를 가지기 때문에 효율적이다. 그러나 원소의 개수만큼 리스트를 쪼개고 따로 저장하고 있어야하기 때문에 O(n)의 공간복잡도를 가진다. 한마디로 공간복잡도를 어느정도 포기하여 시간복잡도를 얻는 경우이다.
5. 퀵 정렬(Quick sort)
퀵 정렬도 병합 정렬과 마찬가지로 분할정복을 통한 정렬 방법이기 때문에 병합 정렬을 이해하고 내려 왔다면 어렵지 않을 것이다.
병합정렬과의 차이점은 병합정렬은 분할 단계에서는 아무것도 하지않고 병합하는 과정에서 정렬을 수행하지만, 퀵정렬은 분할 단계에서 중요한 작업들을 수행하고 병합시에는 아무것도 하지않는다는 점이다.
퀵 정렬은 다음과 같이 작동한다.
입력된 리스트에서 하나의 원소를 고른다. 이 원소를 피벗이라고 부른다.
피벗을 기준으로 리스트를 둘로 분할한다.
피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮긴다
피벗을 기준으로 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮긴다
