Sorting II

SORTING


Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi.Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna.


Dua Macam Pengurutan

•  Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar.
•  Descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

1. Insertion sort

Pengurutan yang dilakukan dengan cara membandingkan dengan data ke-2 sampai data terakhir. Jika ditemukan data yang lebih kecil atau lebih besar maka data tersebut disisipkan kedepan sesuai posisi yang seharusnya.

Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila
ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan
pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu.
Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya
dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelahkiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

2. Merge Sort

Merupakan proses pengurutan data yang menggunakan merging dua buah vector. Pada proses merge sort, data dibuat sepasang-sepasang, yang terdiri dari dua elemen. Jika N ganjil, maka ada satu vector yang terdiri dari 1 elemen. Lalu kemudian data tersebut di merging sampai terurut. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table

sehingga dalam keadaan urut.

3. Quick Sort

Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.

Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot. Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi.

Contoh soal untuk materi diatas :

Jawaban :

1. 

import time

def daribelakang(GG):

    for j in range(len(GG)-1,-1,-1):

        value = GG[j]

        hole = j

        while hole<(len(GG)-1) and GG[hole+1]>GG[hole]:

            GG[hole] = GG[hole+1]

            hole = hole+1

            GG[hole] = value

        print(GG)

def daridepan(GG):

    for j in range(1,len(GG)):

        value = GG[j]

        hole = j

        while hole>0 and GG[hole-1]>GG[hole]:

            GG[hole] = GG[hole-1]

            hole = hole-1

            GG[hole] = value

        print(GG)

alist = [10, 74, 87, 27, 61, 9, 24, 53, 72, 41, 86, 88, 35, 48, 33, 15, 94, 79, 90, 93, 77, 42, 1, 49, 38, 76, 2, 68, 5, 20, 80, 32, 82, 29, 75, 62, 83, 14, 46, 65, 58, 57, 100, 73, 3, 23, 66, 71, 36, 69, 91, 28, 16, 64, 43, 17, 56, 11, 45, 60, 52, 21, 44, 7, 50, 19, 47, 6, 89, 4, 39, 92, 98, 26, 40, 22, 34, 31, 55, 13, 96, 30, 70, 59, 84, 54, 67, 51, 81, 63, 78, 18, 37, 85, 97, 95, 99, 8, 12, 25]

alist1=[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, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]

start = time.time()

daribelakang(alist)

end=time.time()

start1 = time.time()

daribelakang(alist1)

end1 = time.time()

print("waktu acak:", end-start)

print("waktu urut:", end1-start1)

2. 

3.

Sekian pembahasan beberapa materi sorting oleh saya, terima kasih. :)