Insert or Merge

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N(100)N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification

For each test case, print in the first line either “Insertion Sort” or "Merge Sort"to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

Sample Output 2

Merge Sort
1 2 3 8 4 5 7 9 0 6

分析

本题关键在于对插入排序和归并排序的理解,并不一定定需要对依次对整个排序过程完全模拟

插入排序特点

  • 已经排好序的部分呈现为递增,并且从头开始直到非递增的部分以后就是未排序的,未排序的部分与原始序列相同
    • 实际上是向一个空序列中每次添加一个元素,然后对这个序列进行排序)

归并排序特点

  • 以length=1开始进行分组(实际上length为2才涉及到排序的问题),然后将排好序的组合并后再两两归并
    • 直到最终合并为一个单一的序列(length=n)
    • 题干声明本题有唯一解,所以在归并过程中一定会出现与partial result相同的序列

如何区分简单插入排序和非递归的归并排序

  • 插入排序:前面有序,后面没变化
  • 归并排序:分段有序(每个固定长度的归并段内均有序)

“捏软柿子”算法

  • 判断是否插入排序
    • 从左向右扫描,直到发现顺序不对,跳出循环
    • 从跳出地点继续向右扫描,与原序列比对,发现不同则判断为“非”
    • 循环自然结束,则判断为“是”,返回跳出地点
  • 如果是插入排序的话,则从跳出地点开始进行一趟插入

判断归并段的长度

  • 从头开始连续有序的子列长度
    • 反例:如果从开始扫描的话得出的归并段长度为4(1,2,8,9),但是明显后面以4为归并长度的子列不是有序的

2 1 8 9 6 5 3 4
1 2 8 9 5 6 3 4

  • 所有连续有序子列的最短长度?
    • 反例:这种情况续有序子列的最短长度为2(5,10),但从一个子段来看归并长度明显应该是4,之所以因为最后的子列元素没满。另外,即使不算最后一个子列,这种情况依然错误,因为这个算法是找最短长度,所以几乎一定会是2或1

4 2 1 3 13 14 12 11 8 9 7 6 10 5
1 2 3 4 11 12 13 14 6 7 8 9 5 10

  • 从原始序列出发,模拟归并排序并跟原始序列相比较,直到与原序列相等后再做一次归并
    • for(l=2;l<=N;l*=2);
    • 由于题目中给出的是排序过程中的结果,因此对于归并排序来说一般第一趟归并长度是2,所以每两个一组的数据一定是有序的
    • 继续判断归并段长度,判断在每两个一组的情况下组间是否有序,以1 2 3 4 11 12 13 14 6 7 8 9 5 10为例
      • 判断(2,3),(12,13),(7,8)之间是否有序,如果有序说明归并段长度为4也满足
      • 同理,继续往下判断归并段长度为8,……的情况

测试数据

  • 最小N的情况
    • 由于题目中明确了数据可以区分插入排序和归并排序,因此N最小为4
    • 插入排序的第1步,此时什么都没改变,与原序列相同
    • 归并排序的第1步,所有都变了
  • 尾部子列没有变化,但是前面变了的情况
    • 这种属于归并排序的情况,因此本题无法使用从后往前扫描发现顺序没变就认为是插入排序的算法(这种算法本来就完全错误)
    • 最大N的情况

ac代码(转)

#include<iostream>
#include<algorithm>
#define maxcount 105
using namespace std;
int n,initial[maxcount],partial[maxcount];
void IorM();
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>initial[i];
    for(int i=0;i<n;i++)cin>>partial[i];
    IorM();
    for(int i=0;i<n-1;i++)cout<<initial[i]<<' ';
    cout<<initial[n-1];
}
void IorM(){
    int i,j;        
    for(i=1;i<n&&partial[i-1]<=partial[i];i++);     //注意i的取值,这种情况下i取到的是正好是递增结束元素的下标
    for(j=i;j<n&&partial[j]==initial[j];j++);       //检查非递增部分partial是否和intial相同,如果相同说明是插入排序
    if(j==n){
        cout<<"Insertion Sort"<<endl;
        sort(initial,initial+i+1);                  //对0到i+1的initial排序,即相当于在i的基础上再进行一次插入
    }else{
        cout<<"Merge Sort"<<endl;
        int length=1,flag=1;                        //设置flag信号,当flag=1时说明结果还不相等,继续进行迭代
        while(flag){
            flag=0;
            for(i=0;i<n;i++)if(initial[i]!=partial[i])flag=1;
            length*=2;                              //对length进行处理,每次循环乘2
            for(i=0;i<n/length;i++)sort(initial+i*length,initial+(i+1)*length); //对每个相邻的length长度的子列进行归并
            sort(initial+n/length*length,initial+n); //对最后一个剩余的元素数量不满的组进行归并
        }
    }
} 

Insertion or Heap Sort

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. It involves the use of a heap data structure rather than a linear-time search to find the maximum.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N(100)N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

Sample Output 2

Heap Sort
5 4 3 1 0 2 6 7 8 9

ac代码

#include<iostream>
#include<algorithm>
#define Maxcount 105
using namespace std;
int n,init[Maxcount],partial[Maxcount],insort[Maxcount],hesort[Maxcount];
void IorH(),percdown(int,int);
bool insertion(),heap();
int main(int argc,char*argv[]){
    cin>>n;
    for(int i=0;i<n;i++)cin>>init[i];
    for(int i=0;i<n;i++)insort[i]=hesort[i]=init[i];
    for(int i=0;i<n;i++)cin>>partial[i];
    IorH();
}
void IorH(){
    if(insertion()){
        cout<<"Insertion Sort"<<endl;
        for(int i=0;i<n-1;i++)cout<<insort[i]<<' ';
        cout<<insort[n-1]<<endl;
    }else if(heap()){
        cout<<"Heap Sort"<<endl;
        for(int i=0;i<n-1;i++)cout<<hesort[i]<<' ';
        cout<<hesort[n-1]<<endl;
    }
}
bool insertion(){
    int i,j;
    for(i=1;i<n&&partial[i-1]<=partial[i];i++);
    for(j=i;j<n&&partial[j]==init[j];j++);
    if(j==n){
        sort(insort,insort+i+1);
        return true;
    }
    return false;
}
bool heap(){
    for(int i=n/2-1;i>=0;i--)percdown(i,n);
    for(int i=n-1;i>0;i--){
        int j,tmp=hesort[0];
        hesort[0]=hesort[i],hesort[i]=tmp;
        percdown(0,i);
        for(j=0;j<n&&hesort[j]==partial[j];j++);
        if(j==n){
            tmp=hesort[0];
            hesort[0]=hesort[i-1],hesort[i-1]=tmp;
            percdown(0,i-1);
            return true;
        }
    }
    return false;
}
void percdown(int root,int size){
    int parent,child,tmp=hesort[root];
    for(parent=root;parent*2+1<size;parent=child){
        child=parent*2+1;
        if(hesort[child+1]>hesort[child]&&child<size-1)child++;
        if(tmp>=hesort[child])break;
        else hesort[parent]=hesort[child];
    }
    hesort[parent]=tmp;
}

Sort with Swap(0, i)

Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification

Each input file contains one test case, which gives a positive N(105)N (≤10^5) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input

10
3 5 7 2 6 4 9 0 8 1

Sample Output

9

分析

表排序的物理排序(将序列分为环,根据环数计算交换次数)

  • 在计算环时,要将已经纳入某个环中的数记录下来。如果每次都重复计算的话可能会超时
  • 环的分类
    • 序列中只有单元环(没有多元环,此时每个数都已经在自己的位置上,不需要交换)
    • 序列中只有一个多元环(0一定在这个多元环中,此时只需计算环内的交换次数即可,不需要与别的环进行交换)
      • 此时总交换次数=多元环内交换次数=多元环元素个数-1
        • 多元环元素个数=n-单元环元素个数,因此总交换次数=n-single-1
    • 序列中存在多个多元环,此时要先将0与其他多元环元素进行一次交换,相当于把多个多元环组合为一个大的多元环
      • 多元环间交换次数=多元环个数-1
      • 此时总交换次数=多元环间交换次数+大多元环元素交换次数=多元环个数-1+多元环元素个数-1
        • 总交换次数=n-single-multiple-2
      • 0在第0个位置的时候,由于本题只能换0,所以必须将0换到其他的多元环中,此时0本身实际相当于一个多元环(multiple++)
        • 存在一种特殊情况:序列没有其他多元环,此时不需要交换,0也不需要看作多元环

ac代码

#include<iostream>
#define maxcount 105000
using namespace std;
int n,table[maxcount],flag[maxcount],swap0andi();
void swap(int*,int*);
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>table[i];
    cout<<swap0andi()<<endl;
}
void swap(int*num1,int*num2){
    int tmp=*num1;
    *num1=*num2,*num2=tmp;
}
int swap0andi(){
    int right=0,tmp,circle=0;
    for(int i=1;i<n;i++)if(table[i]==i)flag[i]=1,right++;
    if(!table[0]&&right<n-1){
        for(tmp=1;tmp<n&&flag[tmp];tmp++);
        swap(table[0],table[tmp]);
        circle++;
    }
    for(int i=0;i<n;i++)if(!flag[i]){
        tmp=i,flag[tmp]=1;
        for(int j=table[tmp];j!=tmp;j=table[j])flag[j]=1;
        circle++;
    }
    if(circle==0)return 0;
    else if(circle==1)return n-right-1;
    else return n-right+circle-2;
}