[C/C++ 6.1] STL Sorting

다양한 sorting 방법

 

Insert Sort )

// STL 을 사용한 다양한 정렬 방법 

// Insert Sort //

// 기본  ver
int main() {
	int arr[6] = { 4,9,11,8,6,2 };
	int result[6];	
	for (int y = 0; y < 6; y++) {
		// 하나씩 배열에 insert 하며
		result[y] = arr[y];
		// 넣자마자, 이미 넣은(앞쪽의)요소와 비교
		for (int x = y; x > 0; x--) {				
			if (result[x - 1] < result[x]) {		// 내림차순  (오름차순 일경우 > )
				swap(result[x - 1], result[x]);
			}
			// 앞쪽보다 작으면 더 비교할 것 없이 끝냄 
			else break;
		}
	}
	// 출력
	for (int x = 0; x < 6; x++) {
		cout << result[x] << " ";
	}
	return 0;
}

// 구조체 배열 ver
	// 숫자-문자 쌍 구조체 형식
	// insert sort 사용
	// i -  숫자 오름차순/ ii - 문자 내림차순 
struct node {
	int a;
	char b;
};
node arr[5] = {
	{1,'A'},
	{3,'A'},
	{2,'C'},
	{1,'B'},
	{3,'B'}
};
// 다중조건일 때 사용할 함수
bool compare(node front, node back) {
	// 1. 숫자비교
	if (front.a < back.a)return true;		// 앞의 숫자가 더 작아야 한다 (참)
	if (front.a > back.a)return false;		// 뒤의 숫자가 더 작으면 (거짓)

	// 둘 다 안걸리고 통과 했다는 것은, 숫자가 같다는 것이므로 
	// 그 다음순위 정렬조건인 문자비교
	
	// 2. 문자비교
	return front.b > back.b;				// T,F 출력 
}
int main() {
	node result[5];
	for (int y = 0; y < 5; y++) {
		result[y] = arr[y];
		for (int x = y; x > 0; x--) {
			// for 가독성 
			node front = result[x - 1];
			node back = result[x];
			// 정렬조건 2개 
			if ( !compare(front,back) ){	// a: 숫자오름차순, b:문자내림차순		//(front.a > back.a || front.a == back.a)  &&  (front.b < back.b) 을 함수대신 대체해도 됨
				swap(result[x - 1], result[x]);
			}
			else break;
		}
	}
	return 0;
}

 

Count Sort )

 

// Count sort				// O(n)의 속도를 가짐
int main() {				// 이중 for문을 세번 돌려 구현
	int arr[7] = { 3,9,1,2,1,3,4 };
	int bucket[11] = { 0 };
	int result[11] = { 0 };
	// 1) DAT					: 해당 값을 index로 하는 DAT를 만들어 각 값 count!
	for (int x = 0; x < 7; x++) {
		bucket[arr[x]]++;
	}
	// 2) 누적합				: DAT를 활용해 count된 값의 누적합 구하기
	for (int x = 1; x < 11; x++) {
		bucket[x] += bucket[x - 1];
	}
	// 3) 값넣기				: 누적합 = value가 정렬시 몇번째에 위치해 있는지를 나타내줌,  누적 count(몇 번째 인지)를 index로 하는 새 result 배열에, DAT의 index값(원래 value) 넣어주기 
	for (int x = 0; x < 7; x++) {
		int t = arr[x];
		result[bucket[t]--] = t;
	}
	return 0;
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

c++ 에서 사용하는 sort

	데이터 양이 적을 때	데이터 양이 많을 때
sort	quick	heap
stable sort	insert	merge

* sort는 quick + heap 의 구조로 만들어짐. (nlogn)

 

* 즉, count sort 로 구현하면 O(n)으로 구현 가능

 

 

반드시 필요한 헤더파일 !!! (sort를 사용하기 위해 )

#include<algorithm>

 

// 오름차순 
sort(배열의 포인터, 배열의 포인터 + 배열의 크기, 오름차순<자료형>());
sort(ptr, ptr + size, [less or greater]<int>());

// sort
int main() {
	int arr[6] = { 3,6,2,1,5,8 };
	// int 형
	sort(arr, arr + 6);					// 오름차순 (기본 default) :  뒤에 옵션으로 less<int>() 붙여도 됨 
	sort(arr, arr + 6, greater<int>());	// 내림차순	

	// string 형
	string str = "kevinchoi";
	sort(str.begin(), str.end());
	sort(str.begin(), str.end(), greater<char>());

	// 배열 string 형
	string brr[4] = { "kevin","bob","jane","kate" };
	sort(brr, brr + 4);
	sort(brr, brr + 4, greater<string>());

	vector<int>vect = { 6,3,4,6,5,2,1,9 };
	sort(vect.begin(), vect.end());
	sort(vect.begin(), vect.end(), greater<int>());

	vector<vector<int>>t = { {3,2},{1,3},{6,2} };	// 앞의 숫자를 기준으로 정렬
	sort(t.begin(), t.end());
	sort(t.begin(), t.end(), greater<vector<int>>());

	pair<int, int>p;
	vector<pair<int, int>>pp = { {8,2},{3,3},{5,2} };
	sort(pp.begin(), pp.end(), greater<pair<int, int>>());

	return 0;
}

 

 

 

 

#include<algorithm>
#include<vector>
bool compare(int front, int back) {
	if (front % 2 == 0 && back % 2 == 1)return true;
	if (front % 2 == 1 && back % 2 == 0)return false;
	return front > back;
}
int main() {
	int arr[7] = { 2,6,41,3,7,4,8 };
	sort(arr, arr + 7, compare);
	return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------

 

find union ) 

 

친구 묶는 프로그램 답)

 

#include <iostream>
using namespace std;
int vect[10];
int dat[10];
int cnt;
int getFind(int v)
{
	if (vect[v] == 0) return v;
	int ret = getFind(vect[v]);
	vect[v] = ret;
	return ret;
}
void setUnion(int t, int v)
{
	int t1 = getFind(t);
	int t2 = getFind(v);
	if (t1 == t2) return;
	vect[t2] = t1;
	//맨 처음 사용하는 수끼리 그룹 맺을때
	if (dat[t] == 0 && dat[v] == 0) cnt++;
	//둘다 처음 사용 수가 아닌 경우 그룹 맺을때
	if (dat[t] == 1 && dat[v] == 1) cnt--;
	dat[t] = 1;
	dat[v] = 1;
}
int main()
{
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int t, n;
	cin >> t >> n;
	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;
		setUnion(a, b);
	}
	cout << cnt;
	return 0;
}

 

 

근처자리 그룹으로 묶는 프로그램 ) 

 

#include <iostream>
using namespace std;
int vect[10];
int dat[10];
int cnt;
int getFind(int v)
{
	if (vect[v] == 0) return v;
	int ret = getFind(vect[v]);
	vect[v] = ret;
	return ret;
}
void setUnion(int t, int v)
{
	int t1 = getFind(t);
	int t2 = getFind(v);
	if (t1 == t2) return;
	vect[t2] = t1;
	//맨 처음 사용하는 수끼리 그룹 맺을때
	if (dat[t] == 0 && dat[v] == 0) cnt++;
	//둘다 처음 사용 수가 아닌 경우 그룹 맺을때
	if (dat[t] == 1 && dat[v] == 1) cnt--;
	dat[t] = 1;
	dat[v] = 1;
}
int main()
{
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int t, n;
	cin >> t >> n;
	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;
		setUnion(a, b);
	}
	cout << cnt;
	return 0;
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

우선순위 문제 

 

struct Node {
	int a;
	char ch;
};
priority_queue<Node> q;
Node vect[6] = {
	{ 8, 'A' },
	{ 7, 'B' },
	{ 9, 'C' },
	{ 7, 'A' },
	{ 7, 'Q' },
	{ 9, 'A' }
};
// 우선순위 조건							// sort의 compare와 순서 다름, (int t,int v)
bool operator<(Node v, Node t) {			// back 다음에 front 순서	// 꺽쇠는 오른쪽이 큰지 묻는 것임 . 
	// 1. 짝수 우선
	if (v.a % 2 == 1 && t.a % 2 == 0) return 1;
	if (v.a % 2 == 0 && t.a % 2 == 1) return 0;


	// 2. 문자 작은 것 우선
	if (v.ch < t.ch) return 1;
	if (v.ch > t.ch) return 0;

	// 3. 큰 숫자 우선
	return t.a > v.a;

	// 이걸 간단히 한 것 
	//if (v.ch > t.ch) return 1;
	//if (v.ch < t.ch) return 0;
	//return 0;
}
int main()
{
	for (int i = 0; i < 6; i++) {
		q.push(vect[i]);
	}
	while (!q.empty()) {
		cout << q.top().a << " " << q.top().ch << endl;
		q.pop();
	}
	return 0;
}