자료구조_12.정렬

정렬은 자료를 순서대로 정리 해주는 것을 말합니다.
정렬의 종류를 알아보고 구현 방식을 알아보겠습니다.

 

 

버블정렬 

---

버블정렬의 정렬방식

 

버블정렬은 앞의 자료와 뒤의 자료의 크기를 비교하여

더 큰 수를 뒤로 보내는 정렬 방식입니다.

---

 

코드는 이렇게 구현하면 됩니다.

#pragma region "bubble"
int main() {
	int a[101], n, i, j, tmp;
	cin >> n; 
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (i = 0; i < n - 1; i++) {
		for (j = 0; j < n - i - 1; j++) {
			if (a[j]>a[j+1]) {
				tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
	}
	for (i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}
#pragma endregion

 

 

선택정렬

---

선택정렬의 정렬방식

 

선택정렬은 가장 배열중 가장 작은 수를 찾아
그 수를 배열의 맨 앞으로 보내는 정렬입니다.

---

선택 정렬의 구현 방식은 이렇습니다.

#pragma region "selection"
int main() {
	int a[101], n, tmp, selected, i, j;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (i = 0; i < n - 1; i++) {
		selected = i;
		for (j = i + 1; j < n; j++) {
			if (a[j] < a[selected])
				selected = j;
		}
		tmp = a[i];
		a[i] = a[selected];
		a[selected] = tmp;
	}
	for (i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}
#pragma endregion

 

 

삽입정렬

---

삽입정렬의 정렬 방식

 

삽입정렬은 자료 하나를 잡고 그 자료보다 낮은 수가

나올때까지 앞으로 보내는 정렬입니다.

---

삽입정렬의 구현방식은 이렇습니다.

#pragma region "insertion"
int main() {
	int a[100], n, num, i, j;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (i = 1; i < n; i++) {
		num = a[i];
		for (j = i - 1; j >= 0; j--) {
			if (a[j] > num)
				a[j + 1] = a[j];
			else break;
		}
		a[j + 1] = num;
	}
	for (i = 0; i < n; i++) {
		cout << a[i]<< " ";
	}
	return 0;
}
#pragma endregion

 

계수정렬

---

계수정렬의 정렬 방식

 

계수정렬은 정렬을 쭉 돌며 각각의 수가 몇개 있는지 카운팅하고
그 카운팅 한 수대로 배열을 바꾸는 정렬입니다.

---

코드로는 이렇게 구현합니다.

#pragma region "count" 
int main() {
	int n, num;
	cin >> n;
	int cnt[101] = { };

	for (int i = 0; i < n; i++) {
		cin >> num;
		cnt[num]++;
	}

	for (int i = 1; i < 101; i++) {
		while (cnt[i] != 0) {
			cout << i << " ";
			cnt[i]--;
		}
	}
}
#pragma endregion

 

 

기수정렬

---

기수정렬의 정렬 방식

 

우선 1의 자리수부터 비교를 하여 정렬을 하고

그리고 10의 자리수로 정렬을 합니다.

그러고 100의 자리수로 정렬을 하게되면 같은

자릿수인 수들이 정렬이되기 때문에 정렬이 되게 됩니다.

---

코드로는 이렇게 구현합니다.

#pragma region "radix" 
#define DIGITS 3
queue<int>q[10];
int num[100];
void radix_sort(int size) {

	int i = 0, factor = 1;
	for (int d = 0; d < DIGITS; d++)
	{
		for (int j = 0; j < size; j++)
		{
			q[num[j]/factor%10].push(num[j]);
		}

		for (int k = 0; k < 10; k++)
		{
			while (q[k].size())
			{
				num[i++] = q[k].front();
				q[k].pop();
			}
		}
		factor *=10;
        i=0;
	}
}

int main() {
	int size;
	cin >> size;
	for (int i = 0; i < size; i++) {
		cin >> num[i];
	}
	radix_sort(size);
	for (int i = 0; i < size; i++) {
		cout << num[i]<<" ";
	}
}
#pragma endregion

 

 

퀵정렬

---

 

퀵정렬의 정렬방식

 

하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법입니다.

---

 

코드로는 이렇게 구현합니다.

#pragma region "quick" 
int a[100];
void quickSort(int start, int end) {
	if (start >= end) {//원소가 1개인 경우 
		return;
	}
	int key = start; //키는 첫번째 원소
	int left = start + 1; //왼쪽 출발 지점 
	int right = end; //오른쪽 출발 지점 
	int temp;

	while (left <= right) {//엇갈릴 때까지 반복 
		while (a[key]>=a[left]&& left <= right) { //키 값보다 큰 값을 만날 때까지 
			left++;
		}
		while (a[key]<=a[right] && right > start) { //키 값보다 작은 값을 만날 때까지 
			right--;
		}
		if (left >= right) { //현재 만나거나 엇갈린 상태면 키 값과 교체
			temp = a[right];
			a[right] = a[key];
			a[key] = temp;
		}
		else { //엇갈리지 않았다면 left와 right를 교체
			temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
	quickSort(start,right-1);
	quickSort(right+1, end);
}

int main() {
	int n, i;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	quickSort(0, n - 1);

	for (i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}
#pragma endregion

 

 

합병정렬

---

합병정렬의 정렬방식

합병정렬은 하나의 리스트를 두개의 균등한 크기로 분할 하고, 분할된 부분 리스트들을

정렬한 다음 정렬된 부분 리스트들을 하나로 합치면서 정렬되게 하는 방법입니다.

---

코드로는 이렇게 구현합니다.

#pragma region "merge"
int a[101], sorted[101];

void merge(int left, int right) {
	int mid;
	int p1, p2, p3;
	if (left < right) {
		mid = (left + right) / 2;
		merge(left, mid);
		merge(mid + 1, right);
		p1 = left; // 정렬된 왼쪽 배열에 대한 인덱스
		p2 = mid + 1; // 정렬된 오른쪽 리스트에 대한 인덱스
		p3 = left; // 합병될 리스트에 대한 인덱스
		//분할정렬된 배열의 합병
		while (p1 <= mid && p2 <= right) {
			if (a[p1] < a[p2]) sorted[p3++] = a[p1++];
			else sorted[p3++] = a[p2++];
		}
		// 남아 있는 왼쪽 배열 일괄 복사
		while (p1 <= mid) sorted[p3++] = a[p1++];
		// 남아 있는 오른쪽 배열 일괄 복사
		while (p2 <= right) sorted[p3++] = a[p2++];		
		//배열 sorted를 배열 a로 재복사
		for (int i = left; i <= right; i++) {
			a[i] = sorted[i];
		}
	}
}

int main() {
	int n, i;
	cin >> n; 
	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}
	merge(1, n);
	for (i = 1; i <= n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}
#pragma endregion

 

 

이상 각종 정렬들과 정렬 방식을 알아보았습니다.