METODE SORTING

Sorting adalah proses pengurutan data yang banyak banyak ditemukan dalam komputer. Hal ini karena data yang sudah di susun atau di urut lebih mudah di cari dengan cepat. terdapat beberapa metode sorting yaitu:

1. Buble Sort
Buble sort merupakan algoritma pengurutan / metode sorting paling sering digunakan dengan metode pengurutan paling sederhana. Pada metode buble sort, pengurutan dilakukan dengan cara membandingkan masing-masing item / data dalam suatu list secara berpasangan, lalu menukar item tersebut jika diperlukan, dan mengulanginya sampai akhir list secara berurutan dengan sempurna, sehingga tidak ada lagi item yang dapat ditukar.



2. Selection Sort
Selection sort melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Langkah dalam selection sort yaitu, pertama dicari data terkecil dari data pertama sampai data terakhir. Setelah itu data terkecil ditukar dengan data pertama. Maka data pertama 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 seterusnya sampai semua elemen dalam keadaan terurutkan.

3. Merge Sort
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 pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian dan menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok. Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya.

4. Quick Sort
Quick Sort sering disebut juga metode partisi (partition exchange sort). Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut, memilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivo data di sebelah kanan agar lebih besar dar ipada 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.

5. InsertionSort
Insertion sort mengecek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkanpada 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 sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

6. Shell Sort
Shell Sort disebut juga dengan metoda pertambahan menurun (diminishing increment). Metoda ini memanfaatkan penukaran sepasang elemen untuk mencapai keadaan urut. Dalam hal ini jarak dua elemen yang dibandingkan dan ditukarkan tertentu. Pada langkah pertama, ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudian elemen kedua dibandingkan dengan elemen lain dengan jarak yang sama. Demikian seterusnya sampai seluruh elemen dibandingkan

Setiap metode sorting memiliki kecepatan sorting yang berbeda-beda. Maka dari itu untuk mengetahui serta membandingkan kecepatan sorting dari masing-masing metode dapat menggunakan IDLE Paytho Versi 2.7. Dalam pengujian ini kami menggunakan spesefikasi komputer sebagai berikut:

Dengan menggunakan spesifikasi komputer yang tertera pada gambar, hasil dari pengujian kecepatan masing-masing metode sorting sebagai berikut:
Pada percobaan metode buble sort hasil yang di peroleh dari sepuluh kali percobaan dengan jumlah datanya 10.000 adalah:











dengan grafik

Dari data diatas dapat disimpulkan bahwa ketika kita menggunakan spesifikasi komputer yang sedemikian kecepatan sorting yang di peroleh untuk mensorting data sebanyak 10.000 dengan metode buble sort adalah antara 27,89 detik sampai 28,61 detik dengan rata-rata kecepatan sortingnya adalah 28,156 detik. Selisih dari runing tercepat dan terlambat menggunakan buble sort tidak mencapai 1 detik, hal ini membuktikan bahwa keadaan komputer cukup konsisten dalam setiap runing. Hasil runing pada metode Buble sort merupakan metode sorting yang paling lambat dibanding dengan metode sorting yang lain.
Pada percobaan metode insertion sort hasil yang di peroleh dari sepuluh kali percobaan dengan jumlah datanya 10.000 adalah:
dengan grafik:
Dari data diatas dapat disimpulkan bahwa ketika kita menggunakan spesifikasi komputer yang sedemikian kecepatan sorting yang di peroleh untuk mensorting data sebanyak 10.000 dengan metode insertion sort adalah antara 13,91 detik sampai 14,18detik dengan rata-rata kecepatan sortingnya adalaha 13,981 detik. Selisih dari runing tercepat dan terlambat menggunakan insertion tidak mencapai 0,5 detik, hal ini membuktikan bahwa keadaan komputer cukup konsisten dalam setiap runing. Hasil runing pada metode insertion sort lebih cepat dibanding menggunakan buble sort. namun lebih lambat bila dibanding dengan menggunakan metode Selection sort, Shell sort, Merge Sort dan Quick Sort.
Pada percobaan metode Merge sort hasil yang di peroleh dari sepuluh kali percobaan dengan jumlah datanya 10.000 adalah:

dengan Grafik:
Dari data diatas dapat disimpulkan bahwa ketika kita menggunakan spesifikasi komputer yang sedemikian kecepatan sorting yang di peroleh untuk mensorting data sebanyak 10.000 dengan menggunakan metode merge sort adalah antara 0,17 detik sampai 0,26 detik dengan rata-rata kecepatan sortingnya adalah 0,184 detik. Selisih dari runing tercepat dan terlambat menggunakan merge sort tidak mencapai 0,1 detik, hal ini membuktikan bahwa keadaan komputer cukup konsisten dalam setiap runing. Hasil runing pada metode merge sort ini jauh lebih cepat dibanding menggunakan metode buble sort, Insertion sort, selection sort dan Shell sort. namun sedikit lebih lambat dari metode Quick sort.
Pada percobaan metode Selection sort hasil yang di peroleh dari sepuluh kali percobaan dengan jumlah datanya 10.000 adalah:
dengan Grafik:


Dari data diatas dapat disimpulkan bahwa ketika kita menggunakan spesifikasi komputer yang sedemikian kecepatan sorting yang di peroleh untuk mensorting data sebanyak 10.000 dengan menggunakan metode Selection sort adalah antara 0,107 detik sampai 0,156 detik dengan rata-rata kecepatan sortingnya adalah 0,1196 detik. Selisih dari runing tercepat dan terlambat menggunakan merge sort tidak mencapai 0,1 detik, hal ini membuktikan bahwa keadaan komputer cukup konsisten dalam setiap runing. Hasil runing pada metode selection sort adalah yang paling cepat dibanding menggunakan metode -metode sorting yang lain.
Pada percobaan metode Selection sort hasil yang di peroleh dari sepuluh kali percobaan dengan jumlah datanya 10.000 adalah:
dengan Grafik:


Dari data diatas dapat disimpulkan bahwa ketika kita menggunakan spesifikasi komputer yang sedemikian kecepatan sorting yang di peroleh untuk mensorting data sebanyak 10.000 dengan menggunakan metode Selection sort adalah antara 12,05 detik sampai 12,55 detik dengan rata-rata kecepatan sortingnya adalah 12,169 detik. Selisih dari runing tercepat dan terlambat menggunakan merge sort tidak mencapai 0,5 detik, hal ini membuktikan bahwa keadaan komputer cukup konsisten dalam setiap runing. Hasil runing pada metode selection sort ini lebih cepat dibanding menggunakan metode buble sort dan Insertion sort namun jauh lebih lambat dari metode Quick sort, Merge Sort dan Shell Sort.
Pada percobaan metode Shell sort hasil yang di peroleh dari sepuluh kali percobaan dengan jumlah datanya 10.000 adalah:

dengan Grafik:
Dari data diatas dapat disimpulkan bahwa ketika kita menggunakan spesifikasi komputer yang sedemikian kecepatan sorting yang di peroleh untuk mensorting data sebanyak 10.000 dengan menggunakan metode Selection sort adalah antara 0,20 detik sampai 0,21 detik dengan rata-rata kecepatan sortingnya adalah 0,205 detik. Selisih dari runing tercepat dan terlambat menggunakan merge sort tidak mencapai 0,01 detik, hal ini membuktikan bahwa keadaan komputer sangat konsisten dalam setiap runing. Hasil runing pada metode selection sort ini jauh lebih lambat dibanding menggunakan metode merge sort dan Quick sort namun lebih cepat dari buble sort, Selection sort dan Insertion sort.
Berdasarkan pengujian yang dilakukan pada beberapa metode sorting ini, maka perbandingan dari setiap metode dapat dilihat pada Grafik berikut:

Dari beberapa metode yang digunakan dalam mensorting data sebanyak 10.000 diperoleh perbandingan sebagai berikut, dimana metode sorting yang paling efektif digunakan adalah metode Quick Sorting dimana kecepatan rata-ratanya adalah 0,1196 detik. kemudian metode yang ledih efektif lagi adalah dengan menggunakan metode Merge Sort dan Shell Sort dengan kecepatan rata-rata 0,184 detik dan 0,205 detik. selain tiga metode tersebut terdapat tiga metode lagi yang kurang efektif untuk digunakan yaitu metode Selection sort, Insertion sort dan Buble Sort dengan kecepatan rata-rata 12,169 detik, 13,981 detik dan 28,156 detik.
Dengan demikin dapat disimpulan bahwa keefektifan dari setiap metode sorting berbeda-beda dimana metode yang paling efektif adalah metode Quick Sort dan metode yang paling tidak efektif adalah Buble Sort. dalam mensorting data ini spesifikasi komputer yang digunakan dan aplikasi compiler yang digunakan juga berpengaruh. Dimana apabila spesifikasi komputer bagus atau baik maka keefektifan dari metode-metode sorting tersebut akan lebih efektif.

Demikian Penjelasan mengenai metode-metode  sorting serta pembuktian keefektifan dari metode tersebut. Semoga Bermanfaat