Python実現『アルゴリズム導論第三版』におけるアルゴリズム第2章アルゴリズム基礎

目次

第2章アルゴリズム基礎

1. 挿入ソート

2. 集計ソート

3. 選択ソート

4. バブルソート

5. 私の好きな集計ソートの書き方

第2章アルゴリズムの基礎
1.ソートの挿入
P10.ソートの挿入は簡単です.

class InsertionSort:
    def sort(self, A):
        for i in range(1, len(A)):
            temp = A[i]
            j = i - 1
            while j >= 0 and A[j] > temp:
                A[j + 1] = A[j]
                j -= 1
            A[j + 1] = temp #           


def main():
    isort = InsertionSort()
    A = [5, 2, 4, 6, 1, 3] # P10  
    isort.sort(A)
    print(A)

  
if __name__ == '__main__':
    main()

2.集計ソート
P17.集計ソートは分治法を利用した.

class MergeSort:
    def _merge(self, A, p, q, r):
        import math
        n1 = q - p + 1
        n2 = r - q
        L = [0] * (n1 + 1)
        R = [0] * (n2 + 1)
        for i in range(n1):
            L[i] = A[p + i]
        for j in range(n2):
            R[j] = A[q + j + 1]
        L[n1] = math.inf
        R[n2] = math.inf
        i = j = 0
        for k in range(p, r+1):
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                A[k] = R[j]
                j += 1
                
    def sort(self, A, p, r):
        if p < r:
            q = (p + r) // 2
            self.sort1(A, p, q)
            self.sort1(A, q+1, r)
            self._merge(A, p, q, r)          

    
def main():
    ms = MergeSort()
    A = [2, 4, 5, 7, 1, 2, 3, 6] # P18  
    ms.sort1(A, 0, 7)
    print(A)
    
    
if __name__ == '__main__':
    main()

並べ替えの他の書き方.この書き方は本の中の偽コードとは異なり,異なるパラメータが使用されているためである.

class MergeSort:
    def _merge(self, arr1, arr2):
        res = []
        i1 = i2 = 0
        while i1 < len(arr1) and i2 < len(arr2):
            if arr1[i1] < arr2[i2]:
                res.append(arr1[i1])
                i1 += 1
            else:
                res.append(arr2[i2])
                i2 += 1
               
        if i1 == len(arr1):
            res.extend(arr2[i2:])
        else:
            res.extend(arr1[i1:])
            
        return res
        
    def sort(self, arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left_arr = self.sort(arr[:mid])
        right_arr = self.sort(arr[mid:])
        return self._merge(left_arr, right_arr)


def main():
    A = [2, 4, 5, 7, 1, 2, 3, 6] # P18  
    print(ms.sort(A))
    
    
if __name__ == '__main__':
    main()

3.ソートの選択
P 16練習2.2-2.

class SelectionSort:
    def sort(self, A):
        for i in range(0, len(A)):
            k = i
            # Find the smallest num and record its index
            for j in range(k, len(A)):
                if A[j] < A[k]:
                    k = j
            if k != i:
                A[i], A[k] = A[k], A[i]
    
    
def main():
    ss = SelectionSort()
    A = [5, 2, 4, 6, 1, 3] # P10  
    ss.sort(A)
    print(A)
    
    
if __name__ == '__main__':
    main()

4.泡立ちソート
P 23思考問題2-2.

class BubbleSort:
    def sort(self, A):
        for i in range(len(A)):
            for j in range(0, len(A)-i-1):
                if A[j] > A[j+1]:
                    A[j], A[j+1] = A[j+1], A[j]
                    
    
def main():
    bs = BubbleSort()
    A = [5, 2, 4, 6, 1, 3] # P10  
    bs.sort(A)
    print(A)

  
if __name__ == '__main__':
    main()     

5.私の好きな集計ソートの書き方

def merge(A, left, mid, right):
    """A[left:mid+1], A[mid+1:right+1]"""
    container = []  #         
    i, j = left, mid + 1
    while i <= mid and j <= right:
        if A[i] <= A[j]:
            container.append(A[i])
            i += 1
        else:
            container.append(A[j])
            j += 1
    container.extend(A[i: mid + 1])
    container.extend(A[j: right + 1])
    A[left: right + 1] = container


def merge_sort(A, left, right):
    if left < right:
        mid = left + (right - left) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid + 1, right)
        merge(A, left, mid, right)


if __name__ == '__main__':
    A = [0, 1, 2, 3, 4, 9, 8, 7, 4, 4]
    merge_sort(A, 0, len(A)-1)
    print(A)