Stanford -Divide and Conquer, Sorting and Searching, and Randomized Algorithms-assignment 3

题目原文：

Stanford university -Divide and Conquer, Sorting and Searching, and Randomized Algorithms-assignment 3

The file contains all of the integers between 1 and 10,000 (inclusive, with no repeats) in unsorted order. The integer in the i^{th}ith row of the file gives you the i^{th}ith entry of an input array.

Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we'll ask you to explore three different pivoting rules.

You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length mm, you should simply add m-1m−1 to your running total of comparisons. (This is because the pivot element is compared to each of the other m-1m−1 elements in the subarray in this recursive call.)

WARNING: The Partition subroutine can be implemented in several different ways, and different implementations can give you differing numbers of comparisons. For this problem, you should implement the Partition subroutine exactly as it is described in the video lectures (otherwise you might get the wrong answer).

DIRECTIONS FOR THIS PROBLEM:

For the first part of the programming assignment, you should always use the first element of the array as the pivot element.

HOW TO GIVE US YOUR ANSWER:

Type the numeric answer in the space provided.

So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / other punctuation marks. You have 5 attempts to get the correct answer.

(We do not require you to submit your code, so feel free to use the programming language of your choice, just type the numeric answer in the following space.)

首先用python将txt写入；读入字符串，转成array；

然后再以左边的值为pivot；

然后加index；

最后print index；

import numpy as np

txt_path = 'QuickSort.txt'	# txt文本路径
f = open(txt_path)
data_lists = f.readlines()	#读出的是str类型

dataset= []
# 对每一行作循环
for data in data_lists:
    data1 = data.strip('\n')	# 去掉开头和结尾的换行符
    data2 =int(data1)	# 把tab作为间隔符
    dataset.append(data2)	# 把这一行的结果作为元素加入列表dataset

dataset = np.array(dataset)




# 快速排序
def partition(li,left,right):  
    tmp = li[right]
    while left > right:
        while left > right and li[left] <= tmp: 
            
        left+ = 1 #继续从左往右查找
        li[right] = li[left] #把左边的值写到右边空位上
        
        while left > right and li[right] >= tmp :
            
            right -= 1   #继续从右往左查找
            li[left] = li[right]  #把右边的值写到左边空位上
        
       
      
    li[right] = tmp #把tmp归位
    return  right

index = 0

def quick_sort(li,left,right):  
    global index
    index +=1
    if left < right :#至少两个元素
        mid = partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)
li = dataset
quick_sort(li,0,len(li)-1)
print(li)
print(index)