Soal :

1. Jelaskan apa yang dimaksud dengan shell sort !
2. Buatlah suatu program tentang merge sort !
3. Sebutkan kelebihan dan kelemahan sort !
4. Sebutkan metode-metode teknik sort !
5. Siapakah yang pertama kali menemukan algoritma merge sort ?

Pengertian 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.

Contoh program merge sort dalam pascal
type INTARRAY = array[1..100000] of integer;
procedure gen_array(var A:INTARRAY; N:integer);
var i:integer;
begin
for i:=1 to N do A[i]:=Random(10*N);
end;
{copia l’array X in Y}
procedure copy_array(var X, Y:INTARRAY; n:integer);
var i:integer;
begin
for i := 0 to N do Y[i] := X[i];
end;
Function min(a,b:integer):integer;
begin if a
 else min := b;
end;

Soal

1)      Jelaskan apa yang di maksud dengan tree dan binary tree

2) Uraikan istilah-istilah umum dalam tree

3) Buatlah 1 contoh program tree

4) Sebutkan pengertian AVL tree

5) Sebutkan beberapa jenis tree yang memiliki sifat khusus

Pengertian tree dan binary tree

a)      Binery tree

Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Node pada Binary Tree

Jumlah maksimum node pada setiap tingkat adalah 2ⁿ, Node pada binary tree maksimumnya berjumlah 2ⁿ-1.

b)      Pengertian tree

            Kumpulan node yang saling terhubung satu sama lain dalam suatu  kesatuan yang membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu  cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut  hanya tampak sebagai kumpulan node-node  dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan  hubungan yang hirarkis (one-to-many) dan tidak linier antara lemen-elemennya.

Deklarasi Pohon

            Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun  struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam  setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang  kanan, dan informasi yang akan disimpan dalamsimpul tersebut.

Soal

1. Buatlah 1 contoh program insertion sort.
2. Tuliskan pengertian sorting menurut pendapat anda masing-masing.
3. Buatlah contoh program bouble sort dalam bahasa pascal
4. Tuliskan algoritma quick rekursif.
5. Sebutkan dan jelaskan metode-metode sorting.

Contoh Program Insertion Sort.

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <iomanip>

#ifdef __cplusplus__

#include <cstdlib>

#else

#include <stdlib.h>

#endif

using namespace std;

int main()

{

int x[5];

int i;

int temp;

int minindex;

int j;

if (system("CLS")) system("clear");

cout << " >> Program Selection Sort << \n" << endl;

cout << "masukkan nilai x :\n";

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

{

cout << "x[" << i << "] = "; cin >> x[i];

}

cout << "\n Data sebelum di sort :";

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

{

cout << setw(4) << x[i];

}

for (i = 0; i<5 - 1; i++) //perulangan iterasi

        {

                minindex = i;

                for (j = i + 1; j<5; j++) //perulangan membandingkan data

                {

                        if (x[minindex]>x[j])

                        {

                                minindex = j;

                        }

                }

                temp = x[i];

                x[i] = x[minindex];

                x[minindex] = temp;

        }

        cout << "\n Data setelah di sort :";

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

        {

                cout << setw(4) << x[i];

        }

        getchar();

        cout << endl;

        system("pause");

}

                

SOAL

1. Apa kelebihan dari Searching ?
2. Sebutkan jenis searching dalam algoritma !
3. Apa yang dimaksud dengan searching dan tujuannya berikan 1 contoh !
4. Berikan contoh program pencarian binary !
5. Apa pengertian dari searching ?

Kelebihan Searching

Kelebihannya yaitu tidak perlu membandingkan data yang dicari dengan seluruh data array yang ada, cukup melalui titik tengah kemudian kita bisa menentukan ke mana selanjutnya mencari data yang ingin dicari.

Jenis searching dalam algoritma

a)      Sequential search

Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling mudah. Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal). Sedangkan kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).

Sequential search memiliki proses sebagai berikut:

q    Tentukan banyaknya data yang akan di olah, misal banyak data adalah N.

q   Tentukan data apa yang akan dicari, misal data yang akan dicari adalah C.

q   Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan, missal counternya adalah K.

q   Inisialisasikan K =0

q  Lakukanlah perulangan sebanyak N kali

q   Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang diolah sama dengan data yang dicari.

q   Jika ternyata sama K=K+1

q   Jika tidak, lanjutkan proses perulangan .

q   Setelah proses perulangan berhenti, periksalah nilai K.

q   Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data /array dan tampilkan   nilai K ke layer sebagai jumlah data yang ditemukan.

q  Jika nilai K=0, artinya data yang dicari tidak ditemukan dalam data / array dan tampilkan ke layar bahwa data tidak ditemukan

q  Proses selesai.

Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah banyak. Disarankan proses ini digunakan pada jumlah data yang sedikit saja.

b)      Binary Search.

            Pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. Jika terdapat N buah data yang akan diolah, data yang dicari akan dibandingkan dengan data ke-N jika data ke-N lebih besar dari data yang dicari maka akan dilakukan pembagian data menjadi dua bagian. Kemudian ujung data pada setiap bagian dibandingkan lagi dengan nilai yang akan dicari.

Soal

Berikan gambaran/ilustrasi dari kasus antrian berikut !

1.      Diketahui suatu antrian / queue dengan max= 6.

2.      Lakukan enqueu 4 elemen ke dalam antrian, dimanakah posisi Head dan Tail ?

3.      Kemudian lakukan dequeue 2 elemen dari antrian . Maka dimana posisi Head dan Tail ?

4.      Dari keadaan diatas, bagaimanakah kondisi IsFull dan IsEmpty nya ?

QUEUE

Secara harfiah queue dapat diartikan sebagai antrean. Queue merupakan kumpulan data dengan penambahan data hanya dapat dilakukan melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir.

Elemen yang pertama kali masuk kedalam queue disebut elemen depan (front/head of queue), sedangkan elemen yang terakhir kali masukk queue disebut elemen belakang (rear/tail of queue).

Aturan penambahan dan penghapusan elemen pada queue, yaitu pada penambahan elemen selalu di lakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang sudah masuks ebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan.

Contoh Program

PROGRAM ANTRIAN_ARRAY_STATIS;

       

      USES winCRT;

         CONST

            MAX_QUEUE = 6;

         TYPE

            QUEUE = ARRAY[1..MAX_QUEUE] OF CHAR;

       

      VAR

         ANTRIAN      : QUEUE;

         I  : INTEGER;

         DEPAN        : INTEGER;

BELAKANG     : INTEGER;

         PILIH        : CHAR;

       ELEMEN       : CHAR;

PROCEDURE CLEAR;

      VAR

         I : INTEGER;

            BEGIN

               FOR I := 1 TO 10 DO

               BEGIN

                  GOTOXY(62 - 4 * I, 19);WRITELN(' ');

         END;

      END; {*Procedure HUPUS*}

       

      {****************************************************************

         * Fungsi untuk menge-cek keadaan antrian ( Penuh atau Kosong ) *

         ****************************************************************}

{***************************************

 * Procedure menampilkan antrian data. *

 ***************************************}

   PROCEDURE TAMPILKAN( X :INTEGER);

      VAR

         I : INTEGER;

               BEGIN

         FOR I := 1 TO X DO

         BEGIN

            GOTOXY(18 + 4 * I, 19);

            WRITE(ANTRIAN[I]);

           

         END;

      END; {*Procedure TAMPILAKAN*}