折腾来折腾去

pikipity的blog

Algorithms: Design and Analysis Part 1 -- Programming Questions (Week1)

这里主要记录下来在 “Algorithms: Design and Analysis Part 1” 的Programming Questions 中的算法、实现和作业中的困难。我是用的是 Python。Week 1 Programming Question 的题目可以到这里查看,作业用到的数据可以到这里下载。

第一周,作业是要求使用 “Merge Sort” 方法对给定的数列排序,并记录下颠倒元素组(inversions)的个数。对于颠倒元素组,如果在一个数组中a[i]>a[j]但是i<j,就可以将其定义为一个颠倒元素组。例如,在2, 4, 1, 3, 5中,有三组(2,1)(4,1)(4,3)

“Merge Sort” 方法比较简单(毕竟才第一周)。方法主要思想就是把一个大问题变为小问题,通过解决所有的小问题来实现大问题的解决。那么这个方法也就分为两步:

  1. 大问题分解为小问题(Devide):这一步中,要将这个数组从中间进行拆分,一直拆分到数组足够小为止,对于排序问题,最小的数组应该是仅包含两个元素的数组。
  2. 解决所有的小问题实现大问题的解决(Merge):这一步中,要将刚才拆分出来的所有小问题以回溯的方式逐层解决。

拿一个例子来讲解一下,加入我们要排序的数组是2, 4, 1, 3, 5,按照上面的步骤:

  1. 首先将大问题进行拆分,如图。

    Divide

  2. 然后从下向上依次解决小问题:
    • 最下层有两个数组(2, 4)(1),很显然不存在颠倒元素组

      Merge 1

    • 然后将最下层的两个数组(2, 4)(1)进行合并,合并的同时进行排序。注意:在每次合并的时候,两个数组一定是已经各自排好序的,所以如果第一个数组的第 i 个元素大于第二个数组的第 k 个元素,那么第一个数组的第 i+1, i+2, i+3 … 个元素都大于第二个数组的第 k 个元素,也就是说,如果第一个数组的长度为 L,那么就有 (L-i+1) 个颠倒元素组。如图:

      Merge 2

    • 类似的步骤对倒数第二层使用,就可以得到最终的结果了。

      Merge 3

在这个方法中需要特别注意的三点:

  1. 在每次合并的时候,两个数组一定是已经各自排好序的,所以如果第一个数组的第 i 个元素大于第二个数组的第 k 个元素,那么第一个数组的第 i+1, i+2, i+3 … 个元素都大于第二个数组的第 k 个元素,也就是说,如果第一个数组的长度为 L,那么就有 (L-i+1) 个颠倒元素组,如图。需要注意的是,这里的 i 和 k 都是指的第 X 个元素,对于不同的编程语言,由于元素起始编号不同,那么对于第 X 个元素的引用方式也会不同,常规情况下(例如 C,C++,java 等),起始元素编号为0,所以第 i 个元素应该为 a[i-1] 而不是 a[i],而对于 MATLAB,起始元素是1,所以第 i 个元素就是 a[i]。所以在计算颠倒元素个数的时候,要注意应该是 (L-i) 还是 (L-i+1)

    如何统计颠倒元素个数

  2. 在合并的时候,可以每次都比较两个数组中的第一个元素,然后将小的那个从原数组中排出,放到存放结果的数组的最后,如图

    如何合并两个数组

  3. 最后在统计颠倒元素组个数的时候,记得要将所有的颠倒元素组加起来,包括拆分和合并两个部分。

最后是代码部分,我用的是 Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def SortCount(input_array):
    if len(input_array) > 1:
        lower_part, count1 = SortCount(input_array[:len(input_array)//2])
        upper_part, count2 = SortCount(input_array[len(input_array)//2:])
        merge_part, count3 = MergeCount(lower_part,upper_part)
        return merge_part, count1+count2+count3
    else:
        return input_array, 0


def MergeCount(lower_part,upper_part):
    count = 0
    merge_result = []
    while lower_part and upper_part:
        if lower_part[0] <= upper_part[0]:
            merge_result.append(lower_part.pop(0))
        else:
            count += len(lower_part)
            merge_result.append(upper_part.pop(0))
    merge_result  += lower_part + upper_part
    return merge_result, count

file="IntegerArray.txt"
f=open(file,'r')
Array=map(int,f.readlines())
f.close()
SortArray,Count=SortCount(Array)
print Count

代码可以到这里下载。作业用到的数据可以到这里下载。答案:2407905288



Comments