정렬

정렬

1) 버블 정렬

// 1) 버블 정렬 (Bubble Sort)
// N * (N - 1) /2
// = O(N²)
void BubbleSort(vector<int>& v)
{
	const int n = (int)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])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}
}

2) 선택 정렬

// 2) 선택 정렬 (Selection Sort)
// = O(N²)
// 단 버블 정렬보다는 성능이 약간 좋다
// 교환의 횟수가 줄기 때문
void SelectionSort(vector<int>& v)
{
	const int n = (int)v.size();

	for (int i = 0;i < n - 1;i++)
	{
		int bestIdx = i;
		for (int j = i+1;j < n;j++)
		{
			if (v[j] < v[bestIdx])
				bestIdx = j;
		}

		// 교환
		int temp = v[i];
		v[i] = v[bestIdx];
		v[bestIdx] = temp;
	}
}

3) 삽입 정렬

// 3) 삽입 정렬 (Insertion Sort)
// = O(N²)
void InsertionSortt(vector<int>& v)
{
	const int n = (int)v.size();
	for (int i = 1;i < n;i++)
	{
		int insertData = v[i];
		int j;
		for (j = i - 1;j >= 0;j--)
		{
			if (v[j] > insertData)
				v[j + 1] = v[j];
			else
				break;
		}
		v[j + 1] = insertData;
	}
}

4) 힙 정렬

// 힙 정렬 (Heap Sort)
// = O(NlogN)
void HeapSort(vector<int>& v)
{
	priority_queue<int,vector<int>,greater<int>> pq;
	
	// O(NlogN)
	for (int num : v)
		pq.push(num);

	v.clear();

	// O(NlogN)
	while(pq.empty() == false)
	{
		v.push_back(pq.top());
		pq.pop();
	}
}

5) 병합 정렬

// 병합 정렬 (Merge Sort)
// 분할 정복 (Divide and Conquer)
// - 분할 Divide
// - 정복 Conquer
// - 결합 Combine
// =  O(NlogN)


// O(N)
void MergeResult(vector<int>& v, int left, int mid, int right)
{
	vector<int> temp;

	int leftIdx = left;
	int rightIdx = mid + 1;
	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++;
		}
	}

	for (int i = 0;i < temp.size();i++)
		v[left + i] = temp[i];
}

// O(logN)
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);
}

6) 퀵 정렬

// 퀵 정렬 (Quick Sort)
// 맨 왼쪽 첫번째 값을 pivot으로 설정
// = O(NlogN) <- 평균
// = O(N²) <- 최악
// 불필요한 데이터 복사가 일어나지 않음. 
// 따라서 성능이 좋다.
int Partition(vector<int>& v, int left, int right)
{
	int pivot = v[left];
	int low = left + 1;
	int high = right;

	// O(N)
	while (low <= high)
	{
		while(low <= right && pivot >= v[low])
			low++;
		while(high >= left + 1 && pivot <= v[high])
			high--;
		if (low < high)
			swap(v[low], v[high]);
	}
	swap(v[left], v[high]);

	return high;
}
void QuickSort(vector<int>& v, int left, int right)
{
	if (left > right)
		return;
	int pivot = Partition(v, left, right);

	// log(N) Or N
	QuickSort(v, left, pivot-1);
	QuickSort(v, pivot +1, right);
}