Algoritma adalah seperangkat aturan yang terdefinisi dengan baik yang digunakan untuk menyelesaikan suatu masalah dalam sejumlah langkah terbatas. Sederhananya, ini adalah proses penyelesaian masalah komputer. Dalam proses ini, apakah Anda membentuk ide pemecahan masalah atau menulis program, Anda menerapkan algoritma tertentu. Yang pertama adalah algoritma yang diimplementasikan melalui penalaran, dan yang kedua adalah algoritma yang diimplementasikan melalui operasi.
Suatu algoritma harus memiliki lima karakteristik penting berikut:
1. Keterbatasan: Suatu algoritma harus memastikan bahwa algoritma tersebut berakhir setelah menjalankan sejumlah langkah yang terbatas;
2. Ketepatan: Setiap langkah algoritma harus didefinisikan dengan jelas;
3. Masukan: Suatu algoritma memiliki 0 atau lebih masukan untuk menggambarkan situasi awal operan;
4. Keluaran: Suatu algoritma mempunyai satu atau lebih keluaran untuk mencerminkan hasil pengolahan data masukan. Algoritme tanpa keluaran tidak ada artinya;
5. Kelayakan: Pada prinsipnya, algoritme dapat berjalan secara akurat, dan dapat diselesaikan oleh orang-orang yang menggunakan pena dan kertas untuk melakukan sejumlah operasi terbatas.
Merge sort (MERGE SORT) adalah jenis lain dari metode pengurutan yang berbeda. Arti dari penggabungan adalah menggabungkan dua atau lebih rangkaian data yang terurut menjadi suatu rangkaian data yang baru terurut, sehingga disebut juga dengan algoritma penggabungan. Ide dasarnya adalah dengan mengasumsikan bahwa larik A mempunyai N elemen, maka larik A dapat dianggap terdiri dari N barisan berurutan, masing-masing barisan memiliki panjang 1, dan kemudian digabungkan dua per dua untuk mendapatkan N/2 Barisan berurutan dari panjang 2 atau 1 kemudian digabungkan dua per dua, dan ini diulangi sampai diperoleh urutan data terurut dengan panjang N. Metode pengurutan ini disebut pengurutan gabungan 2 arah.
Misal array A mempunyai 7 data yaitu: 49 38 65 97 76 13 27. Maka proses pengoperasian menggunakan algoritma merge sort ditunjukkan pada Gambar 7:
Nilai awal[49] [38] [65] [97] [76] [13] [27]
Dilihat terdiri dari 7 barisan dengan panjang 1. Setelah penggabungan pertama [38 49] [65 97] [13 76] [27]
Dilihat terdiri dari 4 barisan dengan panjang 1 atau 2. Setelah penggabungan kedua [38 49 65 97] [13 27 76]
Dilihat terdiri dari 2 barisan dengan panjang 4 atau 3. Setelah penggabungan ketiga [13 27 38 49 65 76 97]
Gambar 6 Diagram proses algoritma pengurutan gabungan Operasi inti dari algoritma penggabungan adalah menggabungkan dua urutan terurut yang berdekatan dalam array satu dimensi menjadi satu urutan terurut. Algoritma penggabungan juga dapat diimplementasikan dengan menggunakan algoritma rekursif yang bentuknya relatif sederhana, namun kepraktisannya kurang baik.
Banyaknya penggabungan pada algoritma penggabungan merupakan besaran yang sangat penting. Menurut perhitungan, jika terdapat 3 hingga 4 elemen dalam array, jumlah penggabungan adalah 2, bila terdapat 5 hingga 8 elemen, jumlah penggabungan adalah 3. , dan jika ada 9 hingga Jika ada 16 elemen, maka banyaknya penggabungan adalah 4. Menurut aturan ini, jika terdapat N barisan berikutnya, maka dapat disimpulkan bahwa banyaknya penggabungan adalah
X (2>=N, X terkecil yang memenuhi subkondisi).
Deskripsi algoritma gelembung:
Sebelum menjelaskan algoritma bubble sort, mari kita kenalkan dulu algoritma yang menempatkan angka terbesar di antara 10 angka (dalam array A) pada posisi terakhir. Algoritmanya dijelaskan sebagai berikut:
(1) Dari larik A[1] hingga A[10], bandingkan dua bilangan yang berdekatan secara berpasangan. Artinya, A[1] dibandingkan dengan A[2], dan setelah dibandingkan, A[2] dibandingkan dengan A[3],...dan terakhir A[9] dibandingkan dengan A[10].
(2) Pada setiap perbandingan, jika bilangan sebelumnya lebih besar dari bilangan terakhir, maka kedua bilangan tersebut akan ditukar, yaitu bilangan yang lebih besar akan dipindahkan ke belakang dan bilangan yang lebih kecil akan dipindahkan ke depan. Misalnya pada perbandingan pertama, jika A[1] lebih besar dari A[2], maka nilai A[1] dan A[2] dipertukarkan. Gambar di bawah ini menggunakan 6 data untuk menggambarkan algoritma di atas.
Asumsikan 6 data tersebut adalah: A[]=5 7 4 3 8 6
SEBUAH[1] SEBUAH[2] SEBUAH[3] SEBUAH[4] SEBUAH[5] SEBUAH[6]
5 7 4 3 8 6 Pertama kali, A[1]=5 dan A[2]=7 dibandingkan, 7>5, tidak ada pertukaran yang dilakukan.
5 7 4 3 8 6 Kedua kalinya, A[2]=7 dan A[3]=4 dibandingkan, 4<7, tukar.
Maka data setelah perbandingan kedua adalah 5 4 7 3 8 6
5 4 7 3 8 6 Ketiga kalinya, A[3]=7 dan A[4]=3 dibandingkan, 3<7, tukar.
Maka data setelah perbandingan ketiga adalah 5 4 3 7 8 6
5 4 3 7 8 6 Keempat kalinya, A[4]=7 dan A[5]=8 dibandingkan, 8>7, tidak dilakukan pertukaran.
5 4 3 7 8 6 Kali kelima, A[6]=6 dan A[5]=8 dibandingkan, 6<8, tukar.
Kemudian hasil kelima dan terakhir adalah
5 4 3 7 6 8
******************************************************* * *****
Deskripsi algoritma pengurutan seleksi:
Sebelum memperkenalkan metode pengurutan pilihan, mari kita perkenalkan algoritma yang menempatkan angka terkecil di posisi pertama. Tentu saja, Anda juga dapat menggunakan metode pengurutan gelembung yang disebutkan di atas. Sekarang kita menggunakan algoritma baru: Ideologi panduannya Saya tidak termasuk dalam a terburu-buru untuk mengubah posisi pada awalnya, tetapi mulailah dengan A[1] mulai memeriksa satu per satu. Untuk melihat bilangan mana yang terkecil, tuliskan posisi P dari bilangan tersebut. Setelah pemindaian selesai, tukar A[P] dan A[1]. [1] hingga A[ 10] dipindahkan ke posisi depan. Langkah-langkah algoritmanya adalah sebagai berikut:
1) Pertama, asumsikan bilangan pada A[1] adalah bilangan terkecil, dan catat posisi P=1 saat ini;
2) Bandingkan A[P] dan A[I] secara berurutan (I berubah dari 2 menjadi 10). Pada setiap perbandingan, jika angka di A[I] lebih kecil dari angka di A[P], maka I nilainya ditugaskan ke P, sehingga P selalu menunjuk ke posisi bilangan terkecil yang sedang dipindai, artinya, A[P] selalu sama dengan bilangan terkecil dari semua bilangan yang dipindai. Setelah membandingkan satu per satu, P menunjuk pada posisi bilangan terkecil diantara 10 bilangan tersebut, yaitu A[P] adalah bilangan terkecil diantara 10 bilangan tersebut;
3) Balikkan bilangan A[P] dan A[1], maka bilangan terkecil berada pada A[1] yaitu paling depan.
Jika sekarang Anda mengulangi algoritme ini, tetapi setiap kali diulang, rentang rangkaian yang dibandingkan akan dipindahkan mundur satu posisi. Artinya, pada perbandingan kedua, rentangnya adalah dari angka ke-2 hingga angka ke-N. Carilah posisi P dari angka terkecil dalam rentang tersebut, lalu tukar A[P] dan A[2], sehingga dari angka ke-2. Bilangan terkecil dari awal sampai bilangan ke-N ada pada A [2] berhasil, ketiga kalinya mencari bilangan terkecil dari bilangan ke-3 sampai bilangan ke-N, lalu menukar A[P] dan A[3]... Setelah mengulangi proses ini N-1 kali, Susun saja N angka pada array A dari kecil ke besar. Metode penyortiran ini adalah penyortiran seleksi.
******************************************************* * ***************
Deskripsi algoritma pengurutan penyisipan:
Dengan mempelajari dua metode di atas, Anda dapat memahami ide dasar pengurutan, dan Anda juga dapat mengurutkan array tidak berurutan dari besar ke kecil (urutan menurun) atau dari kecil ke besar (urutan menaik). Sekarang asumsikan bahwa ada urutan data yang sudah diurutkan, dan diperlukan untuk memasukkan nomor ke dalam urutan data yang sudah diatur ini, tetapi urutan data tersebut harus tetap diurutkan setelah penyisipan digunakan - Metode insertion sort, operasi dasar dari insertion sort adalah memasukkan suatu data ke dalam data terurut yang telah diurutkan, sehingga diperoleh data terurut baru dengan angka tambah satu.
Soal: Terdapat N buah data pada larik A yang diurutkan dari kecil ke besar. Masukkan angka X, lalu masukkan nilai X ke dalam larik A, sehingga larik A yang dimasukkan tetap tersusun berurutan dari kecil hingga besar. .
Maka algoritma untuk menyelesaikan permasalahan tersebut adalah:
1) Carilah posisi di mana X harus disisipkan dengan membandingkan ukurannya, apakah harus ditempatkan pada posisi ke-I;
2) Pindahkan semua elemen array mulai dari I (termasuk I) satu posisi ke belakang, yaitu A[I+1]:=A[I];
Penyortiran cepat merupakan penyempurnaan dari penyortiran gelembung. Ide dasarnya adalah membagi data yang akan diurutkan menjadi dua bagian yang independen melalui pengurutan satu arah. Semua data di satu bagian lebih kecil dari semua data di bagian lainnya, kemudian kedua bagian data tersebut diurutkan secara berurutan. Untuk penyortiran cepat, seluruh proses penyortiran dapat dilakukan secara rekursif, sehingga seluruh data menjadi suatu urutan yang terurut.
Asumsikan bahwa array yang akan diurutkan adalah A[1]...A[N]. Pertama, pilih data secara acak (biasanya data pertama) sebagai data kunci, lalu letakkan semua angka yang lebih besar darinya di depannya, dan semua bilangan yang lebih besar darinya bilangan besar ditempatkan di belakangnya. Proses ini disebut penyortiran cepat. Algoritma untuk quick sort adalah:
1) Tetapkan dua variabel I dan J. Saat pengurutan dimulai, I:=1, J:=N;
2) Gunakan elemen array pertama sebagai data kunci dan tetapkan ke X, yaitu X:=A[1];
3) Pencarian maju dari J, yaitu pencarian maju dari belakang (J:=J-1), cari nilai pertama yang kurang dari X, dan tukarkan keduanya;
4) Cari mundur dari I, yaitu cari dari depan ke belakang (I:=I+1), cari nilai pertama yang lebih besar dari X, lalu tukarkan keduanya;
5) Ulangi langkah 3 dan 4 sampai I=J;
Misal: nilai array A yang akan diurutkan adalah: (data kunci awal X:=49)
SEBUAH[1] SEBUAH[2] SEBUAH[3] SEBUAH[4] SEBUAH[5] SEBUAH[6] SEBUAH[7]:
49 38 65 97 76 13 27
Setelah penukaran pertama: 27 38 65 97 76 13 49
(Setelah mencari dari belakang sesuai dengan langkah ketiga algoritma pertukaran kedua: 27 38 49 97 76 13 65
(Ikuti langkah keempat algoritma dan mulai dari depan untuk menemukan nilai >
Setelah pertukaran ketiga: 27 38 13 97 76 49 65
(Menurut langkah kelima dari algoritma, langkah ketiga dari algoritma akan dieksekusi lagi dari akhir untuk menemukan pertukaran keempat: 27 38 13 49 76 97 65
(Ikuti langkah keempat algoritma dan mulai dari depan untuk menemukan nilai yang lebih besar dari X, 97>49, tukar keduanya, saat ini J:=4)
Saat ini, ketika menjalankan langkah ketiga, ditemukan I=J, sehingga mengakhiri quick sort. Hasil setelah quick sort adalah: 27 38 13 49 76 97 65, yaitu semua bilangan yang lebih besar dari 49 ada di 49. , jadi angka yang kurang dari 49 semuanya ada di depan 49.
Penyortiran cepat adalah memanggil proses ini secara rekursif - membagi urutan data dengan 49 sebagai titik tengah, melakukan pengurutan cepat serupa di bagian depan dan belakang, sehingga menyelesaikan penyortiran cepat seluruh urutan data, dan akhirnya membalik urutan data menjadi urutan yang berurutan. Menurut ide ini, seluruh proses pengurutan cepat array A di atas ditunjukkan pada Gambar 6:
Keadaan awal {49 38 65 97 76 13 27}
Setelah diurutkan cepat, dibagi menjadi {27 38 13} 49 {76 97 65}
Urutkan dengan cepat masing-masing bagian depan dan belakang {13} 27 {38}
akhir akhir {49 65} 76 {97} 49 {65} akhir akhir
******************************************************* * ****************************
Gambar 6 Deskripsi algoritma penyortiran cepat sepanjang proses penyortiran cepat
1). Misalkan N (dengan asumsi N=10) angka disimpan dalam array S;
2), di S[1. . Ambil elemen apa pun di N] sebagai dasar perbandingan, misalnya T=S[1]. Tujuan awalnya adalah menentukan posisi K dimana T seharusnya berada pada hasil pengurutan. . . K-1]<=S[K]<=S[K+1..N], yaitu angka sebelum S[K] semuanya lebih kecil dari S[K], dan angka setelah S[K] adalah semuanya lebih besar dari S[ K];
3) Penggunaan gagasan bagi-dan-taklukkan (yaitu strategi menjadikan yang besar dan yang kecil menjadi kecil) dapat lebih meningkatkan S[1. . K-1] dan S[K+1. . N] Kedua kumpulan data tersebut kemudian diurutkan dengan cepat hingga hanya tersisa satu data pada objek pengelompokan.
Jika spesifik datanya seperti berikut, maka proses penyortiran cepat yang pertama adalah:
Subskrip array: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
aku j
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53