Sorting Sort 3 - Merged Sort and Shell Sort

1. Merge Sort
Kami sekarang mengalihkan perhatian kami untuk menggunakan strategi membagi dan menaklukkan sebagai cara untuk meningkatkan kinerja algoritma penyortiran. Algoritma pertama yang akan kita pelajari adalah jenis gabungan. Merge sort adalah algoritma rekursif yang terus membagi daftar menjadi dua. Jika daftar kosong atau memiliki satu item, itu diurutkan berdasarkan definisi (kasus dasar). Jika daftar memiliki lebih dari satu item, kami membagi daftar dan secara rekursif memanggil semacam gabungan pada kedua bagian. Setelah dua bagian diurutkan, operasi fundamental, yang disebut penggabungan, dilakukan. Penggabungan adalah proses mengambil dua daftar yang disortir lebih kecil dan menggabungkannya bersama-sama ke dalam daftar tunggal, terurut, baru. Gambar 1 menunjukkan daftar contoh yang kita kenal saat dipisah oleh mergeSort. Gambar 2 menunjukkan daftar sederhana, sekarang disortir, karena mereka digabungkan kembali bersama.

def mergeSort(alist):
    print('spliting :',alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] > righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [68, 90, 78, 44, 34, 20, 100, 56, 34]
mergeSort(alist)
print(alist)

Video Tutorial Merge Sort 

https://goo.gl/Hnwmcq 

2. Shell Sort
Hal ini dapat dilihat sebagai generalisasi penyortiran dengan pertukaran (bubble sort) atau penyortiran dengan penyisipan (semacam penyisipan). Metode ini dimulai dengan menyortir pasangan elemen yang berjauhan satu sama lain, lalu secara progresif mengurangi jarak antar elemen yang akan dibandingkan. Dimulai dengan elemen yang berjauhan, ia dapat memindahkan beberapa elemen di luar tempat ke posisi lebih cepat daripada pertukaran tetangga terdekat yang sederhana.

def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:

      for startposition in range(sublistcount):
        gapInsertionSort(alist,startposition,sublistcount)

      print("After increments of size",sublistcount,"The list is",alist)

      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]
        position = i

        while position >= gap and alist[position-gap] > currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

alist = [45, 23, 9, 100, 77, 21, 54]
shellSort(alist)
print(alist)

Video Tutorial Shell Sort 

https://goo.gl/xoz8cW