LANJUTAN DARI SHORTING

LANJUTAN DARI SHORTING

1. Jelaskan yang di maksud dengan shell sort!
2. Buatlah satu program tentang merge sort?
3. Sebutkan kelebihan dan kelemahan sort?
4. Sebutkan metode-metode penerapan sort?
5. Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :

JAWABAN

1.    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 /

2.    Program Sorting;
uses wincrt;
var  pilih:char;
     a,i,j,n:integer;
     data:array[1..50] of integer;
     y:integer;
     jwb:char;

Type
W=array[1..50]of integer;
var
Z:W;

{Sub Program Merge Sort}
procedure merge(var A,B:W;L,mid,R:integer);
var I,J,K,T:integer;
  begin
       I:=L;K:=L;J:=mid+1;
       repeat
       if A[I]
       Begin
            B[k]:=A[I];
            inc(I)
       end
       else
       begin
            B[K]:=A[J];
            inc(J);
       end;
       inc(k)
       until (I>mid)or (J>R);
       if I>mid then
          for T:=J to R do B[K+T-J]:=A[T]
       else
           for T:=I to mid do B[K+T-I]:=A[T]
  end;

Procedure order(var A,B:W;N,C:integer);
var I,T:integer;
  begin
       I:=1;
       while I<=(N-2*C+1)do
       begin
            Merge(A,B,I,I+C-1,I+2*C-1);
            I:=I+2*C;
       end;
       if(I+C-1)
                     Merge(A,B,I,I+C-1,N)
       else
           for T:=I to N do B[T]:=A[T]
  end;


Procedure mergesort(Var A:W;N:integer);
var C:integer;
B:W;
begin
     C:=1;
     while C
     begin
          Order(A,B,N,C);
          C:=2*C;
          Order(B,A,N,C);
          C:=2*C
     end;
end;

{Sub Program Quick Sort}
procedure change(var a,b:integer);
var c:integer;
begin
     c:=a;
     a:=b;
     b:=c;
end;

procedure quick_sort(L,R:integer);
var
mid,i,j:integer;
begin
     i:=L; j:=R; mid:=data[(L+R)div 2];
     repeat
           while data[i]
           while data[j]>mid do dec(j);
           if i<=j then
           begin
                change(data[i],data[j]);
                inc(i);dec(j);
           end;
     until i>j;
     if L
     if i
end;

label ulang;
begin
     writeln('Selamat datang di program Sorting');
     write('Ini adalah program yang akan ');
     writeln('membantu anda mengurutkan data');
     ulang:
     writeln;
     writeln('Silakan pilih salah satu menu di bawah ini :');
     writeln('  1. Selection Sort');
     writeln('  2. Buble Sort');
     writeln('  3. Insertion Sort');
     writeln('  4. Quick Sort');
     writeln('  5. Merge Sort');
     write('Masukkan nomor menu pilihan anda: ');readln(pilih);
     case pilih of
     '1':
       begin
          clrscr;
          writeln('Selamat Datang di Program Selection Sort');
          writeln;
          write('Banyaknya data: ');readln(n);
          write('Masukkan datanya ');
          writeln('(tekan enter setiap memasukkan satu data): ');
          for i:=1 to n do readln(data[i]);
          for j:=1 to (n-1) do
          begin
               for i:=j+1 to n do
               begin
                    y:=data[j];
                    if data[i]
                    begin
                         data[j]:=data[i];
                         data[i]:=y;
                    end;
               end;
          end;
          writeln;
          writeln('Data setelah diurutkan: ');
          for i:=1 to n do write(data[i]:5);
       end;
     '2':
       begin
          clrscr;
          writeln('Selamat Datang di Program Bubble Sort');
          writeln;
          write('Banyaknya data: ');readln(n);
          write('Silakan masukkan datanya ');
          writeln('(tekan enter setiap memasukkan satu data): ');
          for i:=1 to n do readln(data[i]);
          for i:=2 to n do
          for j:=n downto i do
          begin
               y:=data[j];
               if data[j]
               begin
                    data[j]:=data[j-1];
                    data[j-1]:=y;
               end;
          end;
          writeln;
          writeln('Data setelah diurutkan: ');
          for i:=1 to n do write(data[i]:5);               
       end;
     '3':
       begin
          clrscr;
          writeln('Selamat Datang di Program Insertion Sort');
          writeln;
          write('Berapa banyaknya data? ');readln(n);
          write('Masukkan datanya ');
          writeln('(tekan enter setiap memasukkan satu data) :');
          for i:=1 to n do readln(data[i]);
          for i:=2 to n do
          begin
               y:=data[i];
               j:=i-1;
               while (y1) do
               begin
                    data[j+1]:=data[j];
                    j:=j-1;
               end;
               if y>=data[j] then data[j+1]:=y
               else
               begin
                    data[j+1]:=data[j];
                    data[j]:=y;
               end;
          end;
          writeln;
          writeln('Data setelah diurutkan:');
          for i:=1 to n do write(data[i]:5);
       end;
     '4':
       begin
          clrscr;
          writeln('Selamat Datang di Program Quick Sort');
          writeln;
          write('Banyaknya data ');readln(n);
          write('Silakan masukkan datanya ');
          writeln('(tekan ENTER setiap memasukkan satu data):');
          for a:=1 to n do
          readln(data[a]);
          for a:=1 to n do quick_sort(1,n);
          writeln('Data terurutnya adalah : ');
          for a:=1 to n do writeln(data[a]:10);
       end;
     '5':
       begin
          clrscr;
          writeln('Selamat Datang di Program Merge Sort');
          writeln;
          write('Banyaknya data : ');readln(n);
          writeln('Masukkan datanya ');
          writeln('(tekan ENTER setiap memasukkan satu data): ');
          for a:=1 to n do readln(Z[a]);
          for a:=1 to n do mergesort(Z,n);
          writeln('Data terurutnya adalah : ');
          for a:=1 to n do writeln(Z[a]:10);
       end;
     end;
     writeln;
     write('TEKAN ENTER jika anda sudah selesai memahami data terurut');
     readln;
     clrscr;
     write('Apakah anda mau mengulang lagi? (jawab y atau t): ');
     readln(jwb);
     if jwb='y' then goto ulang;
     writeln;
     write('Anda memilih untuk meninggalkan program sorting ini.');
     writeln(' Terima kasih...');
     writeln;
     writeln('Tekan ENTER untuk menutup jendela ini');
     readln;
     donewincrt;
end. 

3.      Insertion Sort :

Kelebihan

1.       Sederhana dalam penerapannya.

2.       Mangkus dalam data yang kecil.

3.       Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.

4.       Mangkus dalam data yang sebagian sudah terurut.

5.       Lebih mangkus dibanding Bubble Sort dan Selection Sort.

6.       Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.

7.       Stabil.

Kekurangan

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

2.       Untuk larik yang jumlahnya besar ini tidak praktis.

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

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

4.      Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan “mengapung” untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan “diapungkan” (ke indeks terkecil), artinya diangkat ke “atas”(indeks terkecil) melalui pertukaran

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

tugas tree

TUGAS TREE

apa yang di maksud dengan tree dan binary treeapa yang di maksud dengan tree dan binary tree

  Pengertian Tree dalam Struktur Data

 Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkanhubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemenKHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untukjelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree

}Parent : predecssor satu level di atas suatu node.

}Child : successor satu level di bawah suatu node.

}Sibling : node-node yang memiliki parent yang sama dengan suatu node.

}Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

}Size : banyaknya node dalam suatu tree.

}Height : banyaknya tingkatan/level dalam suatu tree.

}Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

}Leaf : node-node dalam tree yang tak memiliki seccessor.

}Degree : banyaknya child yang dimiliki suatu node.

  Pengertian Binaary Tree dalam Struktur Data 

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

Tree

  Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).

istilah-istilah umum dalam tree

  Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

a) Prodecessor : node yang berada diatas node tertentu.

b) Successor : node yang berada di bawah node tertentu.

c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

e) Parent : predecssor satu level di atas suatu node.

f) Child : successor satu level di bawah suatu node.

g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.

h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

contoh program tree

uses crt;

Type

Tree = ^Simpul;

Simpul = Record

Info : char;

Kiri : Tree;

Kanan : Tree;

End;

Function BARU(Hrf : Char) : Tree;

Var Temp : Tree;

Begin

New(Temp);

Temp^.Info := Hrf;

Temp^.Kiri := NIL; Temp^.Kanan := NIL;

BARU := Temp;

End;

Procedure MASUK(Var Pohon : Tree; Hrf : Char);

Begin

If Pohon = NIL Then

Pohon := BARU(Hrf)

Else

Begin

If Pohon^.Info > Hrf then

MASUK(Pohon^.Kiri,Hrf)

Else If Pohon^.Info < Hrf then

MASUK(Pohon^.Kanan,Hrf)

Else

Writeln('Karakter', Hrf, 'Sudah ada di Tree');

End;

End;

Procedure PREORDER(Temp : Tree);

Begin

If Temp <> NIL Then

Begin

Write(Temp^.Info,' ');

PREORDER(Temp^.Kiri);

PREORDER(Temp^.Kanan);

End;

End;

Procedure INORDER(Temp : Tree);

Begin

If Temp <> NIL Then

Begin

INORDER(Temp^.Kiri);

Write(Temp^.Info,' ');

INORDER(Temp^.Kanan);

End;

End;

pengertian AVL tree

  AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

 Single Rotation

  Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar 2.

Sebutkan beberapa jenis tree yang memiliki sifat khusus

  v Create : Membentuk binary tree baru yang masih kosong.

  v Clear : Mengosongkan binary tree yang sudah ada.

  v Empty : Function untuk memeriksa apakah binary tree masih kosong.

  v Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

  v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

  v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

  v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.