1. Output adalah dalam rangka nondecreasing (setiap elemen tidak lebih kecil dari elemen sebelumnya sesuai dengan total order yang diinginkan);2.
2. Output adalah permutasi, atau penataan ulang, dari input.
Sejak awal komputasi, masalah pengurutan telah menarik banyak penelitian, mungkin karena kompleksitas penyelesaian secara efisien meskipun sederhana pernyataannya, akrab. Sebagai contoh, bubble sort dianalisis sejak 1956 [1] Walaupun banyak yang menganggapnya masalah dipecahkan, berguna algoritma pengurutan baru masih ditemukan (misalnya, seperti perpustakaan pertama kali diterbitkan pada tahun 2004).. Sorting algoritma yang lazim di kelas pengantar ilmu komputer, di mana kelimpahan algoritma untuk masalah memberikan pengenalan lembut ke berbagai konsep algoritma inti, seperti membagi besar O, notasi dan menaklukkan algoritma, struktur data, algoritma acak, terbaik, terburuk dan analisis kasus rata-rata, pengorbanan waktu-ruang, dan batas bawah.
Klarifikasi
Sorting algoritma yang digunakan dalam ilmu komputer sering dikelompokkan berdasar:
Kompleksitas Komputasi (perilaku terburuk, rata-rata dan terbaik) dari perbandingan unsur dalam hal ukuran daftar (n). Untuk algoritma pengurutan khas perilaku yang baik adalah O (n log n) dan perilaku buruk adalah O (n2) Ideal untuk semacam perilaku adalah O (n),namun hal ini tidak mungkin dalam kasus rata-rata. Perbandingan algoritma pengurutan berbasis, yang mengevaluasi elemen daftar melalui operasi perbandingan abstrak kunci, memerlukan setidaknya O (n log n) perbandingan untuk input yang paling.
Komputasi kompleksitas swap (untuk "di tempat" algoritma).
Memory penggunaan (dan penggunaan sumber daya komputer lain). Secara khusus, beberapa algoritma pengurutan adalah "di tempat". Ini berarti bahwa mereka hanya perlu O(1) atau O (log n) memori luar item yang disortir dan mereka tidak perlu membuat lokasi tambahan untuk data yang akan disimpan sementara, seperti di lain algoritma pengurutan.
Rekursi. Beberapa algoritma yang baik rekursif atau non-rekursif, sementara yang lain mungkin baik (misalnya, menggabungkan sort).
Stabilitas: algoritma pengurutan stabil menjaga urutan relatif dari record dengan kunci yang sama (yaitu, nilai-nilai). Lihat di bawah untuk informasi lebih lanjut.
Apakah atau tidak mereka adalah semacam perbandingan. Semacam perbandingan memeriksa data hanya dengan membandingkan dua elemen dengan operator perbandingan.
Metode Umum: penyisipan, pertukaran, seleksi, penggabungan, dll. jenis Efek termasuk bubble sort dan quickSort. Seleksi macam termasuk semacam shaker dan heapsort.
Adaptasi: Apakah atau tidak presortedness input mempengaruhi waktu berjalan. Algoritma yang mempertimbangkan hal ini diketahui adaptif.
Stabilitas
algoritma pengurutan Stabil menjaga urutan relatif dari record dengan kunci yang sama. Jika semua tombol berbeda maka perbedaan ini tidak diperlukan. Tetapi jika ada kunci sama, maka algoritma sorting stabil jika setiap kali ada dua catatan (katakanlah R dan S) dengan tombol yang sama, dan R muncul sebelum S dalam daftar yang asli, maka R akan selalu muncul sebelum S di daftar diurutkan. Apabila terdapat unsur yang sama tidak dapat dibedakan, seperti dengan bilangan bulat, atau lebih umum, data dimana seluruh elemen kunci, stabilitas tidak menjadi masalah. Namun, menganggap bahwa pasangan berikut nomor harus diurutkan berdasarkan komponen pertama mereka:
(4, 2) (3, 7) (3, 1) (5, 6)
Dalam hal ini, dua hasil yang berbeda yang mungkin, salah satu yang menjaga urutan relatif dari record dengan kunci yang sama, dan satu yang tidak:
(3, 7) (3, 1) (4, 2) (5, 6) (Urutan dipertahankan)
(3, 1) (3, 7) (4, 2) (5, 6) (Urutan diubah)
algoritma sorting yang tidak stabil dapat mengubah urutan relatif dari record dengan kunci yang sama, tetapi algoritma pengurutan stabil tidak pernah melakukannya. algoritma pengurutan tidak stabil dapat diterapkan khusus menjadi stabil. Salah satu cara untuk melakukan ini adalah artifisial memperpanjang perbandingan kunci, sehingga perbandingan antara dua objek dengan tombol dinyatakan sama akan memutuskan menggunakan urutan entri dalam urutan data aslinya sebagai pemecah-dasi. Mengingat urutan ini, bagaimanapun, sering melibatkan biaya komputasi tambahan.
Sorting berdasarkan tersier, primer sekunder, dll kunci semacam dapat dilakukan oleh setiap metode pengurutan, mengambil semua kunci semacam ke account dalam perbandingan (dengan kata lain, menggunakan kunci semacam tunggal komposit). Jika metode pengurutan stabil, juga memungkinkan untuk menyortir beberapa kali, setiap kali dengan satu tombol sort. Dalam hal bahwa kunci perlu diterapkan dalam urutan prioritas meningkat.
Contoh: sorting pasangan nomor seperti di atas dengan terlebih dahulu, maka kedua komponen:
(4, 2) (3, 7) (3, 1) (5, 6) (asli)
(3, 1) (4, 2) (5, 6) (3, 7) (setelah menyortir menurut komponen kedua)
(3, 1) (3, 7) (4, 2) (5, 6) (setelah menyortir menurut komponen pertama)
Di sisi lain:
(3, 7) (3, 1) (4, 2) (5, 6) (setelah menyortir menurut komponen pertama)
(3, 1) (4, 2) (5, 6) (3, 7) (setelah menyortir menurut Komponen kedua,
urutan oleh komponen pertama adalah terganggu).
Macam-macam sort
1. Bubble Sort
Metode bubble sort merupakan metode tersederhana untuk melakukan pengurutan data , tetapi memiliki kinerja yang terburuk untuk data yang besar. Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.Penukaran baru dilakukan kalau suatu kriteria terpenuhi.
Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya, asc atau desc.Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Bubble Sort adalah salah satu metode pengurutan (sorting) dengan cara membandingkan angka dalam satu waktu yang ada pada list, kemudian memperbaiki urutan angka – angka tersebut jika tidak mengikuti urutan yang ditentukan.
contoh:
input (input.txt)
5 6 8 4 8 9
1 3 6 4 8 4
1 0 6 9 5 8
input memiliki 6 kolom k dan 3 baris j
1. Baca file input.txt dan store setiap value kedalam baris dan kolom yang sesuai, misal variable: angka[j][k]
2. Gunakan for loop 2-d array untuk membaca susunan angka
01 for(int j=0;j<3;j++){//baris
02 for(int k=0;k<6;k++){//kolom
03 //bubble sorting : angka akan diswap bila angka berikutnya lebih besar dari angka sebelum
04 if(angka[j][k] < angka[j][k+1]){
05 int temp = angka[j][k];
06 angka[j][k] = angka[j][k+1];
07 angka[j][k+1] = temp;
08 }
09 cout<
10 }
11 cout<
12 }
sekarang variable angka telah diurutkan. bisa langsung tulis ke dalam file output.txt
output (output.txt):
9 8 8 6 5 4
8 6 4 4 3 1
9 8 6 5 1 0
ilustrasi pengurutan dengan bubble sortnya akan terlihat seperti pada table dibawah ini :
LANGKAH 1 :
1 2 3 4 5 6 POSISI DATA
22 10 15 3 8 2 Data Awal
22 10 15 3 2 8 tukar data 5 dengan 6
22 10 15 2 3 8 tukar data 4 dengan 3
22 10 2 15 3 8 tukar data 3 dengan 2
22 2 10 15 3 8 tukar data 2 dengan 1
2 22 10 15 3 8 LANGKAH 1 SELESAI
LANGKAH 2 :
1 2 3 4 5 6 POSISI DATA
2 22 10 15 3 8 Data Langkah 1 Akhir
2 22 10 3 15 8 tukar data 4 dengan 3
2 22 3 10 15 8 tukar data 3 dengan 2
2 3 22 10 15 8 LANGKAH 2 SELESAI
LANGKAH 3 :
1 2 3 4 5 6 POSISI DATA
2 3 22 10 15 8 Data Langkah 2 Akhir
2 3 22 10 8 15 tukar data 5 dengan 6
2 3 22 8 10 15 tukar data 4 dengan 3
2 3 8 22 10 15 LANGKAH 3 SELESAI
LANGKAH 4 :
1 2 3 4 5 6 POSISI DATA
2 3 8 22 10 15 Data Langkah 3 Akhir
2 3 8 22 10 15 tukar data 5 dengan 4
2 3 8 10 22 15 LANGKAH 4 SELESAI
LANGKAH 5 :
1 2 3 4 5 6 POSISI DATA
2 3 8 10 22 15 Tukar data 5 dengan 6
2 3 8 10 15 22 TERURUT
2.Exchange Sort
Metode Exchange Sort merupakan metode pengurutan data yang sangat mirip dengan Bubble Sort bahkan banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Namun perbedaan antara Exchange Sort dan bubble sort terletak dalam hal bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
ilustrasi pengurutan dengan Exchange sortnya akan terlihat seperti pada table dibawah ini :
• Prosedur Exchange Sort
3.Selection Sort
Metode selection sort merupakan metode pengurutan data kombinasi antara sorting dan searching. Mekanismenya seperti berikut ini : Mula – mula suatu petunjuk (diberi nama posAwal ) yang menunjuk lokasi awal pengurutan data diatur agar berisi indeks pertama dalam larik. Selanjutnya dicari bilangan terkecil yang terletak antara posisi sesudah yang ditunjuk oleh penunjuk tersebut element yang terakhir dalam larik. Lokasi bilangan ini di tunjuk oleh posMin. Lalu tukarkan nilai bilangan terkecil tersebut dengan nilai yang di tunjukkan posAwal. Proses seperti ini di ulang dari posAwal berniali 0 hingga n-2 , dengan n menyatakan jumlah element larik.
ilustrasi pengurutan dengan Selection sortnya akan terlihat seperti pada table dibawah ini :
4.Insertion Sort
Metode Insertion sort merupakan metode pengurutan data yang mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya sehinggan penambahan kartu tersebut akan membuat semua kartu tetap terurutkan. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
ilustrasi pengurutan dengan Insertion sortnya akan terlihat seperti pada table dibawah ini :
5.Quick Sort
Metode Quick sort merupakan metode pengurutan data yang di kemukakan pertama kali oleh C. AR Hoare pada tahun 1962. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme seperti berikut : Larik L[p..r] dengan indeks terkecil adalah p dan indeks terbesar adalah r disusun ulang (dipartisi) menjadi dua buah larik A[p..p] dan A[q+1…r] sehingga setiap elemen dalam A[p..q] selalu bernilai lebih kecil daripada A[q+1…r]. Selanjutnya kedua larik tersebut di urut secara rekursif. Dengan sendirinya kombinasi kedua larik tersebut membentuk larik dengan data yang telah di urut.
Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi. Sehingga didalamnya telah terjadi proses Rekursif.
6.Merge Sort
Merge sort merupakan salah satu teknik sorting yang mengurutkan suatu data dengan cara penggabungan.Merge sort juga menggunakan proses divide and conquer pada rekursi.Berikut adalah langkah kerja merge sort :
1. Devide
Memilah elemen – elemen dari data menjadi dua bagian.
2. Conquer
Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi akan berhenti jika telah mencapai elemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian. Sebagai catatan, pengkombinasian dilakukan dengan cara pembandingan. Elemen yang nilainya lebih kecil akan masuk ke kotak terlebih dahulu dan mengisi bagian disebelah kiri terlebih dahulu.Pada merge sort, data yang akan digabungkan berada pada suatu array, sebutlah array x dan array yang digunakan untuk menampung hasil gabung adalah array yang berbeda dari array x tersebut, sebutlah array y. Penyalinan elemen data dari array x ke array y ditentukan oleh hasil perbandingan data kelompok pertama x(i) dan data kelompok setelahnya x(j). Apabila nilai x(i) lebih kecil dibanding x(j) maka x(i) disalin ke y(k) kemudian indeks I dan k masing – masing ditambah satu. Proses ini akan berulang sampai seluruh data habis diproses.
7.Shell Sort
Ditemukan oleh Donal Shell pada tahun 1959. Merupakan algoritma paling efisien dari kelas sorting O(n2). Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen – elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak mengulangi atau merusak hasil sorting sebelumnya. Adapula nilai – nilai jarak yang dianjurkan adalah sebagai berikut :
1. Shell’s increment
1, 2, 4, 8
2. Hibbard’s increment
1, 3, 7, 15, …, 2k – 1
3. Sedgewick’s increment
1, 5, 19, 41, 109
Pada proses sorting, jarak yang diambil dilakukan secara menurun, sedangkan proses sorting elemennya dilakukan seperti insertion. Pada pengurutan elemen – elemen jarak lima, pengurutan dilakukan terhadap data ke-9, ke-4, ke-8, ke-3, dan seterusnya. Dimana jumlah data yang terlibat dalam suatu rangkaian pengurutan tidak selalu dua tetapi tergantung pada banyak data. Andaikan jumlah data adalah 11 maka pada rangkaian pengurutan pertama dilakukan pengurutan terhadap data ke-10, ke-5, dank e-0.
Contoh :
Rangkaian data :
1 2 3 4 5 6 7 8 9 10
2 5 1 3 9 7 8 0 5 4
Kenaikan : 5
Maka data yang pertama dibandingkan adalah data ke-6 dengan ke-1 kemudian ke-7 dengan ke-2 , ke-8 dengan ke-3, ke-9 dengan ke-4, ke-10 dengan ke-5. Dan hasilnya adalah :
1 2 3 4 5 6 7 8 9 10
2 5 0 3 4 7 8 5 5 9
Kenaikan : 2
Maka data yang selanjutnya dibandingkan adalah data ke-3 dengan ke-1, ke-4 dengan ke-2, ke-5 dengan ke-3, ke-6 dengan ke-4, ke-7 dengan ke-5, ke-8 dengan ke-6, ke-9 dengan ke-7,dan ke-10 dengan ke-8. Dan hasilnya adalah sebagai berikut :
1 2 3 4 5 6 7 8 9 10
0 3 2 5 4 5 5 7 8 9
Kenaikan : 1
Maka data yang akan diurutkan adalah data ke-2 dengan ke-1, ke-3 dengan ke-2, ke-4 dengan ke-3, dan seterusnya sampai data ke-10 dengan ke-9. Dan hasilnya adalah sebagai berikut :
1 2 3 4 5 6 7 8 9 10
0 2 3 4 5 5 5 7 8 9
Dalam proses pengurutannya shell sort dapat lima kali lebih cepat bila dibandingkan dengan bubble sort dan kurang lebih dua kali lebih cepat bila dibandingkan dengan insertion sort. Namun, jika dibandingkan dengan merge, heap, ataupun quicksort, shellsort masih tergolong lebih lambat. Tetapi algoritma sorting yang begitu sderhana membuat shellsort merupakan pilihan yang cocok untuk melakukan sorting pada data kurang dari 5000 item atau data dengan ukuran tidak terlalu besar.
Tidak ada komentar:
Posting Komentar