Pengurutan Data Secara Advanced Dengan Merge Sort

Merge Sort merupakan metode lanjutan untuk pengurutan data.Kenapa bisa disebut lanjutan ? Karena memang cara kerjanya tidak sesederhana metode sebelumnya yang sudah diperkenalkan seperti Bubble,Selection dan Insertion Sort yang mudah untuk digunakan secara real maupun dimasukkan ke dalam bahasa pemrograman.Mungkin untuk merge sort kita agak mikir dikit

Kira-kira seperti apa sih Merge Sort itu ? Gambaran kasar nya Merge Sort itu kita membagi data menjadi 2 terus menerus sampai ukuran terkecil (1 data) kemudian kita menggabungkan sekaligus mengurutkannya untuk mendapatkan data yang terurut.Merge Sort termasuk ke dalam Divide dan Conquer karena cara kerjanya itu

Untuk detail cara penggunaannya adalah sebagai berikut :

Saya punya data 37 42 31 44 34 32 38 dan akan saya urutkan secara ascending

37 42 31 44 34 32 38 

37    42    31    44            34 32 38  ---> 4 data dan 3 data

37    42  31  44           34    32        38   --->2,2,2 dan 1 data

37       42       31         44        34          32         38  ---> 1 data

37   42      31   44           32  34       38 ---> gabungkan 2 elemen yang berdekatan dan urutkan

31  37  42  44                 32  34  38

31  32  34  37  38  42  44 (data terurut)

Contoh Kode Java Merge Sort


package mainclass; /* Program Java untuk Merge Sort */ class Contoh { // Gabungkan dua subarray dari arr[]. // subarray pertama adalah arr[l..m] // subarray kedua adalah arr[m+1..r] void merge(int arr[], int l, int m, int r) { // Cari ukuran 2 subarray untuk digabungkan int n1 = m - l + 1; int n2 = r - m; /* Membuat array sementara */ int L[] = new int [n1]; int R[] = new int [n2]; /*Copy data ke array sementara*/ for (int i=0; i<n1; ++i) L[i] = arr[l + i]; for (int j=0; j<n2; ++j) R[j] = arr[m + 1+ j]; /* Merge the temp arrays */ // Indeks awal subarray pertama dan kedua int i = 0, j = 0; // Indeks awal array yang digabungkan int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* Copy elemen L[] jika ada yang sisa */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* Copy elemen R[] jika ada yang sisa */ while (j < n2) { arr[k] = R[j]; j++; k++; } } void sort(int arr[], int l, int r) { if (l<r) { // Cari titik tengah int m =(l+r)/2; // Urutkan tengah pertama dan kedua sort(arr,l,m); sort(arr,m+1,r); // Gabungkan keduanya merge(arr,l,m,r); } } /* function untuk print array */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = {37,42,31,44,34,32,38}; System.out.println("Array semula"); printArray(arr); Contoh ob = new Contoh(); ob.sort(arr, 0, arr.length-1); System.out.println("\narray terurut"); printArray(arr); } }

Contoh Kode Python Merge Sort :

def mergeSort(arr): if len(arr) >1: mid = len(arr)//2 #Cari titik tengah array L = arr[:mid] # membagi elemen array R = arr[mid:] # menjadi 2 bagian mergeSort(L) # Urutkan bagian pertama mergeSort(R) # Urutkan bagian kedua i = j = k = 0 # Copy data ke array sementara L[] dan R[] while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i+=1 else: arr[k] = R[j] j+=1 k+=1 # Mengecek elemen yang tersisa while i < len(L): arr[k] = L[i] i+=1 k+=1 while j < len(R): arr[k] = R[j] j+=1 k+=1 # Code to print the list def printList(arr): for i in range(len(arr)): print(arr[i],end=" ") print() arr = [37,42,31,44,34,32,38] print ("Array semula", end="\n") printList(arr) mergeSort(arr) print("Array terurut: ", end="\n") printList(arr)

Penggunaan Insertion Sort Untuk Mengurutkan Data

Insertion Sort merupakan penyempurnaan dari Selection Sort .Prinsip kerja dari Insertion Sort adalah mengambil satu elemen lalu kita akan menempatkannya di posisi yang tepat.Setelah kita ambil,supaya lebih mudah maka kita pisahkan dari list dulu.Setelah itu,ambil elemen berikutnya lalu tempatkan di luar list dengan posisi yang benar.

Begitu seterusnya sampai semua elemen telah terambil dan kita mendapatkan data yang urut.Jadi untuk singkatnya Insertion Sort ini seperti "Ambil Data lalu Tentukan Posisinya"

Kelebihan Insertion Sort :

• Tidak memerlukan iterasi yang panjang seperti Bubble Sort
• Titik pengambilan elemen bebas,kalian bisa dari kiri atau kanan bahkan tidak urut saja tidak apa-apa beda sekali dengan Bubble Sort yang memang harus urut supaya lebih mudah

Kekurangan Insertion Sort :

• Perlu kecermatan tinggi,karena dalam menentukan posisi nya kita tidak boleh salah jadi ini lebih rumit dari pada Bubble Sort dan Selection Sort
• Tidak cocok untuk jumlah data yang banyak,sama seperti metode yang sebelumnya

Contoh Cara Menggunakan Insertion Sort untuk Pengurutan Data :

• Saya punya data  misalnya [42,35,27,45,52,49,57] dan akan saya urutkan dari kecil ke besar (Ascending)
• [42 35 27 45 52 49 57] 35 taruh di sebelah kiri 42
• 35 42[ 27 45 52 49 57] 27 paling kecil dibandingkan 35 dan 42,jadi taruh paling kiri
• 27 35 42[ 45 52 49 57] 45 lebih besar dari 27,35,42 jadi posisinya tidak berubah
• 27 35 42 45[ 52 49 57] 52 lebih besar dari 27,35,42 dan 45 jadi posisinya tidak berubah
• 27 35 42 45 52[ 49 57] 49 lebih besar dari 45 tapi lebih kecil dari 52 jadi 49 diletakkan diantara 45 dan 52
• 27 35 42 45 49 52[57] 57 paling besar di sini jadi benar posisinya di situ
• [27 35 42 45 49 52 57] (data urut secara Ascending)

Saya kasih contoh sekali lagi namun kali ini secara Descending

• Saya punya data misalnya [32,37,29,26,30,45,43]
• [32 37 29 26 30 45 43]  32<37 jadi 37 taruh di sebelah kiri 32
• 37 32[ 29 26 30 45 43] 29 lebih kecil dari 37 dan 32 jadi posisi 29 tetap di situ
• 37 32 29[ 26 30 45 43] 26 lebih kecil dari 37,32 dan 29 jadi posisinya tetap
• 37 32 29 26[ 30 45 43]  30 lebih kecil dari 32 dan lebih besar dari 29 jadi posisinya diantara 32 dan 29
• 37 32 30 29 26[45 43] 45 paling besar di sini jadi taruh saja di paling kiri
• 45 37 32 30 29 26[43] 43 hanya lebih kecil dari 45 jadi taruh 43 di sebelah kanan 45
• [45 43 37 32 30 29 26] (Data urut secara Descending)

PseudoCode Untuk Insertion Sort :

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

 Contoh Insertion Sort di Java :

Contoh Insertion Sort di Python :

Mengurutkan Data Dengan Selection Sort

Kita akan melanjutkan postingan sebelumnya mengenai metode-metode untuk mengurutkan kumpulan data sebelumnya kita telah membahas tentang Bubble Sort yang mengharuskan kita untuk menukar posisi data terus-menerus sampai tidak ada data yang bisa ditukar posisinya lagi.Untuk metode Bubble Sort meskipun cara kerjanya sederhana namun perlu ketelitian yang tinggi sehingga metode ini kurang efisien

Nah,kali ini kita akan membahas metode yang lebih efektif untuk mengurutkan data yaitu Selection Sort. Algoritma ini juga terbilang sederhana namun kita juga perlu ketelitian tinggi untuk mendapatkan data yang urut.Algoritma ini memiliki prinsip kita akan mencari nilai terendah/tertinggi di dalam kumpulan data

Saya langsung kasih contohnya saja supaya lebih mudah dipahami

1. Saya punya data misalnya [25,11,15,39,52,47] dan saya ingin mengurutkannya secara Ascending(kecil ke besar)Cari data terkecil di sana.
2. Saya sudah menemukannya yaitu 11
3. Taruh 11 di paling kiri dan pisahkan 11 dari list tersebut sehingga jadi begini 11[25 15 39 52 47]
4. Ulangi langkah 2 dan 3 terus menerus sampai data urut 

11[25 15 39 52 47] ---> data terkecil 15
11 15[25 39 52 47] ---> data terkecil 25
11 15 25[39 52 47] ---> data terkecil 39
11 15 25 39 [52 47] ---> data terkecil 47
[11 15 25 39 47 52] (data urut secara ascending)

Lalu bagaimana dengan Descending ?

[11 25 15 39 52 47] ---> data terbesar 52
52[11 25 15 39 47]  ---> data terbesar 47
52 47[11 25 15 39]  ---> data terbesar 39
52 47 39[11 25 15]  ---> data terbesar 25
52 47 39 25[11 15]  ---> data terbesar 15
[52 47 39 25 15 11] (data urut secara descending)

Kelebihan Selection Sort :

• Sangat simple tidak perlu banyak perbandingan
• Proses berhenti saat data sudah urut,tidak seperti Bubble Sort yang tetap lanjut untuk memastikan tidak ada lagi pertukaran posisi
• Cepat untuk menggurutkan data

Kekurangan Selection Sort :

• Hanya efektif untuk jumlah data sedikit
• Harus teliti untuk menemukan data terkecil (di Bubble Sort kita tidak perlu mencari data terkecil) Kalau salah sedikit maka harus ulangi dari awal

Contoh kode dan Output Selection Sort Java :

Contoh kode dan Output Selection Sort Python :

Mengurutkan Data Dengan Bubble Sort

Metode Bubble Sort merupakan proses pengurutan data dengan memindahkan data secara berangsur-angsur ke posisi yang tepat.Metode Bubble Sort ini memang terinspirasi dari gelembung yang berada di permukaan air,karena berat jenis gelembung lebih kecil dari pada air maka gelembung akan selalu terapung di permukaan air.Kira-kira seperti itulah gambaran pengurutan data menggunakan Bubble Sort

Cara kerja Algoritma Bubble Sort dalam pengurutan data :

• Tentukan dulu mau urut secara Ascending(kecil ke besar) atau Descending(besar ke kecil)
• Hitung jumlah datanya dulu
• Jumlah iterasi pada setiap proses adalah jumlah data dikurangi satu
• Bandingkan suatu data dengan data di sebelahnya kemudian tukar posisinya jika tidak benar urutannya
• Meskipun data sudah urut, proses tetap dilakukan untuk memastikan tidak ada lagi pertukaran data

Nah,sekarang saya kasih contoh cara mengurutkan data dengan Bubble Sort :

1) Secara Ascending

Saya punya data sebagai berikut [5,3,9,11,8,12] dan saya ingin mengurutkannya dari kecil ke besar maka begini langkahnya

Jumlah iterasi = 6-1 =5

Iterasi 1

[5 3 9 11 8 12]  5 > 3 tukar posisinya

[3 5 9 11 8 12]  5 < 9 tetap

[3 5 9 11 8 12]  9 < 11 tetap

[3 5 9 11 8 12]  11 > 8 tukar posisinya

[3 5 9 8 11 12]  11 < 12 tetap

Iterasi 2

[3 5 9 8 11 12] 3 < 5 tetap

[3 5 9 8 11 12] 5 < 9 tetap

[3 5 9 8 11 12] 9 > 8 tukar posisinya

[3 5 8 9 11 12] 9 < 11 tetap

[3 5 8 9 11 12] 11 < 12 tetap

Kita lakukan iterasi sekali lagi untuk memastikan tidak ada lagi pertukaran posisi

Iterasi 3

[3 5 8 9 11 12] 3 < 5 tetap

[3 5 8 9 11 12] 5 < 8 tetap

[3 5 8 9 11 12] 8 < 9 tetap

[3 5 8 9 11 12] 9 < 11 tetap

[3 5 8 9 11 12] 11 < 12 tetap

Karena sudah tidak ada lagi pertukaran data,kita hentikan proses di sini saja.Kita sudah mendapatkan data yang terurut secara ascending yaitu [3,5,8,9,11,12]

2) Secara Descending

Saya akan menggunakan contoh data yang sama namun kali ini kita akan mengurutkannya dari besar ke kecil (Descending) Data yang belum urut tadi adalah [5,3,9,11,8,12]

Iterasi 1

[5 3 9 11 8 12] 5 > 3 tetap

[5 3 9 11 8 12] 3 < 9 tukar posisinya

[5 9 3 11 8 12] 3 < 11 tukar posisinya

[5 9 11 3 8 12] 3 < 8 tukar posisinya

[5 9 11 8 3 12] 3 < 12 tukar posisinya

Iterasi 2

[5 9 11 8 12 3] 5 < 9 tukar posisinya

[9 5 11 8 12 3] 5 < 11 tukar posisinya

[9 11 5 8 12 3] 5 < 8 tukar posisinya

[9 11 8 5 12 3] 5 < 12 tukar posisinya

[9 11 8 12 5 3] 5 > 3 tetap

Iterasi 3

[9 11 8 12 5 3] 9 < 11 tukar posisinya

[11 9 8 12 5 3]  9 > 8 tetap

[11 9 8 12 5 3] 8 < 12 tukar posisinya

[11 9 12 8 5 3]  8 > 5 tetap

[11 9 12 8 5 3] 5 > 3 tetap

Iterasi 4

[11 9 12 8 5 3] 11 > 9 tetap

[11 9 12 8 5 3] 9 < 12 tukar posisinya

[11 12 9 8 5 3] 9 > 8 tetap

[11 12 9 8 5 3] 8 > 5 tetap

[11 12 9 8 5 3] 5 > 3 tetap

Iterasi 5

[11 12 9 8 5 3] 11 < 12 tukar posisiya

[12 11 9 8 5 3] 11 > 9 tetap

[12 11 9 8 5 3] 9 > 8 tetap

[12 11 9 8 5 3] 8 > 5 tetap

[12 11 9 8 5 3] 5 > 3 tetap

Iterasi 6

[12 11 9 8 5 3] 12 > 11 tetap

[12 11 9 8 5 3] 11 > 9 tetap

[12 11 9 8 5 3] 9 > 8 tetap

[12 11 9 8 5 3] 8 > 5 tetap

[12 11 9 8 5 3] 5 > 3 tetap

Karena sudah tidak ada pertukaran data lagi,maka prosesnya sudah selesai.Kita mendapatkan data yang sudah terurut secara descending yaitu [12,11,9,8,5,3]

Contoh kode dan Output Bubble Sort Ascending di java

Kalau mau merubahnya jadi Descending,tinggal rubah saja tanda > menjadi <  

Contoh kode dan output Bubble Sort secara Ascending Python :

Kalau mau descending,sama seperti tadi tinggal rubah tanda > menjadi <

Pencarian Data Secara Biner

Melanjutkan postingan sebelumnya mengenai metode pencarian data,kali ini kita akan beranjak ke metode pencarian yang lebih kompleks namun lebih efektif dari pada pencarian linear yaitu pencarian secara biner.Di pencarian biner ini kita tidak perlu mengecek elemen satu per satu namun di sini lebih ke menebak posisi data yang akan di cari.Kita membelah koleksi menjadi 2 bagian lalu kita periksa dari tengah,kiri dan kanan

Supaya lebih jelas saya kasih contoh real nya saja

• Saya punya data sebagai berikut 3,5,8,9,11,13,14,17,20,23,25,28,30,35.Di sini datanya harus sudah urut karena itu merupakan syarat dari pencarian secara biner.Saya ingin mencari angka 11 di koleksi tersebut
• jumlah data 14 maka 0+13//2 = 6 (data ke-7) yaitu 14 merupakan titik tengahnya
• 11 < 14 maka penanda kanan geser ke kiri menjadi data ke-6  sedangkan titik tengah barunya 0+5//2 = 2 (data ke-3) yaitu 8
• 11 > 8 maka penanda kiri geser ke kanan menjadi data ke-4 yaitu 9 sedangkan titik tengah barunya 3+5//2 = 8//2 = 4 (data ke-5) yaitu 11
• 11 = 11 (data ditemukan) pencarian pun dihentikan

Contoh kode untuk pencarian biner menggunakan Java

Kita coba data yang satunya lagi

Contoh kode dan Output di Python :