Shell Sort (Metode Shell)
Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat dituliskan sebagai berikut :
1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
Stack (Tumpukan)
stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari tumpukan tersebut. Tumpukan dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri tumpukan:
- TOP merupakan sebutan untuk elemen paling atas dari suatu stack
- Elemen TOP merupakan elemen yang paling akhir ditambahkan
- Elemen TOP diketahui
- penambahan dan penghapusan elemen selalu dilakukan di TOP
- LIFO
Pemanfaatan tumpukan:
- Perhitungan ekspresi aritmetika (posfix)
- algoritme backtraking (runut balik)
- algoritme rekursif
Operasi tumpukan :
- InsertFirst () biasa disebut Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke tumpukan
- DeleteFirst () biasa disebut Pop (output E : typeelmt, input/output data : stack ) : menghapus sebuah elemen tumpukan
- IsEmpty () : mengecek apakah stack kosong atau ada elemennya
- IsFull () : mengecek apakah stack telah penuh atau belum
- Clear () : menghapus semua data
- Peek () : melihat data TOP
Hashing
transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Menurut bahasa, hashing berarti memenggal dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.
Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hash-nya. Pada pencarian suatu nilai pada tabel hash, yang pertama dilakukan adalah menghitung nilai hash dari kunci atau nilai aslinya, kemudian membandingkan kunci atau nilai asli dengan isi pada memori yang beralamat nomor hash-nya. Dengan cara ini, pencarian suatu nilai dapat dilakukan dengan cepat tanpa harus memeriksa seluruh isi tabel satu per satu.
Contoh program untuk mater diatas :
Shell Sort
Stack
Hashing
table=[None]*11
print ("Data =[54,26,93,17,77,31,44,55,20,65,53]")
def hash(x):
return x % 11
def insert(table,key,value):
index = hash(key)
if table[index] == None:
table[index] = value
else:
collusion = index
found = False
index = collusion + 1
if index >= len(table)-1:
index = 0
i = 1
while (index<=len(table)-1) and not(found):
if table[index] == None:
found = True
table[index] = value
index=(collusion+(i**2))%11
i += 1
def cari (table):
search = int(input("Masukkan angka yang ingin dicari : "))
Data =[54,26,93,17,77,33,44,55,20,65,53]
for x in range(len(Data)-1):
insert(table,Data[x],Data[x])
print(table)
posisi= 0
counter = 0
last = len(table)-1
found = False
while posisi <= last and not found:
counter += 1
if table[posisi] == search:
found = True
else:
posisi = posisi + 1
if found:
print('Data ditemukan',posisi)
print(' Iterasi yang terjadi adalah',counter)
else:
print('Data tidak ditemukan')
print('Jumlah iterasi yang terjadi adalah',counter)
if search in table:
table.remove(search)
table.append(None)
else :
insert(table,search,search)
print(table)
cari(table)
Nah demikian ulasan tentang Shell Sort, Stack dan Hashing. mudah-mudahan bermanfaat bagi teman-teman sekalian.terima kasih ^_^
Contoh program untuk mater diatas :
Shell Sort
Stack
Hashing
- Hashing Close Order
- Hashing Linier
table=[None]*11
def hash(x):
return x % 11
def insert(table,key,value):
index = hash(key)
if table[index] == None:
table[index] = value
else:
collusion = index
found = False
index = collusion + 1
if index >= len(table)-1:
index = 0
while (index<=len(table)-1) and not(found):
if table[index] == None:
found = True
table[index] = value
index += 1
def cari (table):
search = int(input("Masukkan angka yang ingin dicari : "))
Data =[5,6,9,7,17,3,4,5,2]
for x in range(len(Data)-1):
insert(table,Data[x],Data[x])
print(table)
posisi= 0
counter = 0
last = len(table)-1
found = False
while posisi <= last and not found:
counter += 1
if table[posisi] == search:
found = True
else:
posisi = posisi + 1
if found:
print('Angka ditemukan di indeks nomor',posisi)
print('Jumlah iterasi yang terjadi adalah',counter)
else:
print('Angka tidak ditemukan')
print('Jumlah iterasi yang terjadi adalah',counter)
if search in table:
table.remove(search)
table.append(None)
else :
insert(table,search,search)
print(table)
cari(table)
- Hashing Time
from __future__ import print_function
import time
import random
waktu = time.time()
print("No.1 Linear Probbing 100 data".center(80))
table = [None]*110
def Linear(x):
return x % 11
def insert(table,keys,value):
index = Linear(keys)
if table[index]==None:
table[index]=value
else:
tumbukan=index
found = False
ind = tumbukan + 1
if ind >= len(table)-1:
ind = 0
while (ind<=len(table)-1) and not(found):
if table[ind]== None:
found = True
table[ind]=value
ind +=1
return table
keys = []
value = []
for i in range (0,100):
keys.append(random.randint(11,100))
value.append(keys)
linear = insert(table,keys[i],value[0][i])
print (linear)
waktu1 = time.time()
print ("Waktu sekarang :", waktu1)
print("Quadratic Probbing 100 data".center(80))
table1 = [None]*100
def Quadrat(x):
return x% 11
def insert1(table1,keys1,value1):
index = Quadrat(keys1)
if table1[index]==None:
table1[index]=value1
else:
tumbukan=index
found = False
ind = tumbukan + 1
if ind >= len(table1)-1:
ind = 0
i = 1
while (ind<=len(table1)-1) and not(found):
i+=1
if table1[ind]== None:
found = True
table1[ind]=value1
ind = (ind+(i*i))
return table1
keys1 = []
value1 = []
for i in range (0,100):
keys1.append(random.randint(11,100))
value1.append(keys1)
quadratic=insert1(table1,keys1[i],value1[0][i])
print (quadratic)
waktu2 = time.time()
print ("Waktu sekarang :", waktu2)
print("Chaining(Close Address) 100 data".center(80))
table2 = [[]]*20
def Chaining(x):
return x % 11
def insert2(table2,keys2,value2):
index = Chaining(keys2)
if table2[index]==[]:
table2[index]=[value2]
else:
table2[index].append(value2)
return table2
keys2 = []
value2 = []
for i in range (0,100):
keys2.append(random.randint(11,100))
value2.append(keys2)
chaining = insert2(table2,keys2[i],value2[0][i])
print (chaining)
waktu3 = time.time()
print ("Waktu sekarang :", waktu3)
- Hasing Quadratic
table=[None]*11
print ("Data =[54,26,93,17,77,31,44,55,20,65,53]")
def hash(x):
return x % 11
def insert(table,key,value):
index = hash(key)
if table[index] == None:
table[index] = value
else:
collusion = index
found = False
index = collusion + 1
if index >= len(table)-1:
index = 0
i = 1
while (index<=len(table)-1) and not(found):
if table[index] == None:
found = True
table[index] = value
index=(collusion+(i**2))%11
i += 1
def cari (table):
search = int(input("Masukkan angka yang ingin dicari : "))
Data =[54,26,93,17,77,33,44,55,20,65,53]
for x in range(len(Data)-1):
insert(table,Data[x],Data[x])
print(table)
posisi= 0
counter = 0
last = len(table)-1
found = False
while posisi <= last and not found:
counter += 1
if table[posisi] == search:
found = True
else:
posisi = posisi + 1
if found:
print('Data ditemukan',posisi)
print(' Iterasi yang terjadi adalah',counter)
else:
print('Data tidak ditemukan')
print('Jumlah iterasi yang terjadi adalah',counter)
if search in table:
table.remove(search)
table.append(None)
else :
insert(table,search,search)
print(table)
cari(table)
Nah demikian ulasan tentang Shell Sort, Stack dan Hashing. mudah-mudahan bermanfaat bagi teman-teman sekalian.terima kasih ^_^
Tidak ada komentar:
Posting Komentar