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

TUGAS SORTING

1. Buatlah 1 contoh program insertion sort.
2. Tuliskan pengertian sorting menurut pendapat anda masing – masing.
3. Buatlah contoh prgram buble sort dalam bahasa pascal
4. Tuliskan algoritma quick recursif.
5. Sebutkan dan jelaskan metode – metode sorting.

Contoh program insertion sort

#include <stdio.h>

int main()

{

  int n, array[1000], c, d, t;

  printf("Enter number of elements\n");

  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++) {

    scanf("%d", &array[c]);

  }

for (c = 1 ; c <= n - 1; c++) {

    d = c;

    while ( d > 0 && array[d] < array[d-1]) {

      t          = array[d];

      array[d]   = array[d-1];

      array[d-1] = t;

      d--;

    }

  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

  return 0;

}

PENGERTIAN SORTING

 sorting  adalah sebuah metode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan.
Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.

Contoh Prgram Buble Sort Dalam Bahasa Pascal

program bubble_sort_polma;

uses crt;

var

 i,n,j : integer;

 a : array [1..10] of integer;

procedure urutkan;

 var

  z : integer;

  begin

   for i:=1 to n-1 do

    begin

         for j:=n downto i+1 do

          begin

           if a[j] > a[j-1] then

            begin

z:=a[j];

                 a[j]:=a[j-1];

                 a[j-1]:=z;

                end;

          end;

    end;

  end;

begin

 clrscr;

 writeln('Program : Mengurutkan Nilai menggunakan Bubble Sort');

  writeln;

 write ('Masukkan banyak data yang ingin di urut : '); readln(n);

 for i:=1 to n do

  begin

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

  end;

 urutkan;

 write('Data setelah diurutkan : ');

 for j:=1 to n do

  write (a[j],' ');

readln;

end.

Algoritma Quick Recursif

Algoritma quick Rekursif dapat dituliskan sebagai berikut :

Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT. Berikut pseudocode dari algoritma quick sort :

Procedure quick_sort (I/O A : TabelInt, input i,j : integer )

{ Mengurutkan table A [i..j] dengan algoritma Quick Sort, dengan pemilihan pivot menggunakan elemen median table.

    Masukan : Tabel [i..j] yang sudah terdefinisi elemen-elemennya.

    Keluaran : Tabel [i..j] yang terurut secara asc }

Kamus

     p,q,temp, pivot : integer

Algoritma

   p         i

   q          j

   pivot       A[(p+q) div 2]

repeat

while A[p] < pivot do

           p         p + 1

endwhile

while A[q] > pivot do

          q         q - 1

endwhile

if p £ q then

temp         A[p]

              A[p]          A[q]

              A[q]          temp

              p         p +1

              q         q - 1

endif

until p > q    

if i < q then

quick_sort (A, i, q)

endif

if j > p then

quick_sort (A, p, j)

endif

Algoritma diatas termasuk dalam algoritma mempartisi dan algoritma mengurutkan dimana algoritma partisi untuk dapat menuju keadaan terurut tidaklah sukar lagi, setelah membagi tabel maka diterpkan lagi procedure yang sama pada keadaan bagian, procedure diatas mengktifkan dirinya sendiri secara rekursif.

Metode – metode Sorting

BUBBLE SORT

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

algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.

Proses dalam Bubble sort dilakukan sebanyak N-1 langkah (pass) dengan N adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh array L[0..N-1] yang terurut menaik.

Untuk mendapatkan urutan yang menaik, algoritmanya dapat ditulis secara global sebagai berikut :

Untuk setiap pass ke – I = 0,1,………., N-2 , lakukan :

Mulai dari elemen J = N-1, N-2,….., I + 1, lakukan :

Bandingkan L[J-1] dengan L[J]

Pertukarkan L[J-1] dengan L[J] jika L[J-1] > L[J]

Rincian setiap pass adalah sebagai berikut :

Pass 1:      I = 0. Mulai dari elemen J = N-1,N–2,…,1, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 1, elemen L[0] berisi harga minimum pertama.

Pass 2:      I = 1. Mulai dari elemen J = N-1,N–2,…,2, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 2, elemen L[1] berisi harga minimum kedua dan array L[0..1] terurut, sedangkan L[2..(N-1)] belum terurut.

Pass 3:      I = 2. Mulai dari elemen J = N-1,N–2,…,3, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 3, elemen L[2] berisi harga minimum ketiga dan array L[0..2] terurut, sedangkan L[3..(N-1)] belum terurut.

Pass N-1:  Mulai dari elemen J = N-1, bandingkan L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan L[J].

Pada akhir langkah N-2, elemen L[N-2] berisi nilai minimun ke [N-2] dan array L[0..N-2] terurut menaik (elemen yang tersisa adalah L[N-1], tidak perlu diurut karena hanya satu-satunya).

Misal array L dengan N = 5 buah elemen yang belum terurut. Array akan diurutkan secara ascending (menaik).

0      1     2     3      4

Pass 1 :

I = 0 ;J= N-1= 4                      8          9          7          1          6

J = 3                            8          9          1          7          6

J = 2                            8          1          9          7          6

J = 1                            1          8          9          7          6

Hasil akhir langkah 1 :

0      1       2      3      4

 

Pass 2 :

I = 1 ;J= N-1= 4                      1          8          9          6          7

J = 3                            1          8          6          9          7

J = 2                            1          6          8          9          7

Hasil akhir langkah 2 :

0       1      2      3      4

Pass 3 :

I = 2 ;J= N-1= 4                      1          6          8          7          9

J = 3                            1          6          7          8          9

Hasil akhir langkah 3 :

Metode Selection Sort
Selection Sort berbeda dengan Bubble sort. Selection Sort pada dasarnya memilih data yang akan diurutkan menjadi dua bagian, yaitu bagaian yang sudah diurutkan dan bagian yang belum di urutkan.
Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. Metode ini lebih efektif dari pada metode bubble karena tidak memerlukan banyak pertukaran dan pengalokasian memori.