Tugas Pendahuluan Pertemuan 10 LINKED LIST

PERTEMUAN  X

LINKED LIST

TUGAS PENDAHULUAN

1.      1. Apa yang dimaksud dengan Linked List!

2.      2. Jelaskan perbedaan antara singly linked list, doubly linked list, dan circular linked list!

3.      3. Jelaskan operasi-operasi pada singly linked list!

4.      4. Jelaskan operasi-operasi pada doubly linked list!

Jawaban

1.      1. Linked List adalah struktur berupa rangkaian elemen saling berkait dimana tiap elemen dihubungkan ke elemen lain melalui pointer. Pointer juga merupakan alamat dari sebuah elemen.

2.      -  Singly Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya, biasanya field pada tail menunjuk ke NULL.

-          Doubly Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

-          Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL.

3.      3. Operasi-operasi pada singly linked list:

Insert = Istilah  Insert berarti menambahkan  sebuah  simpul baru ke dalam  suatu linked  list.

Konstruktor = Fungsi ini membuat sebuah  linked  list yang baru dan masih kosong. 

IsEmpty = Fungsi ini menentukan apakah  linked list kosong atau  tidak.

Find First = Fungsi ini mencari elemen pertama dari linked  list.

Find Next = Fungsi ini mencari elemen  sesudah elemen yang ditunjuk now. 

Retrieve = Fungsi  ini  mengambil  elemen  yang  ditunjuk  oleh  now.  Elemen tersebut  lalu dikembalikan oleh fungsi. 

Update = Fungsi ini mengubah elemen yang ditunjuk oleh  now dengan  isi dari sesuatu. 

Delete Now = Fungsi  ini  menghapus  elemen  yang  ditunj uk  oleh  now.  Jika yang dihapus  adalah elemen pertama dari  linked  list (head), head akan berpindah ke elemen berikut.

4.      4. Operasi-operasi pada doubly linked list:

Insert Tail = Fungsi  insert  tail  berguna  untuk  menambah  simpul  di  belakang (sebelah  kanan)  pada sebuah linked list. 

Insert Head = Sesuai dengan namanya, fungsi Insert Head berguna untuk menambah simpul di depan (sebelah  kiri). Fungsi  ini  tidak  berada  jauh  dengan  fungsi  Insert Tail yang telah dijelaskan sebelumnya.

Delete Tail = Fungsi  Delete  Tail  berguna  untuk  menghapus  simpul  dari  belakang.  Fungsi  ini merupakan kebalikan dari fungsi Insert Tail yang menambah simpul dibelakang. Fungsi Delete  Tail  akan  mengarahkan  Now  kepada  Tail  dan kemudian  memanggil  fungsi Delete Now.

Delete Head  = Fungsi  Delete  Head  merupakan  kebalikan  dari  fungsi  Delete  Tail yang  menghapus simpul  dari  belakang,  sedangkan  Delete  Head  akan  menghapus simpul  dari  depan (sebelah  kiri).  Fungsi  Delete  Head  akan  mengarahkan  Now kepada  Head  dan kemudian memanggil fungsi Delete Now. 

Read More

Tugas Pendahuluan Pertemuan 9 SORTING (Lanjut 2)

PERTEMUAN   IX

SORTING (Lanjut 2)

TUGAS PENDAHULUAN

1.      1. Jelaskan kekurangan menggunakan metode shell sort dan insertion sort dengan metode –metode sorting lainnya!

2.      2. Jelaskan perbedaan program sorting dengan menggunakan antara metode shell sort dan insertion sort!

3.      3. Jelaskan tahapan-tahapan sorting menggunakan metode shell sort!

4.      4. Jelaskan tahapan-tahapan sorting menggunakan metode insertion sort!

Jawaban

1.      1. Kekurangan metode shell sort yaitu:

-          Membutuhkan method tambahan.

-          Sulit untuk membagi masalah.

Kekurangan metode insertion sort yaitu:

-          Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.

-          Untuk larik yang jumlahnya besar ini tidak praktis.

-          Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.

-          Membutuhkan waktu 0(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.

2.      2. a. Shell sort

metode pengurutan yang hampir sama dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir.

     b. insertion sort

salah satu metode sorting dengan cara menyisipkan/insert. Pada dasarnya insertion sort memilih data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan.

3.      3. Tahapan-tahapan sorting menggunakan metode shell sort.

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 makna kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N/2. Demikian seterusnya sampai seluruh data dibandingkan sehinga 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.

4.      4. Tahapan-tahapan sorting menggunakan metode insertion sort.

Dalam pengurutan datanya. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakkan didepan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

Catatan: Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil akan dibandingkan dengan data-data yang ada disebelah kiri/data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4,... dan seterusnya). Proses akan berlangsung sampai data-data terurutkan dengan benar.

Read More

Tugas Pendahuluan Pertemuan 8 SORTING (Lanjut 1)

PERTEMUAN   VIII

SORTING (Lanjut 1)

TUGAS PENDAHULUAN

1.      1. Jelaskan kekurangan menggunakan metode maximum/minimum sort dengan metode-metode sorting lainnya!

2.      2. Jelaskan perbedaan program sorting dengan menggunakan antara metode maximum sort dan minimum sort!

3.      3. Jelaskan tahapan-tahapan sorting menggunakan metode maximum sort!

4.      4. Jelaskan tahapan-tahapan sorting menggunakan metode minimum sort!

Jawaban

1.      1. Kekurangan menggunakan metode maximum/minimum sort dengan metode-metode sorting lainnya :

-          Membutuhkan method tambahan.

-          Sulit untuk digabungkan kembali.

-          Perlu dihindari untuk penggunaan data lebih dari 1000 tabel karena akan menyebabkan kompleksitas yang lebih tinggi dan kurang praktis.

2.      2. Perbedaannya maximum sort memilih elemen maximum sebagai basis pengurut, sedangkan minimum sort memilih elemen minimum sebagai basis pengurutan. Dan saya juga sudah mencoba program yang ada pada modul bagian sorting lanjut a dan b dimana program maximum sort menggunakan imaks untuk mengurutkan data secara menurun (dari besar ke kecil). Sedangkan minimum sort menggunakan imin dan U-- untuk mengurutkan data secara menurun pada dasarnya programnya sama yang membedakan hanya itu saja menurut saya pribadi.

3.      3. Saya jujur masih sedikit kurang paham mengenai tahapan-tahapan sorting menggunakan metode maximum sort, tetapi saya hanya dapat tahapan-tahapan pada maximum sort seperti dibawah ini.

-          Cari elemen maximum didalam [0—(N-1)].

Pertukaran elemen max dengan elemen L[N-1].

-          Cari elemen maximum didalam L[0--N-2].

Pertukaran elemen max dengan elemen L[N-2].

-          Cari elemen maximum didalam L[0--N-3].

Pertukaran elemen maximum dengan elemen L[N-3].

Elemen yang tersisa adalah L[0], tidak perlu diurut hanya satu-satunya, jadi pada setiap untuk pengurutan terdapat proses pencari harga max dan proses pertukaran dua buah elemen array.

4.      4. Tahapan-tahapan sorting menggunakan metode minimum sort.

-          Cari elemen minimum didalam [0--(N-1)].

Pertukaran elemen min dengan elemen L[N-1].

-          Cari elemen minimum didalam [0--N-2].

Pertukaran elemen min dengan elemen L[N-2].

-          Cari elemen minimum didalam [0-(N-3)].

Pertukaran elemen minimum dengan elemen L[N-3].

Pada dasarnya metode maximum dan minimum sort itu sama saja yang membedakan adalah metode pencariannya, dimana metode maximum mencari nilai yang besar dan metode minimum hanya mencari nilai yang terkecil saja.

Read More

Tugas Pendahuluan Pertemuan 7 SORTING

PERTEMUAN  VII

SORTING

TUGAS PENDAHULUAN

1.      1. Apa yang dimaksud dengan sorting!

2.      2. Jelaskan perbedaan dari pengurutan internal dan pengurutan eksternal!

3.     3. Jelaskan perbedaan metode-metode sorting seperti : Bubble Sort, Quick Sort, Selection Sort, Merge Sort, Tree Sort, Maximum Sort, dan Insertion Sort!

4.      4. Buatlah contoh program sederhana menggunakan sorting!

Jawaban

1.      1. Sorting (pengurutan) adalah proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu. Sorting dapat dibedakan menjadi dua jenis yaitu ascending dan descending.

2.    2. - Pengurutan Internal (Internal Sort) yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai pengurutan tabel.

- Pengurutan Eksternal (External Sort) yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.

3.                   3. a.  Bubble Sort

Proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah.

b.  Quick Sort

Metode terdapat dalam proses pengurutan data dengan menggunakan prinsip rekursif. Metode ini menggunakan strategi “Pecah Belah” dengan mekanisme.

c.  Selection Sort

Algoritma Selection Sort yang memilih elemen maksimum/minimum array, lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir array (tergantung pada urutannya ascending/descending).

d.  Merge Sort

Algoritma yang berdasarkan dari Strategi divide-and-conquer. Algoritma ini terdiri dari dua bagian utama, yaitu bagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut.

e.  Insertion Sort

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.

f.  Tree Sort

Metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output : Pre Order, In order, Post Order.

g.  Maximum Sort

Proses memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan.

4.      4. Program sederhana menggunakan sorting.

#include<iostream>

#include<stdio.h>

#include<conio.h>

using namespace std;

int sort_function (const void *a, const void *b);

char list[5][4] = {"cat", "car", "cab", "cap", "can"};

int main()

{

    printf(" Nama : Muhammad Zuhri Kelas : 04TPLP011 NIM: 2016140614 ");

    printf(" ======================== ");

    int x;

    qsort(( void *)list,5, sizeof(list[0]), sort_function);

    for (x =0; x<5; x++)

    printf("%s ",list[x]);

    return 0;

}

int sort_function(const void *a, const void *b)

{

    return (strcmp ((char *) a,(char *)b));

}

Read More