algorithm - 冒泡排序变体——三个相邻数字交换

Question

这个问题出现在已经结束的code jam 2018资格赛中。
https://codejam.withgoogle.com/2018/challenges/ (问题2)

问题描述:

The basic operation of the standard bubble sort algorithm is to examine a pair of adjacent numbers and reverse that pair if the left number is larger than the right number. But our algorithm examines a group of three adjacent numbers, and if the leftmost number is larger than the rightmost number, it reverses that entire group. Because our algorithm is a "triplet bubble sort", we have named it Trouble Sort for short.

We were looking forward to presenting Trouble Sort at the Special Interest Group in Sorting conference in Hawaii, but one of our interns has just pointed out a problem: it is possible that Trouble Sort does not correctly sort the list! Consider the list 8 9 7, for example.

We need your help with some further research. Given a list of N integers, determine whether Trouble Sort will successfully sort the list into non-decreasing order. If it will not, find the index (counting starting from 0) of the first sorting error after the algorithm has finished: that is, the first value that is larger than the value that comes directly after it when the algorithm is done.

因此，一种天真的方法是对给定列表应用麻烦排序，对列表应用正常排序，然后找到第一个不匹配元素的索引。但是，对于非常大的 N，这会超时。

这是我的想法:该算法会将第 0 个索引与第 2 个、第 2 个与第 4 个进行比较，依此类推。类似地，第 1 对第 3，第 3 对第 5，依此类推。

奇数索引处的所有元素都将根据奇数索引进行排序。对于偶数索引元素也是如此。所以问题出在两个连续的奇数/偶数索引元素之间。

如果不采用 O(n^2) 方法，我想不出一种方法来解决这个问题。

我的方法是否可行，或者有更简单的方法吗？

Answer 1

您的观察很到位。问题陈述中提出的算法只会比较(和交换)连续的奇数和偶数元素。

如果您更进一步观察，您可以说麻烦排序是一种算法，可以正确地对数组中的奇数和偶数索引元素进行排序。 (即，就好像数组 A 的奇数索引元素和偶数索引元素是两个独立的数组 B 和 C)

换句话说，问题排序确实正确地对 B 和 C 进行了排序。这里的问题是那些奇数和偶数索引元素的数组 B 和 C 是否可以正确合并。您应该检查在它们之间对奇数和偶数索引元素进行排序是否足以使整个数组排序。

这一步真的很像MergeSort的合并步骤。唯一的区别是，由于索引是您操作的限制因素，您始终知道将从哪个数组中选择顶部元素。对于 1 索引数组 A，在 B 和 C 的合并步骤中，在每个步骤中，您应该从 B 中选择最小的先前未选择的元素，然后是 C。

所以，基本上，如果您对 B 和 C 进行排序，则需要 O(NlogN)使用诸如 mergesort 或 heapsort 之类的算法，然后以上一段中描述的方式合并它们，这需要 O(N) ，经过问题排序算法处理后，您最终会得到相同版本的数组 A。

区别在于时间复杂度。虽然问题排序需要 O(N^2)时间，上述操作需要 O(NlogN)时间。一旦你得到这个数组，你就可以 checkin O(N)时间 if，对于每个连续的索引 i，j，A[i] < A[j]持有。算法的整体复杂度仍为 O(NlogN) .

下面是一个 Python 代码示例，用于演示我上面描述的算法的某种伪代码。由于 Python 数组是 0 索引的，因此在实现中存在一些细微差别。您可能会观察此代码的执行 here .

def does_trouble_sort_work(A):
    B, C = A[0::2], A[1::2]
    B_sorted = sorted(B)
    C_sorted = sorted(C)
    j = k = 0
    for i in xrange(len(A)):
        if i % 2 == 0:
            A[i] = B_sorted[j]
            j += 1
        else:
            A[i] = C_sorted[k]
            k += 1 

    trouble_sort_works = True
    for i in xrange(1, len(A)):
        if A[i-1] > A[i]:
            trouble_sort_works = False
            break
    return trouble_sort_works