정렬에 대한 정말정말 다양한 방법들이 있지만, 오늘은 3가지 정도만 구현해보려고 합니다.
O(N^2)의 대표격인 버블정렬과 O(NlogN)의 대표격인 Merge Sort와 Quick Sort 2개에 대해서 정리해보려고 합니당!
정렬
어렵게 생각하지 않아도 됩니다! 정렬하면 딱 떠오르는 그 행위 그대로입니다. 예를들어, A=[2,5,3,1] 을 A = [1,2,3,5]로 순서를 바꾸는 작업을 우리는 정렬한다고 합니다. 사전적으로 정의를 보면 다음과 같이 안내되어 있습니다.
정렬은 어떤 기준에 맞게 자료들을 나열하는 걸 의미합니다.
여기서 기준이 내림차순,오름차순,사전순 등등이 있을 수 있습니다.
번외) 내림차순, 오름차순
내림차순 오름차순이 은근히 헷갈릴 때가 있습니다. 더불어, DB에 Query를 던질 때 , Descending, Ascending 헷갈릴 때가 있습니다. 저는 2개를 그림으로 외우고 있는데, 헷갈릴 때 이 그림을 떠올리면 어떨까용! 아래로 내려가는건 내림차순(점점 내려가는 순서대로), 오른쪽으로 올라가는건 오름차순(점점 올라가는 순서대로)
버블정렬
버블정렬은 가장 구현이 간단한 방법입니다. 인접한 친구들끼리 비교해가면서 , 정렬을 하는 방법입니다. 인접한 친구끼리 비교했을 때, 크다면 자리를 바꿔주면서 , 가장 큰 원소를 계속 제일 뒤로 보내는 정렬 방법입니다. 아래의 예시에서는 운좋게 1회차 만에 정렬이 되었네용!
코드
#include<bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N;
int arr[100];
int main(){
fastio;
cin>>N;
for(int i=0;i<N;i++){
cin>>arr[i];
}
for(int i=0;i<N;i++){
for(int j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1]);
}
}
return 0;
}
Merge Sort(합병정렬)
합병정렬부터는 조금 난이도가 확 올라가게 됩니다. 합병정렬은 배열을 잘게 나눴다가 다시 합치면서 정렬을 하겠다는 개념입니다.즉, Merge Sort는 2개의 배열을 합쳐줄 때, 정렬이 일어나게 됩니다.
Merge Sort의 알파이자 오메가 - 합치는 과정
예를들어, A=[1,3,5,7] 와 B=[2,4,6] 두 개의 배열이 있을 때, 어떻게 합치면서 정렬 할 수 있을까요? C=[1,2,3,4,5,6,7] 처럼 말이죠! 막상 구현하려고 하면 생각보다 어렵습니다.
두 개의 배열의 원소를 가리키는 Cursor를 두고, 새로운 공간에 집어 넣으면 쉽게 구현할 수 있습니다. 하지만, 이때 커서의 범위를 잘 생각 해주어야 합니다.
- A와 B를 비교해서, 작은 것부터 넣는다고 합시다. 그럼, C =[1,2,3,4,5,6] 지점에서 B의 커서는 더 이상 갈 수가 없습니다. 즉, 이때부터는 무적권 A의 남은 원소를 집어 넣어야합니다. 반대로, B도 똑같습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N, M;
int A[100];
int B[100];
int main()
{
fastio;
cin >> N >> M;
for (int i = 0; i < N; i++)
cin >> A[i];
for (int i = 0; i < M; i++)
cin >> B[i];
int cnt = N + M;
int A_cursor = 0;
int B_cursor = 0;
while (cnt--)
{
if (B_cursor == M)
cout << A[A_cursor++] << " ";
else if (A_cursor == N)
cout << B[B_cursor++] << " ";
else if (A[A_cursor] <= B[B_cursor])
cout << A[A_cursor++] << " ";
else
cout << B[B_cursor++] << " ";
}
return 0;
}이제 이 과정을 나누는 과정 뒤에, 합쳐주는 과정으로 구현해주면 됩니다. 핵심적인 두 과정을 구현하면 아래와 같이 됩니다.
- 배열을 반으로 각각 나눈다
- 각각의 배열을 나누었으면, 합치면서 정렬한다.
void merge(int st,int en){
int mid = (st+en)/2;
int lidx = st;
int ridx = mid;
for(int i=st; i<en;i++){
if(ridx==en) B[i] = A[lidx++];
else if(lidx ==mid) B[i] = A[ridx++];
else if(A[lidx] <= A[ridx]) B[i] = A[lidx++];
else
B[i] = A[ridx++];
}
A에 B배열 반영하기
}
void merge_sort(int st,int en){
//크기가 1
if(en-st==1)
return;
int mid = (st+en)/2;
merge_sort(st,mid);
merge_sort(mid,en);
//나누어 줬으면, 합쳐줘야함.
merge(st,en);
}
위 코드에서 헷갈릴 수 있는 부분이 Merge에서 mid와 ridx인데, ridx에 mid를 넣는 이유는 그림으로 보면 쉽습니다. 나눠지는 배열의 시작점이 각각 st,mid이기 때문에, 그렇습니다.
Quick Sort(퀵 소트, 퀵 정렬, 빠른 정렬(?))
Quick Sort는 메모리의 추가소모를 하지 않고, 내부적으로 정렬을 하는 방법입니다.Quick Sort는 메모리를 추가적으로 소모하지 않기 때문에 , Cache hit rate가 높다고 합니다.(그래서 빠른 정렬인듯)
퀵 소트의 개념은 pivot(기준)이 되는 원소를 하나 선정해서, 그 원소를 기준으로 오른쪽에는 그 원소보다 큰 게 있고, 왼쪽에는 자신보다 작은 게 있도록 하는 자리를 찾아가게 해주는 과정을 반복합니다. 예를들어, A=[1,4,2,3,9,8]이라고 합시다.
- 1이 피봇으로 선택 되었다.
- 1보다 왼쪽에는 1보다 작은 수가 있어야합니다.
- 1보다 오른쪽에는 1보다 큰 수가 있어야합니다.
그러기 위해서, L ,R 두개의 커서를 설정해서 L는 1보다 큰 원소를 찾을 때까지 오른쪽으로 가고
R은 1보다 작은 원소를 찾을 때 까지 왼쪽으로 갑니다.(그래야,오른쪽에는 1보다 큰 게, 왼쪽에는 1보다 작은게 옵니다). 그리고, 해당 L에 있는 원소와 R에 있는 원소의 자리를 바꿔줍니다.
1인 경우에는, R이 L을 Cross하므로 1은 현재 있는 위치가 자기 위치가 맞습니다. 여기서, 마지막에 R커서와 자리를 바꿔야하는 점을 헷갈리기 쉬운데, R과 pivot의 자리를 바꿔야 합니다. 그리고, 다음 pivot을 선택하면 됩니다.
void quick_sort(int st, int en)
{
if (en <= st + 1)
return;
int pivot = arr[st];
int l = st + 1;
int r = en - 1;
while (true)
{
while (l <= r && arr[l] <= pivot)
l++;
while (l <= r && arr[r] > pivot)
r--;
if (l > r)
break;
swap(arr[l], arr[r]);
}
swap(arr[st], arr[r]);
quick_sort(st, r);
quick_sort(r + 1, en);
}
