際際滷

際際滷Share a Scribd company logo

Algoritma Sorting

Download as DOC, PDF
Lubna Abidah
Lubna Abidah

Dokumen tersebut membahas mengenai beberapa metode sorting seperti bubble sort, selection sort, insertion sort, quick sort, dan shell sort. Metode-metode tersebut dijelaskan cara kerja dan contoh kode pseudocode-nya.

1 of 4
Downloaded 21 times
Metode Sorting dan Aplikasinya Tugas Kuliah Algoritma dan Struktur Data Lubna Abidah Manajemen Informatika Politeknik Negeri Lampung Bandar Lampung, Lampung Lubna16abidah@gmail.com AbstrakMakalah ini menjelaskan mengenai metode sorting dan aplikasinya. Sorting merupakan suatu metode pengurutan algoritma penyusunan data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu. [1] Dalam sorting dikenal beberapa metode seperti metode bubble sort, selection sort, insertion sort, quick sort, dan shell sort. Kata kunci Sorting, Ascending, Descending, Data acak, Metode sorting. I. PENDAHULUAN Sorting atau pengurutan data merupakan suatu proses penyusunan data acak menggunakkan aturan tertentu sehingga didapatkan data yang tersusun sesuai aturan tersebut. Ada dua macam urutan yang biasa digunakkan dalam proses pengurutan yaitu: (1) Urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar. (2) Urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai yang kecil.[2] Contohnya bilangan 4,8,2,1,10,9 diurutkan secara ascending menjadi 1,2,4,8,9,10 dan dapat diurutkan secara descending menjadi 10,9,8,4,2,1. Dalam sorting dikenal beberapa jenis metode yaitu : (1) Pengurutan berdasarkan perbandingan (comparsion-based sorting) seperti bubble sort dan excange sort. (2) Pengurutan berdasarkan prioritas (priority quene sorting method) seperti selection sort dan heap sort. (3) Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method) seperti insertion sort dan tree sort. (4) Pengurutan berdasarkan pembagian dan penguasaan (devide and couner method) seperti quick sort dan merge sort. (5) Pengurutan berkurang menurun (diminshing increment sort method) seperti shell sort dan pengembangan insertion.[1] Keuntuntungan mengurutkan atau sorting data yaitu data yang terurut mudah dicari, mudah diperiksa, dan mudah untuk direfisi jika terjadi kesalahan. Data yang terurut dengan baik juga mudah dihapus sewaktu-waktu jika data tersebut sudah tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka akan semakin mudah untuk menyisipkan atau menggabungkan data.mengurutkan data.[4] II. BUBBLE SORT Metode bubble sort merupakan metode pengurutan dengan cara membandingkan sebuah data dengan data lainnya kemudian ditukar. Metode ini diberi nama Bubble karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar pada gelas bersoda.[1] Cara kerjanya adalah dengan berulang-ulang melakukan traversal(proses looping) terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam traversal tersebut, nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan pesanan maka akan dilakukan pertukaran (swap). [4] Metode jenis ini merupakan metode termudah namun dirasa kurang efisien dengan metode jenis lain. Berikut ini adalah contoh proses pengurutan dengan metode bubble sort: [1]
Berikut ini contoh pseudocode algoritma metode bubble sort: [2] void BubbleSort() { int i, j; for(i=1; i<Max-1; i++) for(j=Max-1; j>=i; j--) if(Data[j-1] > Data[j]) Tukar(&Data[j-1], &Data[j]); } III. SELECTION SORT Selection sort merupakan metode kombinasi antara sorting dan searcing.[1] Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian index elemen struktur data. [4] Setiap proses akan dicari elemen-elemen yang belum terurut diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat dalam array.[1] Contoh algoritma selection sort: (1) Temukan nilai yang paling minimum di dalam sebuah data. Jika ascending pilih yang minimum jika descending maka sebaliknya. (2) Tukar nilai pada posisi pertama di bagian struktur data sebelum diurutkan.(3) Ulangi langkah diatas untuk bagian struktur data tersisa. [4] Berikut ini adalah contoh proses pengurutan dengan metode selection sort: [4] Berikut ini contoh pseudocode algoritma metode bubble sort: [1] void selection_sort(){ for(int i=0;i<n-1;i++){ pos = i; for(int j=i+1;j<n;j++){ if(data[j] < data[pos]) pos = j; //ascending } if(pos != i) tukar(&data[pos],&data[i]); } } IV. INSERTION SORT Insertion sort merupakan metode pertengahan. Artinya metode ini memiliki kecepatan rata-rata antara metode primitif (bubble dan selection) dan modern (merge dan quick). [5] Metode ini mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan ini dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) di posisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.[1] Algoritma insertion sort dapat dirangkum sebagai berikut: (1) Simpan nilai Ti ke dalam variabel sementara dengan i =1. (2) Bandingkan nilainya dengan elemen sebelumnya. (3) Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih Ti dengan Ti-1 tersebut. Kurangi nilainya dengan 1. (4) Lakukan terus poin ketiga sampai Ti-1<= Ti. (5) Jika Ti- 1 <= Ti terpenuhi, tindih nilai Ti dengan variabel sementara yang disimpan sebelumnya (6) Ulangi langkah dari poin 1 di atas dengan di tambah 1.[4] Berikut ini adalah contoh proses pengurutan dengan metode insertion sort: [5]
Berikut ini contoh pseudocode algoritma metode insertion sort: [1] void insertion_sort(){ int temp; for(int i=1;i<n;i++){ temp = data[i]; j = i -1; while(data[j]>temp && j>=0){ data[j+1] = data[j]; j--; } data[j+1] = temp; } } V. QUICK SORT Metode quick sort sering disebut dengan metode partisi (partition excange sort). [4] Metode ini dirancang oleh C.A.R Hoarae pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer sains Elliot Brothers. Untuk mempertinggi efektifitas metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar. [2] Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.: mula- mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x. [2] Berikut ini adalah contoh proses pengurutan dengan metode quick sort:[2] VI. SHELL SORT Shell sort disebut juga pertambahan menurun. [1] Metode shell sort dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu.[4] Mengurutkan datanya dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.[1] 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. [4] Contoh dari proses Sorting dengan menggunakan metode Shell Sort : [4] Berikut ini contoh pseudocode algoritma metode shell sort: [1] . DAFTAR PUSTAKA [1] Rachmat C, Antonius.Struktur Data. http://lecturer.ukdw.ac.id/anton/download/strukdat3.pdf . (diakses 01 Juni 2015). [2] Anonim. Bab VI Pengurutan (Sorting). http://entin.lecturer.pens.ac.id/Struktur%20Data%20& %20Algoritma/buku/Data%20Structure%20-%20Bab%206.pdf. (diakses tanggal 01 Juni 2015). [3] Nurhayati, Oky Dwi. Algoritma dan Pemrograman Sorting dan Searching.http://core.ac.uk/download/pdf/11719025.pdf. (diakses tanggal 01 Juni 2015). [4] Syaviri, Ananda putri. Laporan Praktikum Sorting (Pengurutan). https://www.academia.edu/6136390/laporan_sorting_script_di_ dalamnya_juga_searching_kok_ . (diakses tanggal 01 Juni 2015). [5] Arief hendra Saptadi, Desi Windi Sari. Analisis Algoritma Insert Sort Merge Sort dan Implementasinya. https://www.academia.edu/4618083/Jurnal_Infotel_2_Akatel_S P (diakses tanggal 01 Juni 2015)
Algoritma Sorting

More Related Content

Algoritma Sorting

  • 1. Metode Sorting dan Aplikasinya Tugas Kuliah Algoritma dan Struktur Data Lubna Abidah Manajemen Informatika Politeknik Negeri Lampung Bandar Lampung, Lampung Lubna16abidah@gmail.com AbstrakMakalah ini menjelaskan mengenai metode sorting dan aplikasinya. Sorting merupakan suatu metode pengurutan algoritma penyusunan data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu. [1] Dalam sorting dikenal beberapa metode seperti metode bubble sort, selection sort, insertion sort, quick sort, dan shell sort. Kata kunci Sorting, Ascending, Descending, Data acak, Metode sorting. I. PENDAHULUAN Sorting atau pengurutan data merupakan suatu proses penyusunan data acak menggunakkan aturan tertentu sehingga didapatkan data yang tersusun sesuai aturan tersebut. Ada dua macam urutan yang biasa digunakkan dalam proses pengurutan yaitu: (1) Urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar. (2) Urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai yang kecil.[2] Contohnya bilangan 4,8,2,1,10,9 diurutkan secara ascending menjadi 1,2,4,8,9,10 dan dapat diurutkan secara descending menjadi 10,9,8,4,2,1. Dalam sorting dikenal beberapa jenis metode yaitu : (1) Pengurutan berdasarkan perbandingan (comparsion-based sorting) seperti bubble sort dan excange sort. (2) Pengurutan berdasarkan prioritas (priority quene sorting method) seperti selection sort dan heap sort. (3) Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method) seperti insertion sort dan tree sort. (4) Pengurutan berdasarkan pembagian dan penguasaan (devide and couner method) seperti quick sort dan merge sort. (5) Pengurutan berkurang menurun (diminshing increment sort method) seperti shell sort dan pengembangan insertion.[1] Keuntuntungan mengurutkan atau sorting data yaitu data yang terurut mudah dicari, mudah diperiksa, dan mudah untuk direfisi jika terjadi kesalahan. Data yang terurut dengan baik juga mudah dihapus sewaktu-waktu jika data tersebut sudah tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka akan semakin mudah untuk menyisipkan atau menggabungkan data.mengurutkan data.[4] II. BUBBLE SORT Metode bubble sort merupakan metode pengurutan dengan cara membandingkan sebuah data dengan data lainnya kemudian ditukar. Metode ini diberi nama Bubble karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar pada gelas bersoda.[1] Cara kerjanya adalah dengan berulang-ulang melakukan traversal(proses looping) terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam traversal tersebut, nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan pesanan maka akan dilakukan pertukaran (swap). [4] Metode jenis ini merupakan metode termudah namun dirasa kurang efisien dengan metode jenis lain. Berikut ini adalah contoh proses pengurutan dengan metode bubble sort: [1]
  • 2. Berikut ini contoh pseudocode algoritma metode bubble sort: [2] void BubbleSort() { int i, j; for(i=1; i<Max-1; i++) for(j=Max-1; j>=i; j--) if(Data[j-1] > Data[j]) Tukar(&Data[j-1], &Data[j]); } III. SELECTION SORT Selection sort merupakan metode kombinasi antara sorting dan searcing.[1] Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian index elemen struktur data. [4] Setiap proses akan dicari elemen-elemen yang belum terurut diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat dalam array.[1] Contoh algoritma selection sort: (1) Temukan nilai yang paling minimum di dalam sebuah data. Jika ascending pilih yang minimum jika descending maka sebaliknya. (2) Tukar nilai pada posisi pertama di bagian struktur data sebelum diurutkan.(3) Ulangi langkah diatas untuk bagian struktur data tersisa. [4] Berikut ini adalah contoh proses pengurutan dengan metode selection sort: [4] Berikut ini contoh pseudocode algoritma metode bubble sort: [1] void selection_sort(){ for(int i=0;i<n-1;i++){ pos = i; for(int j=i+1;j<n;j++){ if(data[j] < data[pos]) pos = j; //ascending } if(pos != i) tukar(&data[pos],&data[i]); } } IV. INSERTION SORT Insertion sort merupakan metode pertengahan. Artinya metode ini memiliki kecepatan rata-rata antara metode primitif (bubble dan selection) dan modern (merge dan quick). [5] Metode ini mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan ini dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) di posisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.[1] Algoritma insertion sort dapat dirangkum sebagai berikut: (1) Simpan nilai Ti ke dalam variabel sementara dengan i =1. (2) Bandingkan nilainya dengan elemen sebelumnya. (3) Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih Ti dengan Ti-1 tersebut. Kurangi nilainya dengan 1. (4) Lakukan terus poin ketiga sampai Ti-1<= Ti. (5) Jika Ti- 1 <= Ti terpenuhi, tindih nilai Ti dengan variabel sementara yang disimpan sebelumnya (6) Ulangi langkah dari poin 1 di atas dengan di tambah 1.[4] Berikut ini adalah contoh proses pengurutan dengan metode insertion sort: [5]
  • 3. Berikut ini contoh pseudocode algoritma metode insertion sort: [1] void insertion_sort(){ int temp; for(int i=1;i<n;i++){ temp = data[i]; j = i -1; while(data[j]>temp && j>=0){ data[j+1] = data[j]; j--; } data[j+1] = temp; } } V. QUICK SORT Metode quick sort sering disebut dengan metode partisi (partition excange sort). [4] Metode ini dirancang oleh C.A.R Hoarae pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer sains Elliot Brothers. Untuk mempertinggi efektifitas metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar. [2] Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.: mula- mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x. [2] Berikut ini adalah contoh proses pengurutan dengan metode quick sort:[2] VI. SHELL SORT Shell sort disebut juga pertambahan menurun. [1] Metode shell sort dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu.[4] Mengurutkan datanya dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.[1] 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. [4] Contoh dari proses Sorting dengan menggunakan metode Shell Sort : [4] Berikut ini contoh pseudocode algoritma metode shell sort: [1] . DAFTAR PUSTAKA [1] Rachmat C, Antonius.Struktur Data. http://lecturer.ukdw.ac.id/anton/download/strukdat3.pdf . (diakses 01 Juni 2015). [2] Anonim. Bab VI Pengurutan (Sorting). http://entin.lecturer.pens.ac.id/Struktur%20Data%20& %20Algoritma/buku/Data%20Structure%20-%20Bab%206.pdf. (diakses tanggal 01 Juni 2015). [3] Nurhayati, Oky Dwi. Algoritma dan Pemrograman Sorting dan Searching.http://core.ac.uk/download/pdf/11719025.pdf. (diakses tanggal 01 Juni 2015). [4] Syaviri, Ananda putri. Laporan Praktikum Sorting (Pengurutan). https://www.academia.edu/6136390/laporan_sorting_script_di_ dalamnya_juga_searching_kok_ . (diakses tanggal 01 Juni 2015). [5] Arief hendra Saptadi, Desi Windi Sari. Analisis Algoritma Insert Sort Merge Sort dan Implementasinya. https://www.academia.edu/4618083/Jurnal_Infotel_2_Akatel_S P (diakses tanggal 01 Juni 2015)