신입 개발자 기술면접 : C++ 정렬 총정리 (버블, 삽입, 선택, 퀵, 힙, 병합)

https://velog.io/@jinh2352/%EC%A0%95%EB%A0%AC-%EA%B8%B0%EB%B3%B8

https://d2.naver.com/helloworld/0315536

 

화이트보드나 종이나 비쥬얼 스튜디오에 작성하면서 설명할 수 있어야 합니다.

 

버블, 삽입, 선택 알고리즘은 모두 기본적인 정렬 알고리즘으로, 대규모 데이터셋에 대해서는 비효율적일 수 있습니다. 그러나 간단한 사용 사례나 작은 데이터셋에는 여전히 유용할 수 있습니다. 데이터가 이미 부분적으로 정렬되어 있거나, 데이터의 양이 적을 때는 삽입 정렬이 다른 두 알고리즘에 비해 더 빠를 수 있습니다. 합병 정렬은 모든 경우에서 O(NlogN) 의 시간 복잡도를 유지하지만, 추가 메모리 요구와 캐시 효율 문제로 인해 평균적인 성능이 퀵 정렬보다 느릴 수 있습니다.

 

합병 정렬과 퀵 정렬은 둘 다 효율적인 정렬 알고리즘이지만, 작동 방식에 몇 가지 중요한 차이점이 있습니다.

1. 작동 원리: 합병 정렬은 배열을 반으로 나누고 각 부분을 재귀적으로 정렬한 다음 합치는 방식으로 동작합니다. 반면, 퀵 정렬은 피벗을 선택하여 이를 기준으로 배열을 두 부분으로 나눈 뒤, 각 부분을 재귀적으로 정렬합니다.
2. 공간 복잡도: 합병 정렬은 추가 배열을 사용하기 때문에 공간 복잡도가 높습니다. 퀵 정렬은 제자리 정렬이 가능하여 추가 공간이 거의 필요하지 않습니다.
   • 퀵 정렬은 지역적으로 데이터를 다루기 때문에 캐시 활용이 더 효율적일 수 있습니다. 이는 퀵 정렬의 속도를 추가적으로 높여줍니다.
   • 반면 합병 정렬은 분할된 배열의 여러 부분을 동시에 다루기 때문에, 캐시 효율이 떨어질 수 있습니다.
3. 최악의 경우 성능: 합병 정렬은 모든 경우에 O(NlogN)의 시간 복잡도를 가지지만, 퀵 정렬은 최악의 경우 O(N^2)까지 느려질 수 있습니다. (그러나 퀵 정렬은 실제 적용에서는 피벗을 잘 선택하거나, 랜덤화 기법을 사용하여 최악의 경우를 방지할 수 있습니다)
4. 안정성: 합병 정렬은 안정 정렬 방법입니다. 즉, 동일한 값을 가진 요소들의 순서가 유지됩니다. 퀵 정렬은 안정적이지 않을 수 있습니다.
5. 평균 성능: 평균적으로, 퀵 정렬은 대부분의 경우에서 더 빠른 성능을 보이나, 특정 데이터셋에서는 합병 정렬이 더 효율적일 수 있습니다.

힙 정렬은 추가적인 메모리 사용이 거의 없고, 최악의 경우에도 괜찮은 성능을 보이지만, 데이터의 상대적 순서를 유지하지 않는 불안정한 정렬 방식이라는 점에서 한계를 가지고 있습니다. 힙 정렬은 추가적인 메모리 사용이 거의 없고, 최악의 경우에도 괜찮은 성능을 보이지만, 데이터의 상대적 순서를 유지하지 않는 불안정한 정렬 방식이라는 점에서 한계를 가지고 있습니다.

 

힙 정렬이 퀵 정렬이나 합병 정렬에 비해 일반적으로 덜 효율적이라고 여겨지는 주된 이유는 다음과 같습니다.

1. 캐시 효율성: 힙 정렬은 이진 힙의 특성상 메모리 접근 패턴이 연속적이지 않아 캐시 활용이 비효율적입니다. 반면, 퀵 정렬과 합병 정렬은 더 연속적인 메모리 접근 패턴을 가지며, 특히 합병 정렬은 순차적인 메모리 접근으로 높은 캐시 효율성을 보입니다.
2. 비교 및 교환 횟수: 힙 정렬은 힙을 유지하기 위해 상대적으로 많은 비교와 요소 교환을 필요로 합니다. 퀵 정렬은 평균적인 경우 더 적은 비교와 교환으로 정렬을 수행할 수 있으며, 합병 정렬은 추가적인 공간을 사용하여 효율적인 비교와 병합을 수행합니다.
3. 최악의 경우 성능: 퀵 정렬은 최악의 경우 O(N^2) 의 시간 복잡도를 가지지만, 평균적으로는 O(NlogN) 이며, 피벗 선택 전략에 따라 최악의 경우를 방지할 수 있습니다. 합병 정렬은 모든 경우에 O(NlogN) 의 성능을 유지합니다. 힙 정렬도 O(NlogN) 의 성능을 보이지만, 실제 연산 횟수가 더 많을 수 있습니다.
4. 안정성: 합병 정렬은 안정적인 정렬 방식을 제공하는 반면, 힙 정렬은 불안정한 정렬 방식입니다. 퀵 정렬 역시 불안정하지만, 평균적인 성능이 더 우수합니다.
5. 구현 복잡성: 힙 정렬은 이진 힙 구조를 유지해야 하므로 구현이 상대적으로 복잡합니다. 퀵 정렬은 구현이 간단하고, 합병 정렬은 추가적인 메모리가 필요함에도 불구하고 병합 과정이 직관적입니다.

추가...

안정적인 정렬 방법(Stable Sorting Algorithm)이란 동일한 값을 가진 요소들의 상대적인 순서가 정렬 과정에서 변경되지 않는 정렬 방법을 의미합니다. 즉, 정렬 전후로 같은 값의 요소들 사이의 순서가 보존됩니다.

 

예를 들어, 다음과 같은 객체들의 리스트가 있다고 가정해봅시다.
[('apple', 2), ('orange', 1), ('banana', 2)]
여기서 숫자를 기준으로 안정적인 정렬을 수행하면 다음과 같이 됩니다.
[('orange', 1), ('apple', 2), ('banana', 2)]
apple과 banana는 같은 값을 가지지만, 정렬 전 apple이 banana보다 먼저 나왔기 때문에 정렬 후에도 그 순서가 유지됩니다.

안정적인 정렬 알고리즘의 예로는 버블 정렬(Bubble Sort), 병합 정렬(Merge Sort), 삽입 정렬(Insertion Sort) 등이 있습니다. 반면, 선택 정렬(Selection Sort)과 퀵 정렬(Quick Sort)과 힙 정렬(Heap Sort) 같은 알고리즘은 안정적이지 않습니다. 이러한 구별은 특히 복잡한 데이터 구조를 다룰 때 중요할 수 있으며, 데이터의 순서가 중요한 상황에서는 안정적인 정렬 방법을 선택하는 것이 좋습니다.

---

🗣️ 버블 정렬 시간 복잡도: O(N^2), 메모리: O(1)

 

 

📌소개

버블 정렬은 인접한 두 수를 계속해서 비교하여 정렬하는 알고리즘이다. 

 

1. 인접한 두 수를 대소를 비교한다.

2. 내림차순, 오름차순에 따라 두 수의 자리를 바꾼다.

3. 나머지 값들도 동일하게 처리한다.

 

구현이 매우 간단하여 코드 구현이 쉽지만, 비교 작업이 많기 때문에 시간 복잡도가 O(n^2) 로 오래 걸린다는 단점이 있다.

적은 양의 데이터를 정렬할때는 버블 정렬을 쓸 수 있지만, 대용량의 데이터를 정렬시 엄청 시간이 소요될 것이다. 

 

출처 https://meongj-devlog.tistory.com/193 

 

📌코드

#include <vector>
#include <algorithm>
using namespace std;

void bubble_sort(vector<int>& v)
{
	const int n = v.size();
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
		}
	}
}

 

---

🗣️ 삽입 정렬 최선의 시간: O(n), 최악의 시간: O(n^2), 공간 복잡도: O(1)

 

 

삽입정렬 예시(wikipedia)

 

📌소개

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.

 

+ 손 안의 카드를 정렬하는 방법과 같습니다.
새로운 카드를 정렬된 카드 사이의 알맞은 사이를 찾아 삽입해줍니다.

 

두번째 원소부터 시작하여 그 앞 원소들과 비교하여 삽입할 위치를 지정하고 원소를 뒤로 옮기고
그 자리에 원소를 삽입하여 정렬합니다. 

 

📌시간 복잡도

최선일 경우 (오름차순으로 정렬되어 있음)

• 이동없이 1번씩 비교할 경우
• 비교 횟수: n - 1 번 O(n)

최악일 경우 (내림차순으로 정렬되어 있음)

• 비교 횟수: 외부 루프 안의 각 반복마다 n - 1, n - 2, ... , 1 번의 반복
• (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
• 교환 횟수: 외부 루프의 각 단계마다 (i+2)번의 이동 발생
• n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)

📌코드

#include <vector>
#include <iostream>
using namespace std;

void insertion_sort(vector<int>& v)
{
	const int n = v.size();
	for (int i = 1; i < n; i++)
	{
		int key = v[i];
		int  j = i - 1;

		while (j >= 0 && v[j] > key)
		{
			v[j + 1] = v[j];
			j = j - 1;
		}
		v[j + 1] = key;
	}
}

 

📌 출처

https://meongj-devlog.tistory.com/194 💙시간 복잡도

https://blackon29.tistory.com/4 💙 코드

 https://gguzunhee.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-insertion-sort-c 💙 소개

 

버블, 삽입, 선택 알고리즘은 모두 기본적인 정렬 알고리즘으로, 대규모 데이터셋에 대해서는 비효율적일 수 있습니다. 그러나 간단한 사용 사례나 작은 데이터셋에는 여전히 유용할 수 있습니다. 데이터가 이미 부분적으로 정렬되어 있거나, 데이터의 양이 적을 때는 삽입 정렬이 다른 두 알고리즘에 비해 더 빠를 수 있습니다.

---

🗣️ 선택 정렬 시간 복잡도: O(n^2), 공간 복잡도:  O(1)

 

📌소개

선택 정렬은 제자리 정렬 알고리즘의 하나로 정렬되지 않은 데이터들 중에서 가장 작은 값을 추출하여 가장 맨 앞으로 정렬해나가는 알고리즘이다. 

 

1. 배열 중에 최솟값을 찾는다.

2. 최솟값을 맨 앞으로 정렬시킨다.(swap)

3. 나머지 값들도 동일한 방식으로 정렬해나간다.

 

알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우 사용하기에 용이하며,

구현이 간단하지만 비효율적인 방법인 알고리즘이다.

 

📌시간 복잡도

기준값과 비교값들 중 최솟값을 찾기 위해 이중 for문 필요
- 첫 번째 회전 비교 횟수 : 1 부터 (n-1) = n-1
- 두 번째 회전 비교 횟수 : 2 부터 (n-1) = n-2
               ...
=> 최솟값 찾기 : n-1, n-2, ..., 2, 1 번
T(n) = (n-1)+(n-2)+...+2+1=n(n-1)/2 = O(n^2)

 

📌 출처

https://meongj-devlog.tistory.com/194 

 

📌코드

void selection_sort(vector<int>& v)
{
	const int n = v.size();
	for (int i = 0; i < n - 1; i++)
	{
		int minIdx = i;
		for (int j = i + 1; j < n; j++)
		{
			// minIdx 보다 작은 요소가 있다면 교체 후 갱신
			if (v[j] < v[minIdx])
				minIdx = j;
		}
		if (i != minIdx)
			swap(v[i], v[minIdx]);
	}
}

---

🗣️ 퀵 정렬 평균과 최선의 시간: O(NlogN), 최악의 시간 O(N^2) ... 퀵이라며.

 

퀵 정렬은 무작위로 선정된 한 원소(Pivot 역할) 을 사용하여 배열을 분할한다.
선정된 원소보다 작은 원소들은 앞에, 큰 원소들은 뒤에 보낸다. ➡ 그리고 배열이 분할된다.
배열 분할 작업은 위와같이 연속된 swap 연산을 통해 효율적으로 수행된다.
배열과 그 부분 배열을 반복적으로 분할해 나가면 결국에 배열은 정렬된 상태에 도달한다.

 

하나의 분할 과정에서 사용되는 원소(Pivot) 이 중간값, 적어도 중간값에 가까운 값이 되리라는 보장이 없기에 퀵 정렬은 최악의 경우 수행 시간이 O(N ^2)이 될 수 있다.

 

평균적으로는 O(NLogN)이다.

 

https://velog.io/@jifrozen/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%A9%EB%B3%91%EC%A0%95%EB%A0%AC-%ED%80%B5%EC%A0%95%EB%A0%AC-%ED%9E%99%EC%A0%95%EB%A0%AC

 

하나의 리스트를 Pivot 을 기준으로 두 개의 부분리스트로 나누어 하나는 Pivot  보다 작은 값들의 부분리스트, 다른 하나는 Pivot  보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.

합병정렬과 다른점은 합병정렬의 경우 절반으로 나누어 분할정복하고, 퀵정렬은 Pivot 을 기준으로 나누기 때문에 비균등하게 나뉘어 정복한다는 점이다.

서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정 정렬 알고리즘이다.

 

Pivot 을 선택하는 기준은 3가지이다. 왼쪽, 중앙, 오른쪽
선택함에 따라 코드가 약간 달라질 수 있지만 모두 ' Pivot '을 설정하고 Pivot  을 기준으로 왼쪽 오른쪽 부분리스트를 만드는 과정은 같다. 이를 Partitioning 과정이라고 한다.

Pivot  을 왼쪽으로 선택하는것이 이해하기 쉽기 때문에 왼쪽 선택 방식으로 구현하겠다.

1. Pivot  을 하나 선택한다 (왼쪽, 중앙, 오른쪽 자유롭게)
2. Pivot  을 기준으로 왼쪽에서는 Pivot  보다 큰 값을 찾고, 오른쪽에서는 Pivot  보다 작은 값을 찾는다.
3. 양 방향에서 찾았다면 두 원소를 교환한다.
4. 왼쪽 탐색 위치가 오른쪽 탐색위치 보다 작다면 다시 2번부터 반복한다. 둘의 위치가 엇갈렸다면 5번으로
5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다 (분할)
6. 결국 낱개로 나뉘게 되어있고 다 분할하면 인접한 부분리스트끼리 합친다 (정복)

https://velog.io/@jifrozen/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%A9%EB%B3%91%EC%A0%95%EB%A0%AC-%ED%80%B5%EC%A0%95%EB%A0%AC-%ED%9E%99%EC%A0%95%EB%A0%AC

#include <iostream>
using namespace std;
//퀵정렬
int n,cnt, quick[10000001];

void quickSort(int i, int j)
{
	if(i>=j) return;
	int pivot = quick[(i+j)/2];
	int left = i;
	int right = j;
	
	while(left<=right)
	{
		while(quick[left]<pivot) left++;
		while(quick[right]>pivot) right--;
		if(left<=right)
		{
			swap(quick[left],quick[right]);
			left++; right--;
		}
	}
	quickSort(i,right);
	quickSort(left,j);
}

---

🗣️ 힙 정렬 시간 복잡도: O(NLogN)

 

먼저 힙 정렬은 완전이진트리를 기반으로 구현되는 정렬 방식이다. 완전 이진트리는 트리의 마지막 레벨을 제외한 나머지 레벨에 모든 Node가 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 노드가 채워진 Tree를 말한다.

 

말 그래도 최대힙의 root는 제일 큰 값을 가지기 때문에, 최대값을 찾는데 소요되는 시간은 `O(1)`이다. 루트 노드에서 최대값을 삭제하면 빈 루트노드를 다른 노드가 채워줘야한다. 이 과정에서 heap은 맨 마지막 노드를 루트 노드로 대체한 후, heapify 과정을 거쳐 heap 구조를 유지한다.

 

힙의 경우는 완전 정렬 상태가 아니고 느슨한 정렬 상태이다. 왜냐면 모든 노드가 정렬된채 유지되는것이 아닌 부모 노드가 자식노드보다 항상 큰값이라는 조건만 만족하기 때문이다. 말그대로, 형제간의 우선순위는 고려하지 않는다

 

C++의 경우 표준 우선순위큐 (내림차순) 가 힙자료구조를 기반으로 구현되었다. 그렇기 때문에 C++ 에서 힙정렬을 이용하고자 하면  `priority_queue`를 사용하면 된다. 아래 코드를 확인하면 어떤 상황에서도 O(NlogN)이다.

#include <vector>
#include <queue>
#include <algorithm>

void HeapSort(vector<int>& v)
// 입력으로 받은 벡터 v를 힙 정렬하여 오름차순으로 정렬한다.
{
    priority_queue<int, vector<int>, greater<int>> pq;
    // 우선순위 큐 생성. 
    // priority_queue 의 세 번째 템플릿 인자로 greater<int> 를 사용하여 
    // 작은 값부터 큰 값까지 오름차순으로 정렬되도록 설정.
    // greater<int> 는 C++ STL의 함수 객체 (predicate) 이다.

    // O(NlogN)
    for (int num : v)
        pq.push(num); // 입력값들을 pq에 넣어주고 // O(logN)

    v.clear(); // 벡터를 비워준다.

    // O(NlogN)
    while (pq.empty() == false) // 우선순위 큐가 비어있지 않을 동안
    {
        v.push_back(pq.top()); // O(1) // 가장 작은 값을 벡터에 추가한다.
        pq.pop(); // O(logN) // 가장 작은 값을 우선순위 큐에서 제거한다.
    }
}

 

위와 같이 정렬한다면 추가적인 메모리 pq가 필요하다.
만약 heap을 직접 구현하여 추가적인 메모리 없이 힙정렬을 구현한다면 어떻게 될까?

 

힙정렬은 완전이진트리 기반으로써, 배열을 완전이진트리 꼴로 생각하고 계산을 할 수 있다.

실제로 Left_Child, Right_Child, Parent_Node 등을 특별한 자료구조를 이용해서 생성하는 것은 아니고,

Index번호를 마치 완전이진트리 처럼 생각하고 사용한다.

heap의 자료구조는 어떻게 구현할 수 있을까? 바로 배열을 이용하는것이다. 힙은 이러한 규칙을 가진다.

왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 1
오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 2
부모 노드 인덱스 = (자식노드 인덱스 - 1) / 2

 

힙 정렬의 핵심 단계는 두 부분으로 나뉩니다.

1. Heapify: 주어진 배열을 힙으로 변환합니다. 이 과정에서는 배열의 비리프 노드 (leaf node가 아닌 노드) 에서 시작하여 루트 노드까지 거꾸로 이동하면서 힙 속성을 만족하도록 조정합니다.
2. Sort: 힙에서 최댓값(또는 최솟값)을 추출하고, 남은 요소들로 힙을 재구성한 후, 배열의 끝에서부터 정렬된 요소를 배치합니다.

아래 코드에서 heapify 함수는 주어진 노드를 루트로 하는 서브트리가 힙 속성을 만족하도록 조정합니다.

heap_sort 함수는 먼저 배열을 힙으로 변환하고, 각 요소를 추출하여 정렬된 배열을 만듭니다.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

// Heapify 과정을 수행하는 함수
void heapify(vector<int>& v, int n, int i) {
    int largest = i; // 가장 큰 요소를 가리키는 인덱스로 i(루트)를 초기화
    int left = 2 * i + 1; // 왼쪽 자식 노드 인덱스
    int right = 2 * i + 2; // 오른쪽 자식 노드 인덱스

    // 왼쪽 자식이 루트보다 큰 경우
    if (left < n && v[left] > v[largest])
        largest = left;

    // 오른쪽 자식이 현재 가장 큰 요소보다 큰 경우
    if (right < n && v[right] > v[largest])
        largest = right;

    // 가장 큰 요소가 루트가 아닌 경우
    if (largest != i) {
        swap(v[i], v[largest]);
        // 재귀적으로 하위 트리에 대해 heapify를 호출
        heapify(v, n, largest);
    }
}

// 힙 정렬을 수행하는 함수
void heap_sort(vector<int>& v) {
    int n = v.size();

    // 배열을 힙으로 구성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(v, n, i);

    // 하나씩 요소를 추출하면서 힙을 재구성
    for (int i = n - 1; i > 0; i--) {
        swap(v[0], v[i]); // 현재 루트(가장 큰 값)를 끝으로 이동
        heapify(v, i, 0); // 힙의 크기를 줄이고 재구성
    }
}

int main() {
    vector<int> data = {12, 11, 13, 5, 6, 7};
    heap_sort(data);

    cout << "Sorted array: \n";
    for (int i : data)
        cout << i << " ";
    cout << endl;

    return 0;
}

---

🗣️ 병합 정렬 시간 복잡도: O(NLogN), 공간 복잡도: 메모리 상황에 따라 다름

https://velog.io/@jifrozen/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%A9%EB%B3%91%EC%A0%95%EB%A0%AC-%ED%80%B5%EC%A0%95%EB%A0%AC-%ED%9E%99%EC%A0%95%EB%A0%AC

 

병합정렬 또는 합병정렬은 정렬할 데이터들을 일단 반으로 쪼개고 각 각 정렬한 후 나중에 합치는 알고리즘이다.

비교 기반 정렬 알고리즘이고, 일반적인 방법으로 구현했을 때 안정 정렬에 속하며 분할 정복 알고리즘의 하나이다.

매번 정렬된 데이터를 담을 배열 공간이 추가적으로 필요하다는 점에서 메모리 사용이 비효율적인 문제가 있다. 이에 병합 정렬의 시간 복잡도는 어떤 상황에서도 O(NlogN)이다.

 

출처: https://meongj-devlog.tistory.com/197

 

합병 = '문제를 분할하고, 분할한 문제를 정복하여 합치는 과정'이다.
1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (분할)
2. 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다.
3. 인접한 부분리스트끼리 정렬하여 합친다. (정복)

 

https://velog.io/@jifrozen/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%A9%EB%B3%91%EC%A0%95%EB%A0%AC-%ED%80%B5%EC%A0%95%EB%A0%AC-%ED%9E%99%EC%A0%95%EB%A0%AC

#include <vector>
#include <queue>
#include <algorithm>

/*
[3][K][7][2][J][4][8][9]
[3][K][7][2]  [J][4][8][9]
[3][K]  [7][2]  [J][4]  [8][9]
[3]  [K]  [7]  [2]  [J]  [4]  [8]  [9]
[3][K]  [7][2]  [J][4]  [8][9]
[3][K][7][2]  [J][4][8][9]
*/

void MergeResult(vector<int>& v, int left, int mid, int right)
{
    int leftIdx = left;
    int rightIdx = mid + 1;

    // 임시 벡터
    vector<int> temp;

    // O(N)
    while (leftIdx <= mid && rightIdx <= right)
        // 데이터가 아직 남아있다면
    {
        if (v[leftIdx] <= v[rightIdx])
        {
            temp.push_back(v[leftIdx]);
            leftIdx++; // 커서 옮겨주기               
        }
        else
        {
            temp.push_back(v[rightIdx]);
            rightIdx++; // 커서 옮겨주기                         
        }
    }

    // 왼쪽이 먼저 끝났다면 (왼쪽 부분 배열 병합이 모두 끝나면)
    if (leftIdx > mid)
    {
        while (rightIdx <= right)
        {
            temp.push_back(v[rightIdx]);
            rightIdx++;
        }
    }
    // 오른쪽이 먼저 끝났다면 (오른쪽 부분 배열이 모두 병합되어 끝났다면)
    else
    {
        while (leftIdx <= mid)
        {
            temp.push_back(v[leftIdx]);
            leftIdx++;
        }
    }

    // temp 에 넣어준 걸 원본에 덮어쓰기
    for (int i = 0; i < temp.size(); i++)
        v[left + i] = temp[i];
}

// O(NlogN)
void MergeSort(vector<int>& v, int left, int right)
// 영역을 찝어서 관리하는 식으로 해보기!
{
    if (left >= right)
        return;

    // 분할
    int mid = (left + right) / 2;
    // 재귀
    MergeSort(v, left, mid);
    MergeSort(v, mid + 1, right);

    // 나뉜 걸 다시 합치기 위해 아래 함수를 호출
    MergeResult(v, left, mid, right);
}

int main()
{
    vector<int> v{ 1, 5, 3, 4, 2 };

    MergeSort(v, 0, v.size() - 1);
}

 

---

정렬 알고리즘들에 대해 설명하라.

정렬 알고리즘을은 굉장히 많지만 크게 다섯 가지만 추리자면

버블정렬, 선택정렬, 삽입정렬, 합병정렬, 퀵정렬이 있습니다.

버블정렬 : 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로서 이중for문을 사용하여 계속해서 다음인덱스랑 비교후 바꾸는 알고리즘입니다.

선택정렬 : 제자리 정렬알고리즘 중 하나로서, 해당 순서에 넣을 위치는 정해두고 어떤 원소를 넣을지 선택하는 알고리즘입니다. 첫번째 자료를 두번째 자료부터 끝까지 비교 후 가장작은 값을 찾아넣고 두번쨰 자료는 세번째자료부터 마지막까지 비교하여 넣는 방식을 반복하여 정렬합니다.

삽입정렬 : 자료 배열의 모든 요소를 앞에서부터 차래대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로서 정렬을 완성하는 알고리즘입니다. 두번째 자료부터 시작하여 n - 1 을 반복하면서 자신의 앞 자료들과 비교하여 삽입할 위치를 지정한 후 자료가 삽입될 위치를 찾는 정렬 방식입니다.

합병정렬 :  분할정복 알고리즘 중 하나로 문제를 작은 문제 두개로 분류하고 각각을 해결한 후 결과를 모아서 원래의 문제를 해결하는 방식입니다.

 

퀵정렬(중요!)

퀵정렬 : 가장빠른 정렬방식중 하나로서 다른원소의 비교만으로 정렬을 수행하는 비교정렬이자 분할해서 정렬을 수행하므로 분할정복정렬에도 속합니다.

제일 중요한 정렬 방식이므로 조금 길게 써보겠습니다.

퀵정렬은 Pivot Point라고하는 기준값을 하나 설정합니다. 이 값을 기준으로 작은값을 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행합니다. 이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것입니다.

진행방식을 순서대로 정리하자면

1. 맨 앞의 숫자를 피봇으로 지정합니다.

2. 피봇의 다음 인덱스를 i, 데이터의 맨 끝을 j로 지정하고

3. i는 증감 연산하면서 pivot보다 큰 데이터를 찾고 j는 감쇠연산하면서 pivot보다 작은 데이터를 찾습니다.

4. 만약 i와 j가 교차되지 않고 서로 알맞은 값을 찾았다면 i의 데이터와 j의 데이터를 스왑합니다.

5. 찾는 도중 i > j 가 되었다면 pivot과 j를 스왑 하고

6. 이를 실행하였다면 pivot의 좌측은 pivot보다 작은 값들만 우측은 큰값을만 존재하게됩니다.

7. 지금까지 실행한 알고리즘을 pivot을 기준으로 좌측에서 우측으로 반복해서 수행합니다.(pivot은 제외합니다.)

가장 많이 사용되고 빠른 정렬중 하나지만 갖아 큰 단점이 있습니다.

기존에 이미 정렬이 되어있는 배열을 정렬할경우 O(N^2)의 시간복잡도를 가지게 됩니다.

이를 개선하는 방법으로 첫째, 배열의 첫째나 마지막 요소가 아닌 난수를 pivot 으로 설정하는 방법이 있습니다. 이는 pivot이 편향되는 문제점을 해결할 수 있습니다. 둘째, 배열의 첫 번째 요소, 중간 요소, 마지막 요소 중 중간 값을 pivot으로 선택하는 방법입니다. 이때 가장 작은 값을 배열의 첫 번째에, 가장 큰 값을 배열의 마지막에 위치시킵니다. 그리고 중간 값을 배열의 마지막에서 두 번째 인덱스 숫자와 교환하면 재귀 횟수를 줄일 수 있고 배열의 분할이 가운데에서 수행될 확률이 높아집니다.

---

Reference

• https://velog.io/@strurao/C-%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A0%AC 정렬
• https://velog.io/@jacod2/C-%EB%A9%B4%EC%A0%91-%ED%82%A4%EC%9B%8C%EB%93%9C 면접 키워드