本周将会介绍几种常见的排序算法。

简单排序

简单排序是几个简单的排序算法的统称，下面来一一介绍。

冒泡排序

冒泡排序的思想比较直观，每次循环时，会将数组（或链表）内相邻的两个元素进行比较，按照规定的递增（或递减）顺序向后移动，一直到重复到末尾，基本代码如下：

void Bubble_Sort(ElementType A[], int N) {
    for(P=N-1; P>=0; P--) {
        for(i=0; i<P; i++) {
            if(A[i] > A[i+1]) {
                Swap(A[i], A[i+1]);
            }
        }
    }
}

代码框架十分简单，但是这样会有一个问题，那就是待排序列在已经有序的情况下，依然会进行两次循环，尽管不会交换相邻元素的值，但是还是会进行判断，会白白浪费时间。仔细想一下，如果输入序列是有序的，那么元素的值一次也不会交换，根据这个特点，可以对上述的代码进行一点小优化，添加一个标志位，一次有序后就可以直接跳出循环了。具体代码如下：

void Bubble_Sort(ElementType A[], int N) {
    for(P=N-1; P>=0; P--) {
        flag = 0;
        for(i=0; i<P; i++) {
            if(A[i] > A[i+1]) {
                Swap(A[i], A[i+1]);
                flag = 1;
            }
        }
        if(!flag) break;
    }
}

按照上述代码的思路，可以较为清晰的分析出冒泡排序算法的时间复杂度：

最好的情况，序列为顺序序列， $T = O(N)$
最坏的情况，序列为逆序序列， $T = O(N^2)$

另外，对于冒泡排序而言，每一次冒泡结束（内层循环结束一轮）后都会有一个元素被放到这个序列有序后的最终位置上，而且，冒泡排序也不会交换相同元素的位置（使用 $>$ 而不是 $\geq$ ），所以冒泡排序是稳定的排序算法，再者，冒泡排序还有一个优点，即排序的方向是一定的，只会按照一个方向遍历存储数据的数据结构，这是其他排序算法无法达到的。

插入排序

插入排序有个很形象的例子，就是打扑克牌时“理牌”的过程，不过可能有点差别。区别在于，理扑克牌时，手上是没有牌的，而需要理的牌在牌堆里面，也就是说，有两个空间可以放牌，但插入排序实际上只使用了一个内存空间，这样的话，每一次插入时就需要先找到插入的位置了。
按照“理牌”的过程来描述就是：先摸一张牌，从后往前找到合适的插入位置，将比这张牌大的牌向后移（腾出位置），再将新牌插入到这个位置下即可。基本代码如下：

void Insertion_Sort(ElementType A[], int N) {
    for(P=1; P<N; p++) {
        temp = A[P];
        for(i=P; i>0 && A[i-1]>temp; i--) {
            A[i] = A[i-1];
        }
        A[i] = temp;
    }
}

插入排序和冒泡排序的时间复杂度类似：

最好的情况，序列为顺序序列， $T = O(N)$
最坏的情况，序列为逆序序列， $T = O(N^2)$

同时，插入排序也是稳定的排序算法。

时间复杂度下界

对于下标 $i < j$ ，如果 $A[i] > A[j]$ ，则称 $(i, j)$ 是一对逆序对（Inversion）如序列 ${2, 3, 1}$ 中， $(2, 1)$ 和 $(3, 1)$ 分别是一对逆序对，逆序对的个数称为逆序数，这与线性代数中的概念是一致的。

在冒泡排序和插入排序中，每次交换位置的两个相邻元素正好消去 1 个逆序对，那么它们的时间复杂度就是： $T(N, I) = O(N+I)$ ，其中 $I$ 是逆序对的对数。很明显，如果序列基本有序，则 $I$ 值可忽略不计，时间复杂度仅为 $T(N)$ ，此时算法既简单，又高效。

定理：对于任意N个不同元素组成的序列平均具有 $N(N-1)/4$ 个逆序对。

由上面的定理，我们可以得出：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为 $\Omega(N^2)$ 。这意味着，如果想要提高算法的效率，就得在每次交换元素时，不止消去 1 个逆序对，这就要求每次交换的两个元素要在序列中相隔的比较远。

希尔排序

希尔排序的主要目的就是每次交换元素时，通过消去多个逆序对来达到提升算法效率。其主要思想：先定义增量序列 $D_M > D_{M-1} > \dots > D_1 = 1$ ，然后对每个 $D_k$ 进行“ $D_k$ -间隔”排序（ $k=M, M-1, \dots,1$ ），值得注意的是，后面进行的“间隔”排序不会影响前面“间隔”排序的有序性，也即“ $D_k$ -间隔”有序的序列，在执行“ $D_{k-1}$ -间隔”排序后，仍然是“ $D_k$ -间隔”有序的。
原始希尔排序，增量依次减半， $D_M = \lfloor N/2 \rfloor, D_k = \lfloor D{k+1}/2 \rfloor$ ，此时最坏情况下的时间复杂度为 $T = \Theta(N^2)$ ，基本代码如下：

void Shell_Sort(ElementType A[], int N) {
    for(D=N/2; D>0; D/=2) {
        for(P=D; P<N; P++) {
            temp = A[P];
            for(i=P; i>=D && A[i-D]>temp; i-=D) {
                A[i] = A[i-D];
            }
            A[i] = temp;
        }
    }
}

在最坏的情况（每次进行间隔排序的序列都是有序的）下，希尔排序会退化成插入排序，原因在于增量元素不互质，则小增量可能根本不起作用。为了解决这个问题，引入了更多的增量序列：

Hibbard增量序列， $D_k = 2^k - 1$ ，这样保证了相邻增量元素互质，最坏情况下 $T = \Omega(N^{3/2})$ ，猜想 $T_{avg} = O(N^{5/4})$
Sedgewick增量序列， ${1, 5, 19, 41, 109, \dots}$ ，也即增量序列的每一个元素是由 $9 \times 4^i + 1$ 或 $4^i - 3 \times 2^i + 1$ 计算得到，猜想 $T_{avg} = O(N^{7/6}), T_{worst} = O(N^{4/3})$

由于希尔排序每次对增量序列进行排序，相邻的相等元素属于不同增量序列，则希尔排序可能会改变相等且相邻元素的相对位置，属于不稳定的排序。

选择排序

选择排序是一种简单直观的排序算法，基本工作原理是每一次从待排序的数据元素中选出最小（大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，重复此过程直到全部待排序的数据元素排完。

简单选择排序

简单选择排序的思路很简单，与选择排序的基本思想一致，基本代码如下：

void Selection_Sort(ElementType A[], int N) {
    for(i=0; i<N; i++) {
    //find the minimum from A[i] to A[n-1], and return to Position
        MinPosition = ScanForMin(A, i, N-1);
    //replace the minimum element to the last position of the ordered part
        Swap(A[i], A[MinPosition]);
    }
}

简单选择排序的时间复杂度主要有两个影响条件，第一个是查找最小值，第二个是交换，所以它的时间复杂度无论怎样都是 $T=\Theta(N^2)$ 。

堆排序

分析了简单选择排序算法的时间复杂度后，发现简单选择排序的时间都耗费在了查找最小值上，如果能把这一操作变快，那么简单选择排序的效率就能提高。根据选择排序的特点，每次查找的值必须是最小（大）值，这与小（大）根堆的性质是一致的，那么使用堆来进行元素的查找，每次弹出最小（大）值，就可以提升排序效率。基本代码如下：

void Heap_Sort(ElementType A[], int N) {
    BuildHeap(A);
    for(i=0; i<N; i++) {
        tempA[i] = DeleteMin[A];
    }
    for(i=0; i<N; i++) {
        A[i] = tempA[i];
    }
}

上述代码的过程比较简单，每次找出最小（大）元素后，保存在一个临时数组内，然后在将临时数组内的排序结果复制到原始数组中。这样即需要额外的空间（ $O(N)$ ）去存储这部分数据，又要额外的时间去复制元素。那么如何去避免这部分开销呢？请看下面的代码：

void Heap_Sort(ElementType A[], int N) {
    for(i=N/2; i>=0; i--) {
        PercDown(A, i, N);	//Build heap
    }
    for(i=N-1; i>0; i--) {
        Swap(&A[0], &A[i]);	//delete max
        PercDown(A, 0, i);
    }
}

按照上述代码，建立一个大根堆，排序开始后，交换大根堆最大元素与最末尾元素的值，完成后，将这个最大值剔除出堆，紧接着再调整为大根堆，重复执行上述操作。

定理：堆排序处理N个不同元素的随机排列的平均比较次数是 $2NlogN - O(N log logN)$

虽然堆排序给出最佳平均时间复杂度，但实际效果不如用Sedgewick增量序列的希尔排序。

归并排序

归并排序的核心就是有序子列的归并，首先，申请空间，保存合并后的有序序列，设定两个指针，最初位置分别为两个有序序列的起始位置，比较两个指针指向的元素，选择相对小的元素放到申请的空间内，并移动指针到下一位置，重复直至某一个子序列超出序列尾，接着将另一序列剩下的所有元素直接复制到申请空间的尾部。合并两个有序子列的基本代码如下：

void Merge(ElementType A[], ElementType TempA[], int L, int R, int RightEnd) {
    LeftEnd = R-1;	//Suppose two subsequences are side-by-side
    Tmp = L;	//initial position
    NumElements = RightEnd - L + 1;
    while(L <= LeftEnd && R <= RightEnd) {
        if(A[L] <= A[R]) TempA[Tmp++] = A[L++];
        else TempA[Tmp++] = A[R++];
    }
    // copy the rest straightly
    while(L <= LeftEnd) TempA[Tmp++] = A[L++];	
    while(R <= RightEnd) TempA[Tmp++] = A[R++];
    //copy the result to A[] from right to left
    for(i=0; i<NumElements; i++, RightEnd--) {
        A[RightEnd] = TempA[RightEnd]
    }
}

归并算法在实现的时候有两种不同的策略，下面先介绍递归。

递归

归并排序的递归算法的思想是基于分治法的，先将分开的子序列排好，在合并成一个大的序列。基本代码如下：

void MSort(ElementType A[], ElementType TempA[], int L, int RightEnd) {
    int Center;
    if(L < RightEnd) {
        Center = (L + RightEnd)/2;
        MSort(A, TempA, L, Center);
        MSort(A, TempA, Center+1, RightEnd);
        Merge(A, TempA, L, Center+1, RightEnd);
    }
}

基于分治法的归并排序递归算法的时间复杂度为 $T(NlogN)$ ，推导过程如下：
$\begin{align} T(N) & = 2 T(N/2)) + cN \\ & = 2\ (2T(N/2^2) + c N/2) + cN \\ & = \dots = 2^k * O(1) + ckN \\ & = O(NlogN) \end{align}$
可得 $T(N) = O(NlogN)$ ，这个时间复杂度是很“强”的😆，也即是说在任何情况下（无论好坏）都是 $NlogN$ ，另外，归并排序是稳定的排序算法。为了使它与上述其他排序算法的函数接口统一，再整理下代码：

void Merge_Sort_Recursion(ElementType A[], int N) {
    ElementType *TempA;
    TempA = malloc(N*sizeof(ElementType));
    if(TempA != NULL) {
        MSort(A, TempA, 0, N-1);
        free(TempA);
    } else Error("Insufficient Space.");
}

注意在上面的代码中，临时传递使用的数组是声明在Merge_Sort函数中的，这样做的好处就是避免了在MSort中重复声明和重复释放内存操作。

非递归

归并排序的非递归算法基本思想依然是分治法的思想，每次循环先归并相邻的两个子列，子列长度逐渐增加，直至最后左右两个子列之和大于序列总长度。基本代码如下：

void Merge_Sort_Non_Recursion(ElementType A[], int N) {
    int length;
    ElementType *TempA;
    length = 1; //initialize the length of subsequence
    TempA = malloc(N*sizeof(ElementType));
    if(TempA != NULL) {
        while(length < N) {
            Merge_pass(A, TempA, N, length);	//left
            length *= 2;
            Merge_pass(TempA, A, N, length);	//right
            length *= 2;
        }
    } else printf("Insufficient Space.\n");
}

/*Merge adjacent ordered subsequence in pairs accroding to the current 
length of subsequence*/
void Merge_pass(ElementType A[], ElementType TempA[], int N, int length) {
    int i, j;
    for(i=0; i<=N-2*length; i+=length) {
        Merge(A, TempA, i, i+length, i+2*length-1);
    }
    if(i+length < N) {
        //Merge the last two subsequence
        Merge(A, TempA, i, i+length, N-1); 
    } else {
        //only one subsequence last 
        for(j=i; j<N; j++) TempA[j] = A[j];	
    }
}

注意上述代码中的细节，Merge_pass是一个按照序列长度进行一次归并的函数，当序列长度发生变化的时候，将再次调用此函数，另外，在此函数内，for循环内归并的序列是前N/length - 1对，而不是N/length对，如果N是奇数，最后一个子列就被单独出来了，它与其他子列的长度不等，所以针对最后一个子列的处理，要与前面区分开来。再者，上述代码中length增长的倍数是2，理论上即是二路归并。

小结

归并排序算法的优点很明显，那就是在任何情况（无论好坏）下，其时间复杂度都是 $T(NlogN)$ ，同时，它还是稳定的排序算法，但是它有一个很明显的缺点，就是需要占用 $O(N)$ 大小的空间，并且在内存内要频繁的进行倒换操作，所以，一般内部排序中不会使用归并排序，外部排序会使用归并排序。

Homework

09-1 排序

这个题专门用来检测自己实现的排序算法，最好把老师讲了的都实现一下。

冒泡排序

#include <stdio.h>
#include <stdbool.h>
#define maxn 100005
int array[maxn], n;
void swap(int *p1, int *p2) {
    int t = *p1;
    *p1 = *p2;
    *p2 = t;
}
void bubble_sort(int *array, int n) {
    for(int i = n - 1; i > 0; i--) {
        bool flag = true;
        for(int j = 0; j < i; j++) {
            if(array[j] > array[j + 1]){
                swap(&array[j], &array[j + 1]);
                flag = false;
            }
        }
        if(flag) break;
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", array + i);
    }
    bubble_sort(array, n);
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
    return 0;
}

插入排序

#include <stdio.h>
#define maxn 100005
int array[maxn], n;
void insertion_sort(int *array, int n) {
    for(int i = 1; i < n; i++) {
        int tmp = array[i], j;
        for(j = i; j > 0 && tmp < array[j - 1]; j--) {
            array[j] = array[j - 1];
        }
        array[j] = tmp;
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", array + i);
    }
    insertion_sort(array, n);
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
    return 0;
}

希尔排序

#include <stdio.h>
#define maxn 100005
int array[maxn], n;
void insertion_sort(int *array, int n) {
    for(int i = 1; i < n; i++) {
        int tmp = array[i], j;
        for(j = i; j > 0 && tmp < array[j - 1]; j--) {
            array[j] = array[j - 1];
        }
        array[j] = tmp;
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", array + i);
    }
    insertion_sort(array, n);
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
    return 0;
}

堆排序

#include <stdio.h>
#include <stdbool.h>
#define maxn 100005
int array[maxn], n;
void swap(int *p1, int *p2) {
    int t = *p1;
    *p1 = *p2;
    *p2 = t;
}
void Percolatedown(int *heap, int pos, int size) {
    int parent, child, tmp = heap[pos];
    for(parent = pos; parent * 2 + 1 <= size - 1; parent = child) {
        child = parent * 2 + 1;
        if(child != size - 1 && heap[child] < heap[child + 1]) child++;
        if(tmp >= heap[child]) break;
        else heap[parent] = heap[child];
    }
    heap[parent] = tmp;
}
void heap_sort(int *array, int n) {
    for(int i = n / 2 - 1; i >= 0; i--) {
        Percolatedown(array, i, n);
    }
    for(int i = n - 1; i > 0; i--) {
        swap(&array[0], &array[i]);
        Percolatedown(array, 0, i);
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", array + i);
    }
    heap_sort(array, n);
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
    return 0;
}

归并排序

非递归

#include <stdio.h>
#include <stdlib.h>
#define maxn 100005
int array[maxn], n;
void merge(int *array, int *tmparr, int left, int right, int rightend) {
    int leftend = right - 1, tmp = left;
    int numofelements = rightend - left + 1;
    while(left <= leftend && right <= rightend) {
        if(array[left] < array[right]) tmparr[tmp++] = array[left++];
        else tmparr[tmp++] = array[right++];
    }
    while(left <= leftend) tmparr[tmp++] = array[left++];
    while(right <= rightend) tmparr[tmp++] = array[right++];
    for(int i = 0; i < numofelements; i++, rightend--) {
        array[rightend] = tmparr[rightend];
    }
}
void merge_pass(int *array, int *tmparr, int n, int length) {
    int i, j;
    for(i = 0; i <= n - 2 * length; i += (2 * length)) {
        merge(array, tmparr, i, i + length, i + 2 * length - 1);
    }
    if(i + length < n) merge(array, tmparr, i, i + length, n - 1);
    else for(j = i; j < n; j++) tmparr[j] = array[j];
}
void merge_sort(int *array, int n) {
    int *tmparr;
    tmparr = (int*)malloc(n * sizeof(int));
    if(tmparr != NULL) {
        int length = 1;
        while(length < n) {
            merge_pass(array, tmparr, n, length);
            length *= 2;
            merge_pass(tmparr, array, n, length);
            length *= 2;
        }
        free(tmparr);
    } else return;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", array + i);
    }
    merge_sort(array, n);
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
    return 0;
}

递归

#include <stdio.h>
#include <stdlib.h>
#define maxn 100005
int array[maxn], n;
void merge(int *array, int *tmparr, int left, int right, int rightend) {
    int leftend = right - 1, tmp = left;
    int numofelements = rightend - left + 1;
    while(left <= leftend && right <= rightend) {
        if(array[left] < array[right]) tmparr[tmp++] = array[left++];
        else tmparr[tmp++] = array[right++];
    }
    while(left <= leftend) tmparr[tmp++] = array[left++];
    while(right <= rightend) tmparr[tmp++] = array[right++];
    for(int i = 0; i < numofelements; i++, rightend--) {
        array[rightend] = tmparr[rightend];
    }
}
void msort(int *array, int *tmparr, int left, int rightend) {
    int center;
    if(left < rightend) {
        center = (left + rightend) / 2;
        msort(array, tmparr, left, center);
        msort(array, tmparr, center + 1, rightend);
        merge(array, tmparr, left, center + 1, rightend);
    }
}
void merge_sort(int *array, int n) {
    int *tmparr;
    tmparr = (int*)malloc(n * sizeof(int));
    if(tmparr != NULL) {
        msort(array, tmparr, 0, n - 1);
        free(tmparr);
    } else return;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", array + i);
    }
    merge_sort(array, n);
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
    return 0;
}

09-2 Insert or Merge

这个题形式简单，但是要想得满分，必须得对插入排序跟归并排序都很了解才行。

题目要求输出两样东西：

判断属于那一种排序

然后输出再进行下一次这种排序后所得的序列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 105
int tar[maxn], arr[maxn], tmparr[maxn], n;
bool issame(int *a) {
    for(int i = 0; i < n; i++) {
        if(a[i] != tar[i]) return false;
    }
    return true;
}
void printarray(const int *array, int size) {
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
}
void insert_pass(int *array, int pos) {
    int tmp = array[pos], j;
    for(j = pos; j > 0 && tmp < array[j - 1]; j--) {
        array[j] = array[j - 1];
    }
    array[j] = tmp;
}
bool isinsert(int *array, int n, int *round) {
    for(int i = 1; i < n; i++) {
        insert_pass(array, i);
        if(issame(array)) {
            *round = i + 1;
            return true;
        }
    }
    return false;
}
void merge(int *array, int *tmparr, int left, int right, int rightend) {
    int leftend = right - 1, tmp = left;
    int numofelements = rightend - left + 1;
    while(left <= leftend && right <= rightend) {
        if(array[left] < array[right]) tmparr[tmp++] = array[left++];
        else tmparr[tmp++] = array[right++];
    }
    while(left <= leftend) tmparr[tmp++] = array[left++];
    while(right <= rightend) tmparr[tmp++] = array[right++];
    for(int i = 0; i < numofelements; i++, rightend--) {
        array[rightend] = tmparr[rightend];
    }
}
void merge_pass(int *array, int *tmparr, int n, int length) {
    int i, j;
    for(i = 0; i <= n - 2 * length; i += (2 * length)) {
        merge(array, tmparr, i, i + length, i + 2 * length - 1);
    }
    if(i + length < n) merge(array, tmparr, i, i + length, n - 1);
    else for(j = i; j < n; j++) tmparr[j] = array[j];
}
void merge_sort(int *array, int n) {
    int *tmparr;
    tmparr = (int*)malloc(n * sizeof(int));
    if(tmparr != NULL) {
        int length = 1;
        while(length < n) {
            merge_pass(array, tmparr, n, length);
            length *= 2;
            if(issame(tmparr)) {
                merge_pass(tmparr, array, n, length);
                printarray(array, n);
                break;
            }
            merge_pass(tmparr, array, n, length);
            length *= 2;
            if(issame(array)) {
                merge_pass(array, tmparr, n, length);
                printarray(tmparr, n);
                break;
            }
        }
        free(tmparr);
    } else return;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        tmparr[i] = arr[i];
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &tar[i]);
    }
    int round = 0;
    if(isinsert(tmparr, n, &round)) {
        printf("Insertion Sort\n");
        insert_pass(tmparr, round);
        printarray(tmparr, n);
    } else {
        for(int i = 0; i < n; i++) tmparr[i] = arr[i];
        printf("Merge Sort\n");
        merge_sort(tmparr, n);
    }
    return 0;
}

/*
samples:
in:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
out:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

in:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
out:
Merge Sort
1 2 3 8 4 5 7 9 0 6
*/

09-3 Insertion or Heap Sort

这个题与上题类型一致，只不过把归并排序换成了堆排序。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 105
int tar[maxn], arr[maxn], tmparr[maxn], n;
void swap(int *p1, int *p2) {
    int t = *p1;
    *p1 = *p2;
    *p2 = t;
}
bool issame(int *a) {
    for(int i = 0; i < n; i++) {
        if(a[i] != tar[i]) return false;
    }
    return true;
}
void printarray(const int *array, int size) {
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
}
void insert_pass(int *array, int pos) {
    int tmp = array[pos], j;
    for(j = pos; j > 0 && tmp < array[j - 1]; j--) {
        array[j] = array[j - 1];
    }
    array[j] = tmp;
}
bool isinsert(int *array, int n, int *round) {
    for(int i = 1; i < n; i++) {
        insert_pass(array, i);
        if(issame(array)) {
            *round = i + 1;
            return true;
        }
    }
    return false;
}
void Percolatedown(int *heap, int pos, int size) {
    int parent, child, tmp = heap[pos];
    for(parent = pos; parent * 2 + 1 <= size - 1; parent = child) {
        child = parent * 2 + 1;
        if(child != size - 1 && heap[child] < heap[child + 1]) child++;
        if(tmp >= heap[child]) break;
        else heap[parent] = heap[child];
    }
    heap[parent] = tmp;
}
void heap_sort(int *array, int n) {
    for(int i = n / 2 - 1; i >= 0; i--) {
        Percolatedown(array, i, n);
    }
    int i;
    for(i = n - 1; i > 0; i--) {
        if(issame(array)) break;
        swap(&array[0], &array[i]);
        Percolatedown(array, 0, i);
    }
    swap(&array[0], &array[i]);
    Percolatedown(array, 0, i);
    printarray(array, n);
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        tmparr[i] = arr[i];
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &tar[i]);
    }
    int round = 0;
    if(isinsert(tmparr, n, &round)) {
        printf("Insertion Sort\n");
        insert_pass(tmparr, round);
        printarray(tmparr, n);
    } else {
        for(int i = 0; i < n; i++) tmparr[i] = arr[i];
        printf("Heap Sort\n");
        heap_sort(tmparr, n);
    }
    return 0;
}

/*
samples:
in:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
out:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

in:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9
out:
Heap Sort
5 4 3 1 0 2 6 7 8 9
*/