STRUKTUR DATA Sorting - Merged Sort, Shell Sort Python

STRUKTUR DATA Sorting - Merged Sort, Shell Sort

➢     MergedSort.

MergedSort adalah algoritma Divide and Conquer. Ini membagi array input dalam dua bagian, panggilan itu sendiri untuk dua bagian dan kemudian menggabungkan dua bagian yang disortir. Fungsi gabungan () digunakan untuk menggabungkan dua bagian.

https://www.youtube.com/watch?v=TzeBrDU-JaY&list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U&index=5 

 

 

def MergedSort(A):

    print('splitting', A)

    n = len(A)

    if (n<2):

       return

    mid = len(A)//2

    left = A[:mid]

    right = A[mid:]

    MergedSort(left)

    MergedSort(right)

    i=0

    j=0

    k=0

    while i < len(left) and j < len(right):

        if left[i] > right[j]:

            A[k]=left[i]

            i=i+1

        else:

            A[k]=right[j]

            j=j+1

        k=k+1

    while i < len(left):

        A[k]=left[i]

        i=i+1

        k=k+1

    while j < len(right):

        A[k]=right[j]

        j=j+1

        k=k+1

    print("marging", A)

Alist= [54,26,93,17,99,77,31,44,55,20,100]

MergedSort(Alist) 

print(Alist

  

 

➢   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.

 https://www.youtube.com/watch?v=qzXAVXddcPU

 

 

def shellSort(alist):

    sublistcount = len(alist)//2

    while sublistcount > 0:

      for startposition in range(sublistcount):

        gapInsertionSort(alist,startposition,sublistcount)

      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 = [35,33,42,10,14,19,27,44]

shellSort(alist)

print(alist)