折腾来折腾去

pikipity的blog

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

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

第二周,作业要求使用 “QuickSort” 方法对给定的数列排序,并记录“比较”的次数。这次作业的难点并不是对于 “QuickSort” 的实现,而是作业要求给出“比较”的次数。由于 “QuickSort” 虽然主思路一样但是实现方法千差万别,不同的实现方法会导致统计出来的“比较”的次数不同。所以必须严格按照老师上课讲的方法实现 “QuickSort” 才能得到正确答案。所以是否认真看老师的 lecture video 并能明白老师讲的细节成为这次作业的难点。由于 “QuickSort” 根据选定的 “Pivot” 不同可以分为三种,所以这一次的作业分为三个小问,每一个小问实现一种 “QuickSort",通过“比较”次数的不同就会发现选择哪种 "Pivot” 比较好了。

“QuickSort” 的基本思想和 week 1 中使用的 “Merge Sort” 基本一样,也是将大问题分解为小问题,但是不再是从数组的中间进行数组的拆分,而是通过确定 “Pivot” 元素在排序之后的数组中的位置,并以此位置为基础进行拆分。所以在进行拆分的同时进行了排序,所以也就不需要合并(Merge)的步骤了。基本步骤如下:

  1. 选择一个元素作为 “Pivot"。
  2. 将数组中的其他元素与 “Pivot” 比较大小从而将原数组拆分为两个数组:比 “Pivot” 小的数组与比 “Pivot” 大的数组。确定 “Pivot” 元素的位置从而完成对 “Pivot” 元素的排序。
  3. 分别对拆分出来的两个数组重复步骤1和步骤2,直到全部元素排序完成。

上述步骤中需要注意两点:

  1. 根据选定 “Pivot” 不同,排序步骤会发生不同,这也就是为什么这一次作业会出现三个小问。
  2. 对于拆分的过程不同,拆分出来的两个数组也会不同,这会导致后续步骤中 “Pivot” 的不同,从而导致排序步骤的不同,这也就是为什么要严格按照老师 lecture video 中讲的方法来进行拆分,否则答案会不对。

接下来,对于三个小问(也就是三种 “Pivot” 选择方式衍生出来三种 “QuickSort")分别如何实现来进行讲解。

第一个元素作为 “Pivot”

第一种 “QuickSort” 是将等待排序的数组的第一个元素作为 “Pivot” 来进行排序。在排序中,我们需要两个位置标记 ij,整个等待排序的数列如下图所示,i 标记的是在比 “Pivot” 小的元素的数组中最后一个元素的位置,j 标记的是还没有和 “Pivot” 比较的元素的数组中第一个元素的位置。

第一个元素作为 "Pivot" 的 "QuickSort"

整个排序过程如下:

  1. 选择等待排序的数组的第一个元素作为 “Pivot",初始化 iji指向第一个元素的位置,j 指向第二个元素的位置。
  2. j 指向的元素和 “Pivot” 进行大小比较。如果 j 指向的元素小于 “Pivot",那么就将 j 指向的元素与 i+1 指向的元素进行交换,然后 i 变为 i+1,否则不做任何操作。最后,j 变为 j+1
  3. 重复步骤2,直到 j 指向的位置超出数组范围。得到的数组如下图所示。

    拆分完成

  4. i 指向的元素与 “Pivot” 交换,结束 “Pivot” 元素的排序。得到的数组如下图所示。

    "Pivot" 排序结束

  5. 将比 “Pivot”小的元素组成的数组和比 “Pivot” 大的元素组成的数组分别作为等待排序的数组,重复步骤1~5,直到所有元素排序结束。

需要注意两点:

  1. 尽管存在多种 ij 的选择和移动方式,虽然不影响排序结果,但是会影响后面循环中 “Pivot” 的选择,所以无法得到正确的“比较”次数。
  2. 在第4步中,尽管不采用交换的方式而是直接将 “Pivot” 插入到正确位置并不影响最终的排序结果,但是同样会影响后面循环中 “Pivot” 的选择,所以也无法得到正确的“比较”次数。

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
29
30
31
32
33
34
35
36
37
def QuickSort(InputArray,Count):
    if len(InputArray)==1 or len(InputArray)==0:
        return InputArray,Count
    i=0
    j=1
    while j<len(InputArray):
        Count+=1
        if InputArray[j]<InputArray[0]:
            InputArray[j],InputArray[i+1]=InputArray[i+1],InputArray[j]
            i+=1
            j+=1
        else:
            j+=1
    InputArray[0],InputArray[i]=InputArray[i],InputArray[0]
    InputArray[:i],Count=QuickSort(InputArray[:i],Count)
    InputArray[i+1:],Count=QuickSort(InputArray[i+1:],Count)
    return InputArray,Count
    

# Read file
file="QuickSort.txt"
f=open(file,'r')
InputArray=map(int,f.readlines())
f.close()
Copy=InputArray

# QuickSort
Count=0
InputArray,Count=QuickSort(InputArray,Count)


if InputArray==sorted(Copy):
    print "Correct"
    print Count
else:
    print "Wrong"
    print InputArray

代码的可以到这里下载。答案是162085。

最后一个元素作为 “Pivot”

这种 “QuickSort",只需要在排序前,将最后一个元素和第一个元素交换,就完全可以当作第一种一样进行操作。同样要注意,必须是“交换”,否则无法得到正确的“比较”次数。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
29
30
31
32
33
34
35
36
37
def QuickSort(InputArray,Count):
    if len(InputArray)==1 or len(InputArray)==0:
        return InputArray,Count
    InputArray[0],InputArray[len(InputArray)-1]=InputArray[len(InputArray)-1],InputArray[0]
    i=0
    j=1
    while j<len(InputArray):
        Count+=1
        if InputArray[j]<InputArray[0]:
            InputArray[j],InputArray[i+1]=InputArray[i+1],InputArray[j]
            i+=1
            j+=1
        else:
            j+=1
    InputArray[0],InputArray[i]=InputArray[i],InputArray[0]
    InputArray[:i],Count=QuickSort(InputArray[:i],Count)
    InputArray[i+1:],Count=QuickSort(InputArray[i+1:],Count)
    return InputArray,Count
    

# Read file
file="QuickSort.txt"
f=open(file,'r')
InputArray=map(int,f.readlines())
f.close()
Copy=InputArray

# QuickSort
Count=0
InputArray,Count=QuickSort(InputArray,Count)

if InputArray==sorted(Copy):
    print "Correct"
    print Count
else:
    print "Wrong"
    print InputArray

代码可以到这里下载。答案是164123。

中间元素作为 “Pivot”

这里的“中间”元素并不是指地是数列中间的元素,而是将数列第一个元素、数列最后一个元素和数列中间的元素进行大小比较,排在中间的元素作为 “Pivot"。这一种同样可以等效为第一种,只是在排序前先要进行比较,然后把选定的元素和数列第一个元素进行交换就可以了。同样要注意,必须是“交换”。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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def QuickSort(InputArray,Count):
    if len(InputArray)==1 or len(InputArray)==0:
        return InputArray,Count
    Mid=(len(InputArray)-1)//2
    a=InputArray[0]
    b=InputArray[Mid]
    c=InputArray[len(InputArray)-1]
    if (b>a and b<c) or (b<a and b>c):
        InputArray[0],InputArray[Mid]=InputArray[Mid],InputArray[0]
    elif (c>a and c<b) or (c<a and c>b):
        InputArray[0],InputArray[len(InputArray)-1]=InputArray[len(InputArray)-1],InputArray[0]
    i=0
    j=1
    while j<len(InputArray):
        Count+=1
        if InputArray[j]<InputArray[0]:
            InputArray[j],InputArray[i+1]=InputArray[i+1],InputArray[j]
            i+=1
            j+=1
        else:
            j+=1
    InputArray[0],InputArray[i]=InputArray[i],InputArray[0]
    InputArray[:i],Count=QuickSort(InputArray[:i],Count)
    InputArray[i+1:],Count=QuickSort(InputArray[i+1:],Count)
    return InputArray,Count


# Read file
file="QuickSort.txt"
f=open(file,'r')
InputArray=map(int,f.readlines())
f.close()
Copy=InputArray

# QuickSort
Count=0
InputArray,Count=QuickSort(InputArray,Count)


if InputArray==sorted(Copy):
    print "Correct"
    print Count
else:
    print "Wrong"
    print InputArray

代码可以到这里下载。答案是138382。



Comments