merge sort

void MERGE(int A[], int p, int q, int r)
{
    int n_1 = q - p + 1;
    int n_2 = r - q;
    int* L = new int[n_1 + 2];
    int* R = new int[n_2 + 2];
    for (int i = 1; i <= n_1; i++)
    {
        L[i] = A[p + i - 1];
    }
    for (int j = 1; j <= n_2; j++)
    {
        R[j] = A[q + j];
    }
    L[n_1 + 1] = 10000000;
    R[n_2 + 1] = 10000000;
    int i = 1;
    int j = 1;
    for (int k = p; k <= r; k++)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
    }
    delete[] L;
    delete[] R;
}

void MERGE_SORT(int A[], int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        MERGE_SORT(A, p, q);
        MERGE_SORT(A, q + 1, r);
        MERGE(A, p, q, r);
    }
}

#include<queue>

template<typename T>
void mergesort(T a[], int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = (low + high) / 2;
        mergesort(a, low, pivot);
        mergesort(a, pivot + 1, high);

        int i = low, j = pivot + 1;
        queue<int>arr;

        while ((i <= pivot) && (j <= high))
        {
            if (a[i] <= a[j])
            {
                arr.push(a[i]);
                i++;
            }
            else
            {
                arr.push(a[j]);
                j++;
            }
        }

        while (i <= pivot)
        {
            arr.push(a[i]);
            i++;
        }

        while (j <= high)
        {
            arr.push(a[j]);
            j++;
        }

        for (int i = low; i <= high; i++)
        {
            a[i] = arr.front();
            arr.pop();
        }
    }
}

quick sort

template<typename T>
void quicksort(T A[], int start, int end)
{
    if (start < end)
    {
        int x = A[end];
        int i = start - 1;

        for (int j = start; j < end - 1; j++)
        {
            if (A[j] <= x)
            {
                i++;
                swap(A[i], A[j]);
            }
        }
        swap(A[i + 1], A[end]);
        int q = i + 1;
        quicksort(A, start, q - 1);
        quicksort(A, q + 1, end);
    }
    return;
}

shell sort

삽입 정렬의 응용판 $h = 3h' +1$

template<typename T>
void shell_sort(T a[], int num)
{
    int h =1;

    while(h < num/2)
    {
        h = 3*h+1;
    }
    while(h > 1)
    {
        h = h/3;

        for (int i = h ; i < num ; i++ )
        {
            T item = a[i];
            int j = i-h ;
            while (j >= 0 && item < a[j])
            {
                a[j + h] = a[j];
                j = j-h;
            }
            a[j + h] = item;
        }
    }
}

HEAP SORT

parent는 실제로 사용하지는 않음 실제 과정은 MAX_HEAPIFY와HEAPSORT 두개로 나타낼수있음

int parent(int i)
{
    return i / 2;
}

int left(int i)
{
    return 2 * i;
}


int right(int i)
{
    return 2 * i + 1;
}

void MAX_HEAPIFY(int A[], int i, int heapsize) //I인덱스의 노드가 자식 노드보다 작을 때 이를 밑으로 내려 힙트리 구조를 만든다 
{
    int l = left(i);
    int r = right(i);
    int largest;
    if (l <= heapsize && A[l] > A[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if (r <= heapsize && A[r] > A[largest])
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(A[i], A[largest]);
        MAX_HEAPIFY(A, largest, heapsize);
    }
}

void BUILD_MAX_HEAP(int A[], int n) //전체 배열을 힙트리로 나타내기 위한 함수
{
    int heapsize = n;
    for (int i = n / 2; i >= 1; i--)
    {
        MAX_HEAPIFY(A, i, heapsize);
    }
}

void HEAPSORT(int A[], int size)
{
    int* B = A - 1;//C에 맞게 인덱스값을 하나씩 내린다
    BUILD_MAX_HEAP(B, size);
    int heapsize = size;
    for (int i = size; i > 0; i--) 
    {
        swap(B[1], B[i]);
        heapsize--;
        MAX_HEAPIFY(B, 1, heapsize);

    }
}