Data Structure #09 정렬

화승이·2024년 7월 8일

CS공부

목록 보기

9/14

오늘은 정렬에 대해서 알아보려고 한다. 기존에 다뤘던 자료구조들을 활용한 정렬도 있기에 앞부분 포스트를 보고 오면 더 잘 이해할 수 있을 거라고 생각한다.

버블 정렬 (Bubble Sort)

인접한 2개의 데이터를 비교해가면서 정렬을 진행하는 방식

버블 정렬은 위 사진처럼 진행된다. 두 개의 반복문을 사용하고, 붙어있는 2개의 데이터를 비교해가면서 우선순위에 맞게 위치를 변경하고, 이를 (데이터의 수)-1 만큼 반복하면서 제자리를 찾도록 하는 함수이다. 다음은 간단한 알고리즘 구현이다.

for(i = 0;i < n - 1; i++){
	for(j = 0;j < (n - i) - 1; j++)
    	if(arr[j] > arr[j + 1]) ....

윗 코드가 사실 버블 정렬에서 제일 중요한 파트이다. i, j, arr은 이미 다 정의되어있다고 가정하고 진행한다.

버블정렬 시간복잡도

정렬에서 시간복잡도 계산은 크게 2가지를 보고 계산한다. 바로 비교하는 횟수를 보고 시간복잡도를 계산하고, 두 번째는 데이터의 이동 횟수를 계산한다.

비교횟수의 시간복잡도 : 1 + 2 + 3 + ... (n - 2) + (n - 1)
이렇게 나오는 이유는 위 코드에서 i 가 1씩 증가할 때마다 n개의 자료가 있으면, (n - 1)부터 1까지 비교를 해야하는 상황이 나오기 때문이다. 즉, (n^2-n)/2 가 연산을 통해 나오고 이는 빅오로 나타내면 O(N^2)으로 나타낼 수 있다.
데이터 이동횟수의 시간 복잡도 : (데이터가 역순으로 있는 최악의과정을 나타낼 때 비교횟수의 연산과 같은 결과를 가짐) O(N^2)

선택 정렬(Selection Sort)

정렬순서상 가장 앞서는 것을 선택해 가장 왼쪽, 원래 그 자리에 있던 데이터는 빈 자리에 넣는 정렬을 말한다.

위 정렬은 버블 정렬과 다르게 인접한 부분이 아니라, 첫번째를 기준으로 (오름차순 정렬을 하게 된다면) 제일 작은 값, 그 두번째로 작은 값 하나씩 위치를 변경해주면서 고정하면서 나가는 정렬이다. 이 정렬의 코드에서 중요한 부분은 다음과 같다.

for(int i = 0; i < n - 1; i++){
	max = i;
    for(int j = i + 1; j < n; j++){
    	if(arr[j] < arr[max])....

max라는 변수와, arr이라는 배열 변수는 이미 앞에서 정의되어 있다고 가정한다. 최고 값을 설정을 하고, 하나씩 비교하면서 max보다 작은 값이 존재하면 max의 값을 더 더 작은 값으로 바꿔주는 연산을 한다. 그렇게 j의 반복문이 끝나면 나오는 값을 하나씩 arr[i]에 넣어주면서 배열을 마무리해서 채워주면 되는 문제다.

선택정렬 시간복잡도

선택정렬에서의 시간 복잡도는 위 버블정렬과 크게 차이가 없다. 물론, 두 개가 정렬을 하는 방법은 다르지만, 정렬을 구현하는 방법에서 두 정렬 모두 반복문 2개를 활용한다.

비교횟수의 선택정렬 시간복잡도 : O(N^2)

사실, 2가지의 정렬이 차이가 나는 부분은 데이터 이동횟수의 연산이다. 여기서는 이중 반복문 내에서 데이터가 이동하지 않고, max라는 값이 j의 반복문을 통해서 값이 넣어진다면 이를 i라는 바깥쪽 for문에 위치하기 때문에 이는 시간복잡도를 이렇게 나타낼 수 있다.

연산횟수의 선택정렬 시간복잡도 : O(N)

삽입정렬(Insertion Sort)

정렬 대상을 2부분으로 나누어, 정렬 안된 부분의 데이터를 정렬된 부분의 특정 위치에 삽입하는 방식

정렬 대상을 2부분으로 나눈다는 것은, 정렬된 부분과 정렬 안된 부분을 나누어서 정렬 안된 부분은 정렬 대상에서 자리에 맞게 삽입해준다는 의미에서 이름이 삽입정렬이라고 붙고, 그 과정은 위 사진과 같다. 위 삽입정렬의 중요한 코드를 보도록 하겠다.
```
for(int i = 0; i < n; i++){
	for(int j = i - 1;j >= 0; j--){
    	if(arr[j] > insData)
        	arr[j+1] = arr[j];
        else
        	break;
```

삽입정렬 시간복잡도

삽입대상을 잘 활용해야하는 이유는 다음과 같다. 정렬되어 있지 않은 부분을 정렬되어 있는 배열에 삽입하는 배열이기에 정렬 대상이 많을 수록, 위 코드에서의 break문을 빨리 실행시키며 시간복잡도도 굉장힐 줄일 수 있다. 하지만 시간복잡도는 최악의 과정을 계산하는 거고, 이 문제에서 최악의 경우는 break문을 실행시키지 않는 다 배열이 되어있지 않은 상황이다. 이에는 똑같이 반복문을 2개를 사용한다는 점에서 시간복잡도는 O(N^2)로 나타낼 수 있다.

비교횟수, 연산횟수의 시간복잡도 : O(N^2)

위 버블정렬, 선택정렬, 삽입정렬은 2개의 반복문을 사용해 다 O(N^2)이라는 시간복잡도를 가지며 좋은 효율을 보여주는 정렬은 아니었다. 하지만, 데이터의 길이가 작은 경우에는 굉장히 많이 쓰이는 정렬이기에 알아두면 좋다. 다음부터 다룰 정렬은 더 빠를 효율을 보이는 정렬들이다. 물론 어려운 부분들도 있어서 과정을 잘 이해해야한다.

힙 정렬(Heap Sort)

힙 정렬 설명하기에 앞서, 위 사진을 보자. 힙은 앞 포스트에서 우선순위 큐에 대해서 학습할때 다룬 부분이다. 즉, 우선순위를 담고 있기에 오름차순, 내림차순이라는 우선순위에 맞게 힙에 저장하는 것이다. 또한 큐의 특성상 알아서 정렬이 되고, 우선순위에 맞게 데이터를 꺼내올 수 있다. 즉, 힙 정렬에 대한 설명은 단순하지만 다음과 같다.

데이터들을 힙에 넣었따가 다시 빼는 것
(힙은 루트노드가 반환되면서 알아서 정렬이 되기 때문이다.)

힙 정렬 시간복잡도

그러면 사실상 힙 정렬의 시간복잡도는 앞서 다룬 힙의 시간복잡도와 같을 수 밖에 없다. 힙 정렬은 레벨이 한 단계씩 증가할 때마다 연산을 한번씩 더 한다는 특징이 있기에 시간 복잡도는 O(log2n)이였다. 하지만, 정렬 같은 경우는 N개의 데이터를 정렬한다는 점에서 (정렬하는 데이터의 수) X (힙 정렬의 시간 복잡도) 로 표현할 수 있다.

힙 정렬 시간복잡도 : O(Nlog2N)

병합 정렬(Merge Sort)

분할 정복 : 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방식

사실 이 정렬은 그림을 보면서 이해하는 것이 빠르다. 데이터를 분할하여 나눈다는 것은 위 사진처럼 8개의 데이터를 4개 2개 1개로 분할하고, 그 이후에는 정렬을 하면서 2개 4개 8개로 정렬하는 것이다. 이를 보고 데이터가 많아지면 계속 코드를 작성할까봐 걱정할 수도 있는데, 사실 이 정렬은 '재귀'를 활용할 수 있다.

병합 정렬 시간복잡도

-병합정렬 비교횟수의 시간복잡도 : 정렬의 대상이 N개일 때, 각 병합의 단계마다 최대 n번째 비교연산을 진행한다. => O(nlog2n)

이동연산의 시간복잡도 : 임시 배열에 병합해서, 원래 위치로 변경해야하기 때문에 비교횟수의 시간복잡도 X 2이다. 하지만, 곱하기 2는 시간복잡도에서 크게 좌우하지 않으므로 이도 이렇게 나타낼 수 있다. => O(nlog2n)

퀵 정렬 (Quick Sort)

퀵 정렬은 말로 설명하기에 어려운 부분이라 위 그림을 보면서 설명하겠다. 우선, 접근하기 전에 배열에서 평균적으로 중간값을 가진 값을 피벗으로 설정하고 시작하는 것이 위 코드에서 더 효율적으로 사용할 수 있다. 피벗을 제일 왼쪽에 두고 피벗의 바로 왼쪽은 Left, 배열의 제일 끝부분을 Right라고 정의해보자. 서로 마주보면서 한칸씩 이동할 것이다. 거기서 Left값이 피벗보다 큰 값을 만날때 멈추고, Right값이 피벗보다 작은 값을 가질때는 두 개의 데이터의 위치를 변경해주는 것을 반복한다. 그 이후, 사이에 데이터가 없을때까지 이동했을 때, pivot은 Left의 위치와 바꾼다. 그렇게 하면, pivot의 기준으로 왼쪽에는 pivot보다 작은 값, 오른쪽에는 큰값만 남아있게 된다. 이 과정의 반복이다. 물론 이번에는 pivot이 2개 생겼지만, 이는 재귀를 활용하면 쉽게 해결할 수 있는 부분이다.

퀵 정렬 시간복잡도

이는 비교 연산의 횟수는 O(nlog2n)이다. 물론, 피봇의 위치에 따라 크게 좌우될 수 있지만, 피봇을 정의해주는 것은 그렇게 시간복잡도에 좌우하지 않으므로 무조건 해주는 게 맞다. 최악의 경우는 O(N^2)이다. 왜냐면 반복문을 2개 구성하고 있기 때문이다. 이걸 보면 왜 Quick 이라는 말을 쓸지 궁금할 수 있겠지만, O(nlog2n)의 시간복잡도를 이루는 힙 정렬, 병합 정렬보다는 퀵 정렬이 훨씬 더 빠른 속도를 가진다고 정리된 것이 있기에 더 효율적인 정렬로 현재도 많이 사용하고 있는 정렬이다.

기수 정렬(Radix Sort)

기수 : 주어진 데이터를 구성하는 기본 요소
기수를 이용해 버킷(큐로 구현)에 넣었다가 그대로 빼는 방법

사실, 이 기수정렬은 O(N)이라는 시간복잡도를 가진다. 왜냐하면 버킷으로부터 데이터를 삽입과 추출하는 것이 한 쌍 끝이기 때문이다. 하지만, 조건이 있다. 이는 데이터의 길이가 같을 때만 사용이 가능하다. 즉, 7과 14를 정렬하기 위해서는 그대로의 값으로는 정렬을 할 수 없고, 7을 07이라고 십의 자리수가 0임을 정의해준 이후 진행해야한다. 그러면 기수정렬의 특징 2가지만 보고 이번 포스트를 마무리하도록 하겠다. 다음 포스트는 탐색 알고리즘의 종류에 대해 학습할 것이다.

LSD 기수 정렬 (Least Significant Digit)
-> 작은 자릿수부터 정렬하여 큰 자릿수까지 모두 비교, 중간에 판단이 불가능하기 때문에 만약 데이터가 10,11자리수여도 끝까지 비교한 이후 빼야 올바른 정렬 결과를 확인할 수 있다.
MSD 기수 정렬 (Most Significant Digit)
-> 큰 자릿수부터 정렬하여 작은 자릿수까지 비교, 중간에 정렬이 완성될 수 있기에 수시로 데이터 정렬 여부 확인이 필요함.