알고리즘이론 - 정렬 (Sorting) - 미완

0. 정렬 알고리즘 (Sorting Algorithms)
 - 대부분이 O(n^2)과 O(nlogn)의 사이의 점근적 복잡도를 가진다.
 - Input(입력)이 특수한 성질을 만족하는 경우에는 O(n)의 복잡도를 가지는 Sort도 가능하다.

* Input : -O(n)과 O(n) 사이의 정수


1. 선택 정렬 ( Selection Sort )
- 루프를 돌면서 최대값을 가진 원소를 찾아 맨 오른쪽 원소를 교환하고 맨 오른쪽 원소를 정렬할 범위에서 제외 시킨다.
- 정렬할 범위에 원소의 갯수가 하나의 원소일 때까지 루프를 반복한다.

수행시간 : (n-1) + (n -2 ) + ... + 2 + 1 = Θ(n^2)

-PseudoCode :
selectionSort(A[],n) //A[1...n]을 정렬한다.
{
    for last←n dow n to 2
    {
        k ← theLargest(A, last);    //A[1...last] 중 가장 큰 수 A[k]를 찾기
        A[k] ↔ A[last];               //A[k]와 A[last]의 값을 교환 (큰수를 찾은 값과 정렬할 대상의 맨 오른쪽을 교체)
    }
}
theLagest(A[], last)    // A[1... last] 중 가장 큰 원소의 위치를 반환함
{
    largest ← 1;           //
    for i ← 2 to last
        if( A[i] > A[largest] ) then largest ← i ;
    return largest;    //순서값 반환
} 

2. 버블 정렬 ( Bubble Sort )
- 크게 2개의 루프로 구성
- 삽입정렬과 동일하게 처음부터 끝까지 루프를 실행 (n-1 번)
- 왼쪽부터 이웃한 쌍들을 비교해 왼쪽이 오른쪽 보다 작으면 순서를 바꾼다.

- 수행시간  = Θ(n^2)

-PseudoCode :
bubbleSort(A[], n) // A[1...n]을 정렬 한다.
{
    for last ← n downto 2     //n 이 2가 될때까지 감소하면서 반복 (n-1번)
        for i ← 1 to last -1     //i 가
            if(A[i] > A[i+1]) then A[i] ↔ A[i+1];
}

2.1 버블정렬 응용
- 원소가 이미 정렬되어있을때 계속적으로 정렬 하는 것을 막기 위해
- 자리 이동이 일어나지 않으면 정렬된것으로 간주하고 함수를 종료

- 수행시간 : 이미 정렬이 되어있을경우  Θ(n)

-PseudoCode :
bubbleSort(A[], n) // A[1...n]을 정렬 한다.
{
    for last ← n downto 2 {     //n 이 2가 될때까지 감소하면서 반복 (n-1번)
        sorted ← TRUE;
        for i ← 1 to last -1 {     //i 가
            if(A[i] > A[i+1]) then
             {    
                A[i] ↔ A[i+1];
                sorted ← FALSE;
            }
        }
        if(sorted = TRUE ) then return;
    }
}

3. 삽입 정렬 ( Insertion Sort )
- 이미 정렬된 i개의 원소를 같는 배열에 원소 하나를 더하여 정렬된 i+1개의 배열을 만드는 과정을 반복하여 정렬
- 선택정렬, 버블 정렬과는 상반되게 배열을 줄여나가는 것이 아닌 늘려가면서 정렬한다.

수행시간 : 정렬이 전혀 안되어 있는 최악의 경우나 보통 일반적인 경우 Θ(n^2)의 성능이지만
               정렬이 거의 되어있거나 정렬이 이미 되어 있을경우 Θ(n)에 가까운 시간이 든다.

-PseudoCode :
insertionSort(A[], n)
{
    for i ← 2 to n {
        loc ← i -1;
        newItem ← A[i];
        
        while(loc >=  1 and newItem < A[loc]){
            A[loc+1] ← A[loc];
            loc--;
        }
        A[loc+1] ← newItem;
    }
}

4. 병합 정렬 ( Merge Sort )
- 입력된 값을 반으로 나눈다.
- 전반부와 후반부로 나누어진 값을 다시 병합 정렬을 한다.
- 나눠서 정렬한 값을 합친다.
- 재귀적으로 반복.

수행시간 : Θ(nlogn)
최악의 경우 T(n)= 2T(n/2) +  Θ(nlogn)

!. T(n) = Θ(n^p)(p는 상수) => T(2n) = Θ((2n)^p) = 2^p Θ(n^p)= Θ(n^p)

PseudoCode :
mergeSort ( A[], p , r )
{
    if(p < r) then {
    q ← | (p+r)/2 |; //p,r 의 중간 지점 계산 하여 q에 넣음
    mergeSort(A,p,q);    //전반부 정렬
    mergeSort(A,q+1,r);  //후반부 정렬
    merge(A,p,q,r);     //병합
    }
}

merge(A[], p,q, r)
{
    //A[p ... q] 와 A[q+1 ... r]을 병합하여 정렬된 상태로 만든다.
    //A[p ... q] 와 A[q+1 ... r]은 각각 이미 정렬 되어 있다.
    i ← p; j ← q+1; t ← 1;
    while(i <= q and j <= r ){
       if(A[i] <= A[j])
        then temp[t++] ← A[i++];
        else temp[t++] ← A[j++]; 
    }
    while (i <= q)
        tmp[t++] ← A[i++];
    while (j <= r)
        temp[t++] ← A[j++];
    i ← p; t ← 1;
    while(i <= r)
        A[i++] ← tmp[t++];
}

5. 퀵 정렬 ( Quick Sort )
- 평균적으로 가장 좋은 성능을 가지는 정렬 알고리즘.

수행시간 :
 이상적인 경우 (분할이 항상 반반씩 균등하게 되는 경우) : T(n) = 2T(n/2) + Θ(n) => Θ(nlogn)
 최악의 경우 (한쪽은 하나도 없고 다른 쪽에 몰리도록 분할되는 경우) : T(n) = T(n-1) + Θ(n) => Θ(n^2)
 평균적인 경우 () :
 
PseudoCode :
quickSort(A[], p, r)    // A[p ... r]을 정렬한다.
{
    if(p < r ) then
    {
        q ← partition( A, p, r);        //분할
        quickSort(A, p, q-1);          //왼쪽 부분 배열 정렬
        quickSort(A, q+1, r);           //오른쪽 부분 정렬
    }
}

partition(A[], p, r)
{    
    x ← A[r];    //기준 원소를 정함 
    i ← p-1;      //i는 1구역의 끝지점
    for j ← p to r-1        //j는 3구역의 시작지점
        if( A[j] <=  x )    then A[++i] ↔ A[j];     // i 값을 증가 시킨후 A[i] ↔ A[j] 교환
    
    A[i+1] ↔ A[r];        //기준 원소와 2구역 첫 원소를 교환
    return i+1;
}
    
6. 힙 정렬 ( Heap Sort )

7. 기수 정렬 ( Radix Sort )

8. 계수 정렬 ( Counting Sort )