kaedah mengisih (sorting)
DESCRIPTION
kaedah sortingTRANSCRIPT
Kaedah Mengisih (sorting)
Pengenalan
Dalam sains komputer dan matematik, algoritma isihan (sorting) merupakanalgoritma yang menyusun sekumpulan data dalam tertib tertentu. Senarai data terisih adalah penting kerana memudahkan proses pemahaman dan proses analisa koleksi data yang disimpan dan seterusnya mempercepatkan operasi carian. Sebagai contoh, nombor telefon disusun secara menaik mengikut abjad nama pelanggan dalam direktori telefon. Tertib yang paling banyak digunakan ialah tertib bernombor dan tertib berleksikograf (lexicographical order).
Dua aktiviti utama dalam proses isihan ialah perbandingan elemen-elemenuntuk menentukan kedudukan elemen dan peralihan kedudukan elemen-elemen untuk menyusun elemen-elemen tersebut. Bilangan perbandingan elemen dan bilangan peralihan elemen dalam algoritma isihan menentukan keberkesananalgoritma tersebut. Keberkesanan kedua-dua aktiviti ini juga bergantung kepada bilangan elemen yang perlu ditukar kedudukan dalam proses isihan. Isihan yang efisien adalah penting untuk mengoptimumkan penggunaan algoritma yang lain.
Isihan Pilihan secara tukar ganti (selection with interchange sort)
Dalam laluan pertama, nombor terkecil dalam senarai dicari dan ditukar ganti dengan nombor pertama. Dalam senarai di bawah yang mempunyai 5 nombor akan melibatkan 4 perbandingan.
75
65
43
64
52
43
65
75
64
52
Bagi laluan kedua, nombor terkecil dari nombor kedua ke bawah dicari dan ditukar gantikan dengan nombor kedua. Senarai sekarang melibatkan 3 perbandingan.
Dalam laluan ketiga, nombor terkecil dari nombor ketiga ke bawah dicari dan ditukargantikan dengan nombor ketiga. Senarai ini melibatkan 2 perbandingan.
Laluan keempat pula hanya melibatkan 1 perbandingan untuk contoh di atas yangmempunyai 5 nombor. Jumlah bilangan perbandingan ialah 4 + 3 + 2 + 1 = 10 dan bilangan pertukaran yang maksimum ialah 4.
Ini bermakna ini jika senarai mempunyai n data, maka proses ini akan berterusan untuk (n-1) pertukaran dan n(n-1)/ 2 perbandingan.
43
65
75
64
52
43
52
75
64
65
43
52
75
64
65
43
52
64
75
65
43
52
64
75
65
43
52
64
65
75
Latihan
1. Dalam suatu ujian, markah Ali ialah 57, markah Bill ialah 67, markah Cleo ialah 42 dan Debbie mendapat markah 73.
i) Aplikasikan isihan pilihan secara tukar ganti untuk menyusun individu dari nama mengikut huruf abjad ke markah mengikut tertib menurun.
ii) Berapakah bilangan perbandingan dan pertukaran yang perlu dibuat dalam isihan tersebut?
2. Satu senarai yang mempunyai 6 item disusun dalam tertib menurun. Berikan bilangan perbandingan yang diperlukan dalam isihan pilihan secara tukar ganti untuk menyusun senarai dalam tertib menaik.
Senarai = { 6, 5, 4, 3, 2, 1}
3. Dalam suatu pertandingan melukis poster, Rahman mendapat 81 markah, Ramlah mendapat 74 markah, Chong mendapat 63 markah, David mendapat 60 markah dan Mariam mendapat markah 52. Markah mereka telah telah disusun seperti berikut:
a Gunakan kaedah isihan pilihan secara tukar ganti untuk menyusun markah mereka mengikut tertib menaik. Tunjukkan hasil susunan markah bagi setiap pass dengan jelas.
b Nyatakan jumlah bilangan perbandingan dan bilangan pertukaran sehingga markah tersusun.
81
74
63
60
52
Isihan Shuttle (shuttle sort)
Isihan shuttle membandingkan nombor ke-n dan ke-(n+1) untuk memastikannilai terkecil disusun dahulu. Setiap kali pertukaran, kita akan bandingkan denganturutan sebelumnya dan tukar jika perlu. Bilangan maksimum perbandingan bagilaluan ke-n ialah n.
Bilangan laluan maksimum bagi n data ialah n-1, dan bilanganperbandingan yang maksimum untuk n data ialah n(n-1)/2
Laluan pertama :
Bandingkan dua nombor di depan dan tukar lokasi untukmendapatkan tertib menaik.
Laluan kedua :
Bandingkan nombor kedua dan ketiga dan tukar lokasi jikaperlu, kemudian bandingkan nombor pertama dan kedua.
81
74
63
72
85
74
81
63
72
85
74
81
63
72
85
74
63
81
72
85
63
74
81
72
85
Laluan ketiga :
Bandingkan nombor ketiga dan keempat dan tukar lokasi jika perlu, kemudian bandingkan nombor kedua dan ketiga, akhir sekali bandingkan nombor pertama dan nombor kedua.
Laluan keempat :
Bandingkan nombor keempat dan kelima dan tukar lokasi bila perlu. kemudian bandingan antara nombor ketiga dan keempat dan tukar lokasi jika perlu, selepas itu bandingkan nombor kedua dan ketiga, akhir sekali bandingkan nombor pertama dan nombor kedua.
63
74
81
72
85
63
74
72
81
85
63
72
74
81
85
63
72
74
81
85
63
72
74
81
85
63
72
74
81
85