Shell Sort

-
                 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 nilai dalam setiap sub-daftar dan menukarkannya (jika perlu) dalam larik aslinya. Setelah langkah ini, array baru akan terlihat seperti ini


Kemudian, kita mengambil interval 2 dan celah ini menghasilkan dua sub-daftar - {14, 27, 35, 42}, {19, 10, 33, 44}


Kami membandingkan dan menukar nilai, jika diperlukan, dalam larik asli. Setelah langkah ini, array akan terlihat seperti ini -


Akhirnya, kita mengurutkan sisa array menggunakan interval nilai 1. Shell sort menggunakan semacam penyisipan untuk mengurutkan array.

Berikut adalah penggambaran langkah demi langkah -


      Baiklah kita akan memulai pembahasan materi tentang bagaimana Membuat Program Shell Sort di Bahasa Pemrograman Python. Silahkan cermati program di bawah ini :

  5. def shellSort(alist):
  6.     sublistcount = len(alist)//2
  7.     while sublistcount > 0:
  8.         for startposition in range(sublistcount):
  9.             gapinsertionSort(alist,startposition,sublistcount)
  10.         sublistcount = sublistcount // 2

  12. def gapinsertionSort(alist,start,gap):
  13.     for i in range(start+gap,len(alist),gap):
  14.         currentvalue = alist[i]
  15.         position = i
  16.         
  17.         while position>=gap and alist[position-gap] > currentvalue:
  18.             alist[position] = alist[position-gap]
  19.             position = position - gap
  20.             
  21.         alist[position] = currentvalue

  23. data = [35,14,33,19,42,27,10,44]
  24. shellSort(data)
  25. print(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

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