PAT Advanced 1089 Insert or Merge: More Iterations Until Different

Overview

We can direct simulate to solve PAT 1089 Insert or Merge or by linear scanning from back to front. Next we run more iterations to find a different sequence.

PAT Advanced 1089 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). 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 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 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

Solution Analysis: Need More Iterations Until Different

1) We can directly simulate the process of the Insertion Sort and Merge Sort and compare the partially sorted array after each iteration with the partially sorted array given by the input, once we find the same one, we can decide which sort is applied to the original input and run one more iteration. Before the accepted source code is given out, several vague points in the description need to be given first to clarify things:

  1. One iteration for Insertion Sort means one more number in the remaining unsorted portion is handled and inserted in the sorted part.
  2. One iteration for Merge Sort is different from Insertion Sort and it means all the small subarrays of length (2, 4, 8…etc) need to be  sorted. For example, at iteration 1, all subarrays of size 2 are sorted, if we run one more iteration, then all the sub arrays of size 4 (except the last one) all should be sorted. My first interpretation of such an iteration for merge sort, is one of the subarray of some size (say 4) should be sorted and it turns out to be wrong.
  3. One iteration should lead to a different sequence, it is possible that after one more iteration, the sequence actually remains to be the same as the one after last iteration. Such iteration cannot be counted. That is, we need to run more iterations until we find a different sequence and output the different one. This is the real requirement and clearer one, it is very very misleading in the problem description by saying run one more iteration. And this is why some people cannot pass the 2nd test case (index starts from 0) which worth 1 mark.

The following is the C++ code accepted by PAT OJ to successfully pass this Insert or Merge problem after which I will give improvements:

#include <cstdio>
#include <algorithm>

int num1[105];
int num2[105];
int partial[105];

bool comp(int a[], int b[], int n) {
	for (int i = 0; i < n; ++i) if (a[i] != b[i]) return false;
	return true;
}
bool tryInsertionSort(int a[], int n, int partial[]) {
	int i = 0;
	bool flag = comp(a, partial, n);
	for (i = 1; i < n & !flag; ++i) {
		for (int j = i - 1; j >= 0; --j) {
			if (a[j + 1] < a[j]) std::swap(a[j + 1], a[j]);
			else break;
		}
		flag = comp(a, partial, n);
	}
	if (flag) {
		bool keepGoing = true; // tricky!
		while (keepGoing) {
			for (int j = i - 1; j >= 0; --j)
				if (a[j + 1] < a[j]) {
					std::swap(a[j + 1], a[j]);
					keepGoing = false;
				}
				++i;
		}
	}
	return flag;
}
void printArray(int a[], int n) {
	if (n <= 0) return;
	printf("%d", a[0]);
	for (int i = 1; i < n; ++i) printf(" %d", a[i]);
	printf("\n");
}
void merge(int a[], int len1, int b[], int len2) {
	int i = 0, j = 0, k = 0;
	while (i < len1 && j < len2) {
		if (a[i] < b[j])
			num1[k++] = a[i++];
		else
			num1[k++] = b[j++];
	}
	while (i < len1) num1[k++] = a[i++];
	while (j < len2) num1[k++] = b[j++];
	for (int t = len1 + len2 - 1; t >= 0; --t) a[t] = num1[t];
}
bool tryMergeSort(int a[], int n, int partial[]) {
	int len = 0;
	bool flag = false;
	for (len = 1; len < n && !flag; len *= 2) {
		for (int i = 0; i + len < n; i += 2 * len) {
			merge (&a[i], len, &a[i + len], std::min(n - i - len, len));
		}
		flag = comp(a, partial, n) ;
	}
	for (int i = 0; i + len < n ; i += 2 * len) {
		merge (&a[i], len, &a[i + len], std::min(n - i - len, len));
	}
	return true;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", num1 + i), num2[i] = num1[i];
	for (int i = 0; i < n; ++i) scanf("%d", partial + i);

	int ret = tryInsertionSort(num1, n, partial);
	if (ret) {
		printf("Insertion Sort\n");
		printArray(num1, n);
	}
	else {
		tryMergeSort(num2, n, partial);
		printf("Merge Sort\n");
		printArray(num2, n);
	}
	return 0;
}

I actually code up real Insertion Sort and the bottom up Merge Sort from scratch and there are actually several improvements or more convenient tricks we can play during a real PAT test:

  1. You can use std::sort to replace the real Insertion Sort (swap) or Merge Sort (merge) operations to sort the subarray so you can save a bit of time during a real test.
  2. The above simulation works because of the small size of the input. For more efficient approach to detect Insertion Sort, we can actually start from the tail of the partial array and compare it with the original array one number by one number until we find the different one say A[d], then if A[0..d] is sorted, it must be Insertion Sort, we run one more iteration to insert A[d + 1] into the sorted portion. If not, then it is Merge Sort (it is guaranteed that there is a unique sort). This could be done in O(N) time
  3. If we detect it is a Merge Sort by detecting it as not an Insertion Sort. We need to determine the length of the sorted subarray and run next iteration to sort all the subarrays of length twice many as the detected length. This could be done by trying out length sequence 2, 4, … logN sequence and detect whether all of the subarray of the current sequence is sorted, the first length of which not all the sub array are sorted would be the one iteration we need to run to make all of them sorted. This could be done in O(NlogN) time total.

Summary

We can direct simulate to solve PAT 1089 Insert or Merge or by linear scanning from back to front. Next we run more iterations to find a different sequence.

Written on December 11, 2014