LANJUTAN TUGAS SORTING

SOAL

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 teknik sort?
5. Siapakah yang pertama kali menemukan algoritma merge sort?

SHELL SORT

Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen  yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut.

Kemudain elemen kedua kita bandingkan dengan eleen lain dengan jarak yang sama seperti jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.

Program Tentang Merge Sort

program merge_sort;

uses wincrt;

var

nil1:Array[1..10] of integer;

n,i,j,dum:integer;

begin

clrscr;

write('mau anda isi berapa data acak(integer)=');readln(n);

for i:=1 to n do

begin

write('Data ke',i,':');readln(nil1[i]);

end;

{*penyapuan proses}

for i:=1 to n-1 do

for j:=1 to n do

begin

if nil1[j]<nil1[i] then

begin

dum:=nil1[j];

nil1[j]:=nil1[i];

nil1[i]:=dum;

end;

end;

writeln;

writeln('hasil marge sort');

for i:=1 to n do

write(nil1[i]:3);

readln;

end.

Kelebihan Dan Kelemahan Sort

v  BUBLE SORT KELEBIHAN & KELEMAHAN

Kelebihan Bubble Sort

– Metode Buble Sort Merupakan Metode Yang Paling Simpel

– Metode Buble Sort Mudah Dipahami Algoritmanya

– Mudah Untuk Diubah Menjadi Kode.

– Definisi Terurut Terdapat Dengan Jelas Dalam Algoritma.

– Cocok Untuk Pengurutan Data Dengan Elemen Kecil Telah Terurut

Kelemahan Bubble Sort

Meskipun Simpel Metode Bubble Sort Merupakan Metode Pengurutan Yang Paling Tidak Efisien. Kelemahan Buble Sort Adalah Pada Saat Mengurutkan Data Yang Sangat Besar Akan Mengalami Kelambatan Luar Biasa, Atau Dengan Kata Lain Kinerja Memburuk Cukup Signifikan Ketika Data Yang Diolah Jika Data Cukup Banyak. Kelemahan Lain Adalah Jumlah Pengulangan Akan Tetap Sama Jumlahnya Walaupun Data Sesungguhnya Sudah Cukup Terurut. Hal Ini Disebabkan Setiap Data Dibandingkan Dengan Setiap Data Yang Lain Untuk Menentukan Posisinya.

Insertion Sort :

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

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

Selection Sort:

1. Kelebihan

1)      Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

2)      Operasi pertukarannya hanya dilakukan sekali saja.

3)      Waktu pengurutan dapat lebih ditekan.

4)      Mudah menggabungkannya kembali.

5)      Kompleksitas selection sort relatif lebih kecil.

2. Kekurangan

1)      Membutuhkan method tambahan.

2)      Sulit untuk membagi masalah.

Metode - metode Teknik Sort

v  Selection Sort (Ascending)
Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya, kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan
seterusnya.

Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah :
1. Mencari data terkecil dari data pertama sampai data terakhir, kemunian di tukar posisinya dengan data pertama.
2. mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.

3. mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga
4. dan seterusnya sampai semua data turut naik. apabila terdapat n buah data yang akan di urutkan, maka membutukan (n - 1) langkah pengurutan, dimana data terakhir yaitu data ke-n tidak perlu di urutkan karena hanya tinggal satu satunya.

v  Bubble Sort
Konsep Buble Sort
Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

v  Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat

v  Metode Penyisipan Langsung (Straight Insertion Sort) / Insertion sort Ilustrasi

Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila
ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan
pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu.
Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya
dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelahkiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

v  Metode Penggabungan (Merge Sort)
Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari
metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang
sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table
sehingga dalam keadaan urut.

v  Quick Sort
Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.

v  Metode Shell (Shell Sort)
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

v  Radix sort

Ide dasar dari metode Radix sort ini adalah mengkategorikan data-data menjadi sub kumpulan subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix

Penemu Algoritma Merge Sort

Urut gabung atau sering juga disebut dalam istilah Inggrisnya merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

Prinsip utama yang diimplementasikan pada algoritma urut gabung seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris:divide and conquer). Cara kerja algoritma urut gabung adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya