TIL (2022.04.03)

1. 선택정렬

앞에서부터 순서대로 보면서 앞에 있는 모든 원소가 정렬되어 있다는 가정하에 현재 원소의 위치를 찾는 것!

예를 들어, 1 3 5 2 4이런 배열이 있다고 생각해보자

1 3 5는 제대로 구현이 되어있으니 픽스, 2가 문제.

그러면 우선 앞의 것과 비교를 한다. 5가 더 크니까 한 칸 앞으로 보내주자.

1 3 2 5 4 가 될 것이다.

하지만 바꾼 이후에도 앞의 원소가 더 크므로 또 위치를 변경.

1 2 3 5 4가 된다. 이제는 4가 문제.

앞의 원소랑 비교했을 땐, 앞의 원소가 더 크니까

1 2 3 4 5 로 자리를 바꿔준다.

즉, 자리를 찾기 위해서 앞에 있는 원소들과 계속 비교를 해주면 된다.

N번째 원소를 삽입하기 위해서는 최대 n-1개의 원소가 이동해야하므로,
n(n-1)/2개의 이동 -> O(N^2)의 시간복잡도'

void insertionSort(){
    for(int i=1;i<n;i++){
        int j=i-1;
        // 기준점
        int idx=arr[i];
        while(j>=0 && arr[j]>idx){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=idx;
    }
}

2. 기수정렬

맨 뒤에 있는 자릿수부터 해당 자리수를 기준으로 정렬하는 것
예를 들어, 626 570 999 784 123 이 있다고 생각해보자.
그럼 제일 마지막 자리수부터 정렬한다.

570 123 784 626 999 1의 자리수 기준
123 626 570 784 999 10의 자리수 기준
123 570 626 784 999 100의 자리수 기준

각 자리수는 어떻게 구할까?
123을 예를 들자면 ->
마지막 자리는 모듈러 계산을 통해 123%10=3 을 얻을 수 있다.
2번째 자리는 123/10 = 12 -> 12%10=2 를 얻을 수 있다.
첫번째 자리는 12/10 => 1-> 1%10 =1 을 얻을 수 있다.

int digit(int num, int idx) {

    if(idx == 0)
        return num % 10;
    else
    // idx는 '/' 연산을 몇 번 할지 정해주는 것
        return digit(num / 10, idx - 1);
}

자 자리수를 얻는 것까지 했으니, 이젠 radixSort를 구현해보자.

// 100의 자리수까지만 있으니까 3번
for(int i=0;i<3;i++){
// 0~9까지
	vector<int> sorting[10];
    for(int j=0;j<arr.size();j++){
    	int eachNum = digit(arr[j],i);
        sorting[eachNum].push_back(arr[j]);
    }
    
    int idx=0;
    for(int j=0;j<10;j++){
    	for(int k=0;k<sorting.size();k++){
        	arr[idx++]=sorting[j][k];
        }
    }
}