[바킹독 실전 알고리즘] 강의 노트 _0x0F강 정렬2_Counting sort, Radix sort, STL sort()

바킹독 실전 알고리즘 강의를 듣게 되어서 강의 필기를 할겸 정리용으로 글 씁니다. 저작권 문제시 삭제 하겠습니다.

1. Counting sort

: 각 수의 등장 횟수만 세서 정렬하는 것.

 

정렬 중에 아주 쉬움! 하지만 만능은 아님.=> 배열의 크기가 한정적이라 수의 범위가 너무 넓으면 사용 불가.

 

수의 범위가 1000만 이하면 counting sort 사용하고 그렇지 않은 경우는 쓰지 말것. 

 

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int arr[1000001] = {};
	int tmp[1000001];
	for (int i = 0; i < n; i++)
	{
		cin >> tmp[i];

		
	}

	for (int i = 0; i < 1000001; i++)
	{
		if (tmp[i] == i)
		{
			arr[i]++;
		}
	}

	for (int i = 0; i < 1000001; i++)
	{
		if (arr[i] != 0)
		{
			cout << arr[i] << "\n";
		}
	}
}

---

 

2. Radix Sort (기수정렬)

: 자릿수로 정렬하는 알고리즘

=> counting sort를 수의 최대 자릿수 d만큼 하는것.

 

처음에는 1의 자리 수와 index가 같은 곳에 수를 넣음.

그리고 다시  꺼내서 배열로 만듦.(수가 1의 자리로 재배열 됨.)

 

10의 자리 수와 index가 같은 곳에 수를 넣음(10의 자리가 같은 수 끼리는 1의 자리 정렬을 따름.) 

그리고 다시 꺼내서 배열로 만듦(수가 10의 자리 순으로 재배열됨.)

 

⚠️라딕스 소트는 코테에서 구현해야 하는 경우가 아예 없음.

 

---

3. STL sort : 최악의 경우에도 O(nlogn)을 보장함. 

코테에서 정렬을 직접 짜고 있으면 흑우에요.음머~

 

단, STL sort는 stable sort가 아님! 동일한 값 사이의 우선순위를 보장해주지 않음.

=> 이때는 stable_sort()사용하면 됨. 

 

 

1. 비교 함수를 내가 정해서 넘겨 줄 수 있음.

bool cmp (int a, int b){

	if(a%5!=b%5) 
    {
    	return a%5 < b%5;
    }
    else {
    	return a<b;
     }
   
   }
   
   int a[7]={1,2,3,4,5,6,7};
   sort(a,a+7,cmp);

 

 

2. 주의 ) 비교함구는 두값이 같을 때 혹은 우선 순위가 같을때 false 반환 

bool cmp (int a, int b)
{

	if(a>=b) retrurn true;
    return false;


} // 이런 방식은 좋지 않음


bool cmp(int a, int b)
{	
	return a>b;

}// 대신 이런 방식으로 적기!

 

 

3. 주의 ) 비교함수의 인자로 STL혹은 클래스 객체를 전달시 reference를 사용.

=> 값 복사 대신!!!! 주소로

bool cmp(const string&a, const string& b)
{
 	return a.back()<b.back();
    
 }