대엉코딩

0. 알아보기전에....

 - 지금까지  insertion sort,  quick sort, merge sort, heap sort 등....

    에 대해서 알아보았습니다.

 - 이러한 sorting 알고리즘들은 모두 두 수의 대소비교(key value에 대한) 를 하여 sort를 하는 class 의 알고리즘입니다.

 - 두 수의 크기비교를 통해 정렬하는 알고리즘은 최적의(optimal) 알고리즘은 O(nlogn) 이라는 것도 확인 하였습니다.

1. radix sort (기수정렬)

 - 먼저 언급하자면 , 이 sorting 알고리즘은 O(n) 이라는 수행시간을 가집니다.

 - ?????? 최적은 O(nlogn) 이라는 것도 증명 하였는데 어떻게 O(n)에 수행하는 sorting 알고리즘이?!

 - 그 이유는  크기비교가 아닌 다른 연산을 사용하기 때문에 class가 다른 algorithm이기 때문입니다.

 - 즉 , 두 수간의 대소비교를 통한 어떠한 방법으로 정렬을 하는 것이 아니라는 뜻이죠

2. Strategy 

 - 그럼 어떻게 할 것인가.......?

 - 선생님이 50명의 학생의 시험지를 점수별로 정렬을 시키고 싶은 상황이라고 해보자. (점수는: 0~99 <편의상>라 하자)

 - 일단, 0.1.2.3.....9 까지가 적혀있는 박스 10개를 준비하자.

 - 그리고 1의자리 수 를 기준으로 박스에 담자.

 - 그 후 0번 박스부터 9번 박스까지 들어있는 종이를  다시 하나의 뭉텅이로 합친 후

 -  이제 10의자리 수 를 기준으로 다시 0~9번 박스에 나누어 담자.

 - 모든 점수는 최대 2자리 수 이므로 2번의 이 작업을 수행 하면 sorting이 완료 된 상태이다.

 - 여기서 생각해보면 박스에 맞는 숫자를 담았을 뿐 두 수끼리의 비교하는 연산은 수행하지 않았다 !

 - 이렇게 할 수 있었던 이유는 무엇 일까? 자료에 대한 정보가 더 있었기 때문에 가능했다.

    (이 경우에는 점수 의 범위를 추가적으로 알고 있었다.)

 - **stable**

  : 이 알고리즘의 핵심 property 중 하나는 위에서(위의 상자부터) 순서대로(차례대로) 처리한다는 것

    이럴경우 stable하다고 이야기 한다.

    (즉, 같은 key값을 가진 input data가 여러개 있을 때 그 때 순서가 입력 순서와 같을 것을 보장한다는것)

     --각 단계를 수행 할 때 ! (각 단계는 stable 해야한다.)

3. Algorithm

 <list>이용

4. Analysis

 - distribute  --> Θ(n)  (숫자보고 통에넣고.....n번 수행)

 - combine  -->Θ(n) (list 내용을 하나로)

 - 이 작업을 몇번 수행 하느냐? 4자리수이면 4번....... 즉 자리수 (d) 만큼 (linear in n)

 - O(n)

1. 삽입정렬(insertion sort) 란?

 - 각 단계 마다 하나의 원소를 그 앞의 원소들과 비교를 해서 자신의 자리를 찾아 가는 것이다.

 - 첫 번째 원소는 처음에는 혼자이므로 그 자체로 정렬된 상태이고 두번째 원소부터 비교를 하며 정렬을 한다

 - 첫번째 와 두번째 원소를 비교를 제대로 했다면 3번째 원소를 정렬 할때는 3번째 원소 앞쪽은 정렬이 되어있는 상태일 것 이다.

 - 그럼 세번째 원소가 이제 자신의 자리를 찾으러 갈 것이고 네번째 원소가 비교를 시작하려 할 때는 앞의 3개의 원소는 정렬된 상태

 - 그리고 비교를 해가면서 원소의 자리가 바뀔 수 있기 때문에 자신의 차례때 배정받은 위치가 최종출력의 위치는 아니다.

2. 최악의 경우 (worst case) 

 - 키 오름차순 정렬을 하고 싶다고 가정했을 때, 계속 키가 제일 작은 사람이 차례대로 들어오는 것이다.

   ( 즉, 입력이 역순으로 정렬되어 있을 때)   -->  Θ(n^2)

3. 평균의 경우 (Average Analysis)

 - 각 자리에 들어갈 확률은 모두 같다고 가정 (1/i+1) -->>내가 원소로 들어갔을 때 그자리도 포함 i+1

 - step i에서 평균 i/2의 연산

 - 평균 분석의 경우 대략 n^2/4 정도 이다. 

4.특징

 - input의 크기가 적을 때에 한정해서 매우 빠르다고 알려져있다.

 - 한번에 잘못된 위치를 하나만 수정할 수 있는 제한적인 조건 내에서는 최적의 알고리즘 이다.

5. 구현 (key값을 그냥 입력받은 int의 수라고 가정하고 , 그냥 vector<int>의 각 index에 해당하는 값을 통한 정렬을 구현)