Tipe-Tipe Sorting

Nama   : Nazrah EFrilia Putri

NPM   : 1415061033

Prodi   : Teknik Informatika

 

 

SORTING

 

Pengertian

 

Sorting merupakan suatu proses mengatur kumpulan objek menurut susunan atau urutan tertentu. Urutan dapat berupa ascending (Meningkat) mulai dari terkecil hingga yang terbesar atau descending (menurun) mulai dari yang terbesar hingga yang terkecil. Sorting dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urutan menaik (ascending) dari nilai terkecil sampai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting merupakan proses pengurutan. Dilihat dari tempat penyimpanan data, sort dibedakan antara external sort dan internal sort. External sort bila datanya berada dalam media external, atau external storage, seperti harddisk. Internal sort bila datanya ada dalam internal storage atau memori komputer.

Beberapa macam dari metode sorting:

 

 

1.Bubble Sort

Bubble Sort (metode gelembung) merupakan salah satu metode sorting atau mengurutkan dari data terkecil ke data terbesar ataupun dengan cara membandingkan elemen kesatu dengan elemen yang selanjutnya. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergera/berpindah ke posisi yang tepat , seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. jika elemen sekarang  lebih besar dari elemen berikutnya maka elemen tersebut ditukar (untuk pengurutan ascending) jika elemen sekarang lebih kecil daripada elemen berikutnya, maka kedua elemen  tersebut ditukar (untuk pengurutan descending). algoritma ini seolanh olah menggeser satu per satu elemen dari kenan ke kiri atau kiri ke kanan. tergantung jenis pengurutannya. Ketika suatu proses telah selesai, maka bubble sort akan mengalami proses, demikian seterusnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan,serta tercapai pengurutan yang telah diinginkan

 

Prinsip kerja dari bubble sort adalah:

  1. Pengecekan mulai dari data ke satu sampai data ke-n.
  2. Bandingkan data ke-1 sampai data ke-n dengan data setelahnya.
  3. Jika lebih besar maka tidak terjadi pemindahan atau swap.
  4. Jika data sebelumnya kecil bila dibandingkan dengan data setelahnya besar maka tidak akan terjadi pemindahan atau no swap.
  5. Ulang langkah diatas sampai data bisa tersusun baik secara ascending maupun descending. Sampai data terurutkan.

 

Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada di permukaan 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.

 

 

  1. Insertion Sort

Insertion Sort(Metode Penyisipan) merupakan sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pisisinya dengan cara melakukan perbandingan dengan data – data yang ada. Indeks algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu, dimana jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut. Dalam pengurutan data, metode ini dipakai bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array diurutkan.

 

Penganalogian Insertion Sort dengan pengurutan kartu. Berikut menjelaskan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu, Anggaplah kita ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.

  1. Dimulai dengan posisi tangan kosong, dan semua kartu berada diatas meja. Dan anggaplah kita akan menyusun kartu ke tangan kiri kita.
  2. Mengamil kartu pertama dari meja dan meletakannya ke tangan kiri.
  3. Mengambil kartu kedua dan membandingkannya dengan kartu yang sudah ada di tangan kiri.
  4. Jika kartu yang diambil dari meja memenuhi syarat perbandingan, maka kartu tersebut akan diletakan didepan kartu yang dibandingkan, serta kartu yang lain yang telah dibandingkan akan bergeser mundur (ke belakang). Proses ini akan berlangsung sampai semua kartu akan terurutkan dengan benar sesuai criteria pengurutannya.

 

 

  1. Quick Sort

Quick Sort merupakan mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.

 

Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

  1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.
  2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.
  3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.

 

 

  1. Merge Sort

Merge sort merupakan metode algoritma yang berdasarkan strategi divide-and-conquer. Algoritma ini tediri dari dua bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut.

  1. Divide : membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
  2. Conquer : memecahkan (menyelesaikan) masing-masing submasalah (secara rekursif), dan
  3. Combine : mengabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.

 

  1. Shell SortShell Sort merupakan metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment short). Shell Sort bekerja dengan cara mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran apabila diperlukan.
  2. Selection Sort

Selection Sort merupakan metode sorting dimana elemen di perbandingkan satu-persatu sampai pada elemen terakhir dan disusun berdasarkan ketentuan-ketentuan berlaku (terbesar atau terkecil). Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya.

Prinsip kerja selection short:

  1. Pengecekan dimulai data ke-1 sampai dengan ke-n.
  2. Tentukan bilangan dengan indeks terkecil dari bilangan tersebut.
  3. Tukar bilangan dengan indeks terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut.
  4. Lakukan langkah 2 dan 3 untuk bilangan berikutnya (I=I+1) sampai didapatkan urutan yang optimal.

 

Pada Tugas Sorting Mata kuliah Struktur Data ini saya menggunakan bahasa pemrograman Python V 2.7 dengan perangkat yang di gunakan yaitu Asus tipe A455L dengan spesifikasi

buaya

Metode Iterasi pertama Iterasi ke 2 Iterasi ke 3 Iterasi ke 4 Iterasi ke 5 Iterasi ke 6 Iterasi ke 7 Iterasi ke 8 Iterasi ke 9 Iterasi ke 10
Bubble Sort 30.99 31.03 31.04 31.03 31.03 31.04 31.04 31.03 31.02 31.03
Insertion Sort 16.93 16.94 16.94 16.93 16.93 16.92 16.93 16.93 16.93 16.93
Quick Sort 0.06 0.07 0.07 0.06 0.07 0.07 0.06 0.07 0.07 0.07
Merge Sort 0.19 0.18 0.18 0.17 0.18 0.19 0.17 0.18 0.19 0.19
Shell Sort 0.31 0.30 0.31 0.30 0.30 0.31 0.31 0.31 0.30 0.31
Selection Sort 11.15 11.16 11.15 11.15 11.15 11.15 11.14 11.15 11.15 11.15

Grafik Perbandingan

nazrah

Dari hasil percobaan tersebut dapat disimpulkan bahwa metode yang tercepat dalam melakukan sorting ialah quick sort, dengan waktu rata-rata untuk mensorting 10.000 data random ialah 0.06 detik. Metode yang paling lambat ialah Bubble Sort, dengan waktu rata-rata untuk mensorting 10.000 data ialah 31.04 detik.

Algoritma dan Pemrograman

Source code program menghitung gaji pegawai menggunakan C++

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int jam_lembur;
long int gaji_kotor,total_gaji_lembur;
int gaji_pokok;
long int gol;
float pajak,gaji_bersih,asuransi;
char nama[30];
system(“cls”);
printf(“Nama Pegawai : “);fflush(stdin);gets(nama);
printf(“Golongan     : “);scanf(“%i”,&gol);
if(gol==1)
{
gaji_pokok=900000;
}
else if (gol==2)
{
gaji_pokok=1100000;
}
else if (gol==3)
{
gaji_pokok=2000000;
}
else
{
gaji_pokok=0;
}
printf(“Lama Lembur  : “);scanf(“%i”,&jam_lembur);total_gaji_lembur=(long int)45000*jam_lembur;

//Output Data
gaji_kotor=gaji_pokok+total_gaji_lembur;
pajak=0.025*gaji_kotor;
asuransi=0.05*gaji_kotor;
gaji_bersih=gaji_kotor-pajak-asuransi;
system(“cls”);
printf(“DAFTAR PERHITUNGAN GAJI PEGAWAI\n”);
printf(“============================================================\n\n”);
printf(“Nama Pegawai        : %s\n”,nama);
printf(“Golongan            : %i\n\n”,gol);
printf(“Gaji Pokok          : Rp.%1li\n”,gaji_pokok);
printf(“Lama Lembur         : %i jam\n”,jam_lembur);
printf(“Total Gaji Lembur   : Rp.%1li\n”,total_gaji_lembur);
printf(“Gaji Kotor          : Rp.%1li\n\n”,gaji_kotor);
printf(“POTONGAN\n”);
printf(“Pajak [2.5%%]        : Rp.%1.0f\n”,pajak);
printf(“Asuransi [5%%]       : Rp.%1.0f\n”,asuransi);
printf(“Gaji Bersih         : Rp.%1.0f\n\n”,gaji_bersih);
system(“PAUSE”);
return 0;
}

Hasil compile program diatas adalah

gaji

SILAHKAN DICOBA :)