정렬

정렬

정렬 알고리즘

Algorithm  · 

정렬 알고리즘

N2 알고리즘

- 선택정렬 -> 선택한 인덱스에 맞는 값을 찾아 넣기

for (int i = 0; i < n; i++) {
	int minIndex = i;
	for (int j = i + 1; j < n; j++)
		if (arr[minIndex] > arr[j]) minIndex = j;
	swap(arr[i], arr[minIndex]);
}

- 버블정렬 -> 바로 옆에 있는 수와 지속적으로 비교하여 맞는 위치 찾아가기

for (int i = 0; i < n - 1; i++)
	for (int j = i + 1; j < n; j++)
		if (arr[i] > arr[j]) swap(arr[i], arr[j]);

- 삽입정렬(최적의 경우 n만에 실행) -> 해당 숫자를 맞는 위치에 삽입한다.

for (int i = 1; i < n; i++) {
	int com = arr[i];
	int j = i - 1;
	for (;j > -1 && arr[j] > com; j--)
		arr[j + 1] = arr[j];
	arr[j + 1] = com;
}

예를 들어)

5 4 3 2 1을 정렬한다고 할 때,

i = 1일 때, 4 5 3 2 1

i = 2일 때, 3 4 5 2 1

i = 3일 때, 2 3 4 5 1

i = 4일 때, 1 2 3 4 5 가 될 것이다.

추가적으로 설명하자면, 손 안의 카드를 정렬하는 방법과 유사하다.

앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입한다.

NlogN 알고리즘

- 합병정렬 -> 분할정복을 이용하여 최대한 쪼갠 후 병합하면서 정렬한다.

void merge(int l,int m, int r) {
	int com[101] = {};
	int left = l, right = m + 1;
	int idx = 0;
	while (left <= m && right <= r) {
		if (arr[left] < arr[right]) com[idx++] = arr[left++];
		else com[idx++] = arr[right++];
	}
	while (left <= m) com[idx++] = arr[left++];
	while (right <= r) com[idx++] = arr[right++];
	for (int i = l; i <= r; i++) arr[i] = com[i-l];
	return;
}
void mergeSort(int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(left, mid);
		mergeSort(mid + 1, right);
		merge(left, mid, right);
	}
}
mergeSort(0, n - 1);

- 퀵정렬 -> 분할정복을 이용하여 쪼개면서 정렬하고 병합한다.

void quickSort(int start, int end) {
	if (start >= end) return;
	int p = start;
	int i = p + 1;
	int j = end;
	while (i <= j) {
		while (i <= end && arr[i] <= arr[p]) i++;
		while (j > start && arr[j] >= arr[p]) j--;
		if (i > j) swap(arr[p], arr[j]);
		else swap(arr[i], arr[j]);
	}
	quickSort(start, j-1);
	quickSort(j + 1, end);
}
quickSort(0,n-1);

퀵정렬 설명글 링크 https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html