Insertion sort

-

                  Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort. Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang "tepat" untuk setiap elemen array, dengan cara sequential search. 
                 Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya ang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai "pass"), dengan indeks dimulai dari 0. Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.
      Baiklah kita akan memulai pembahasan materi tentang bagaimana Membuat Program Insertion Sort di Bahasa Pemrograman Python. Silahkan cermati program di bawah ini :

Versi 1:
  3. data = [54,26,93,17,77,31,44,55,20]
  4. def insertion1(listData):
  5.     for i in range(len(listData)):
  6.         value = listData[i]
  7.         posisi = i
  8.         while posisi > 0 and listData[posisi-1] > value :
  9.             listData[posisi]=listData[posisi-1]
  10.             posisi -= 1
  11.             print("inner =", listData)
  12.         listData[posisi] = value
  13.     print(listData)

  15. insertion1(data)
Versi 2:
  2. data = [54,26,93,17,77,31,44,55,20]
  3. def insertion2(listData):
  4.     for i in range(len(listData)-1,-1,-1):
  5.         value = listData[i]
  6.         posisi = i
  7.         while posisi < (len(listData)-1) and listData[posisi+1] < value :
  8.             listData[posisi]=listData[posisi+1]
  9.             posisi += 1
  10.             print("inner =", listData)
  11.         listData[posisi] = value
  12.     print(listData)

  14. insertion2(data)

Komentar

Posting Komentar

Postingan populer dari blog ini

Infix, Prefix dan Postfix pada Python

-
Gambar
A. Definisi Infix adalah cara penulisan atau ungkapan yang meletakan operator di tengah antara 2 operand dalam hal ini dalam kurung sangat menentukan posisi. Contoh Infix : A + B ( A - B ) * C Prefix adalah cara penulisan atau ungkapan yang meletakan operator disebelah kiri 2 operand dan dalam kurung sangat menentukan posisi. Contoh Prefix : + A B * - A B C Posfix adalah cara penulisan yang meletakan operator disebelah kanan 2 operand dan posisi operand yang berada di dalam kurung sangat menentukan. Contoh Postfix : A B + A B - C * B. Ilustrasi C. Algoritma Berikut ini algoritma dari konversi Infix ke Postfix: Buat presisi atau kekuatan operator ( Penjumlahan dan Pengurangan bernilai 2 , Perkalian dan Pembagian bernilai 3 , Kurang buka dan tutup bernilai 1 ) Input data dalam bentuk infix Pisahkan data infix menggunakan split menjadi bentuk List Periksa semua data yang berada di dalam list secara urut mulai dari a
Baca selengkapnya

Shell Sort

-
Gambar
                 Shell sort adalah algoritma penyortiran yang sangat efisien dan didasarkan pada algoritma penyortiran. Algoritma ini menghindari pergeseran besar seperti dalam kasus penyisipan, jika nilai yang lebih kecil ke paling kanan dan harus dipindahkan ke paling kiri. Algoritma ini menggunakan semacam penyisipan pada elemen yang tersebar luas, pertama untuk mengurutkannya dan kemudian mengurutkan elemen yang kurang luas. Jarak ini disebut sebagai interval. Interval ini dihitung berdasarkan rumus Knuth -                 Bagaimana Shell Sort Bekerja? Mari kita perhatikan contoh berikut untuk memiliki gagasan tentang cara kerja Shell sort. Kami mengambil array yang sama yang telah kami gunakan dalam contoh kami sebelumnya. Untuk contoh dan kemudahan pemahaman kami, kami mengambil interval 4. Buat daftar sub-virtual dari semua nilai yang berada pada interval 4 posisi. Di sini nilai-nilai ini adalah {35, 14}, {33, 19}, {42, 27} dan {10, 44} Disisni kita membandingkan nila
Baca selengkapnya

Dequeue

-
Gambar
DeQueue DeQueue, dikenal juga sebagai antrian berujung dua (double-ended), adalah suatu koleksi item terurut serupa dengan queue. Perbedaannya? Sifat tidak terikat untuk penambahan dan penghapusan item-item dari antrian. Item baru dapat ditambahkan ke depan atau belakang. Karena itu, item yang ada dapat dihapuskan dari salah satu ujung. Struktur linier hibrida ini menyediakan semua kapabilutas stack dan antrian dalam satu struktur data. Berikut ini adalah beberapa operasi yang dapat diberlakukan terhadap Deque : 1. deque(), membuat suatu deque baru yang kosong. Tidak perlu parameter dan     mengembalikan suatu deque kosong. 2. addFront(item), menambahkan suatu item baru ke depan dari deque. Perlu item dan tidak     mengembalikan apapun. 3. addRear(item), menambahkan suatu item baru ke ekor dari deque. Perlu item dan tidak     mengembalikan sesuatu. 4. removeFront(), menghapus item depan dari deque. Tidak perlu parameter dan     mengembalikan item. Deque termodifi
Baca selengkapnya