Materi Pelengkap CS50 (Minggu 3, Kuliah 7 dan 8): Notasi Asimptotik, Algoritma Penyortiran dan Pencarian

Kuliah dari kursus Harvard tentang dasar-dasar pemrograman Tugas CS50 CS50 minggu ke 3 bagian 1 Tugas CS50 minggu ke 3 bagian 2

Notasi asimtotik

Mengukur kecepatan suatu algoritma secara real time—dalam hitungan detik dan menit—tidaklah mudah. Satu program mungkin berjalan lebih lambat dari yang lain bukan karena ketidakefisienannya, tetapi karena lambatnya sistem operasi, ketidakcocokan dengan perangkat keras, memori komputer ditempati oleh proses lain... Untuk mengukur efektivitas algoritma, konsep universal telah diciptakan , terlepas dari lingkungan tempat program dijalankan. Kompleksitas asimtotik suatu masalah diukur dengan menggunakan notasi Big O. Misalkan f(x) dan g(x) merupakan fungsi yang terdefinisi pada lingkungan tertentu dari x0, dan g tidak hilang di sana, maka f adalah “O” lebih besar dari g untuk (x -> x0) jika terdapat konstanta C> 0 , bahwa untuk semua x di lingkungan titik x0 berlaku pertidaksamaan |f(x)| <= C |g(x)| Sedikit kurang ketat: f adalah “O” lebih besar dari g jika terdapat konstanta C>0, yang untuk semua x > x0 f(x) <= C*g(x) Jangan takut definisi formal! Pada dasarnya, ini menentukan peningkatan asimtotik dalam waktu berjalan program ketika jumlah data input Anda bertambah hingga tak terbatas. Misalnya, Anda membandingkan pengurutan array yang terdiri dari 1000 elemen dan 10 elemen, dan Anda perlu memahami bagaimana waktu berjalan program akan meningkat. Atau Anda perlu menghitung panjang serangkaian karakter dengan menelusuri karakter demi karakter dan menambahkan 1 untuk setiap karakter: c - 1 a - 2 t - 3 Kecepatan asimtotiknya = O(n), di mana n adalah jumlah huruf dalam sebuah kata. Jika dihitung berdasarkan prinsip ini, waktu yang diperlukan untuk menghitung seluruh baris sebanding dengan jumlah karakter. Menghitung jumlah karakter dalam string 20 karakter memerlukan waktu dua kali lebih lama dibandingkan menghitung jumlah karakter dalam string sepuluh karakter. Bayangkan dalam variabel panjang Anda menyimpan nilai yang sama dengan jumlah karakter dalam string. Misalnya, panjang = 1000. Untuk mendapatkan panjang sebuah string, Anda hanya memerlukan akses ke variabel ini; Anda bahkan tidak perlu melihat string itu sendiri. Dan tidak peduli bagaimana kita mengubah panjangnya, kita selalu dapat mengakses variabel ini. Dalam hal ini, kecepatan asimtotik = O(1). Mengubah data masukan tidak mengubah kecepatan tugas tersebut; pencarian selesai dalam waktu yang konstan. Dalam hal ini, programnya konstan secara asimtotik. Kerugian: Anda membuang-buang memori komputer untuk menyimpan variabel tambahan dan waktu tambahan untuk memperbarui nilainya. Jika menurut Anda waktu linier itu buruk, kami dapat meyakinkan Anda bahwa ini bisa menjadi jauh lebih buruk. Misalnya, O(n ² ). Notasi ini berarti bahwa seiring bertambahnya n, waktu yang diperlukan untuk melakukan iterasi melalui elemen (atau tindakan lain) akan bertambah semakin tajam. Namun untuk n kecil, algoritma dengan kecepatan asimtotik O(n ² ) dapat bekerja lebih cepat dibandingkan algoritma dengan kecepatan asimtotik O(n). Namun suatu saat fungsi kuadrat akan mengambil alih fungsi linier, tidak ada jalan lain. Kompleksitas asimtotik lainnya adalah waktu logaritmik atau O(log n). Dengan bertambahnya n, fungsi ini meningkat dengan sangat lambat. O(log n) adalah waktu berjalan dari algoritma pencarian biner klasik dalam array yang diurutkan (ingat direktori telepon yang robek dalam kuliah?). Array dibagi menjadi dua, lalu separuh tempat elemen berada dipilih, dan setiap kali mengurangi area pencarian hingga setengahnya, kami mencari elemen tersebut. Apa yang terjadi jika kita langsung menemukan apa yang kita cari, membagi susunan data kita menjadi dua untuk pertama kalinya? Ada istilah waktu terbaik - Omega-besar atau Ω(n). Dalam kasus pencarian biner = Ω(1) (ditemukan dalam waktu yang konstan, berapa pun ukuran arraynya). Pencarian linier berjalan dalam waktu O(n) dan Ω(1) jika elemen yang dicari adalah elemen pertama. Simbol lainnya adalah theta (Θ(n)). Digunakan ketika pilihan terbaik dan terburuk adalah sama. Ini cocok untuk contoh di mana kita menyimpan panjang string dalam variabel terpisah, jadi untuk berapa pun panjangnya, cukup merujuk ke variabel ini. Untuk algoritma ini, kasus terbaik dan terburuk masing-masing adalah Ω(1) dan O(1). Artinya algoritma berjalan dalam waktu Θ(1).

Pencarian linier

Saat Anda membuka browser web, mencari halaman, informasi, teman di jejaring sosial, Anda melakukan pencarian, sama seperti ketika mencoba mencari sepasang sepatu yang tepat di toko. Anda mungkin memperhatikan bahwa keteraturan berdampak besar pada cara Anda melakukan penelusuran. Jika Anda memiliki semua kemeja di lemari Anda, biasanya lebih mudah untuk menemukan yang Anda butuhkan di antara kemeja tersebut daripada di antara kemeja yang tersebar tanpa sistem di seluruh ruangan. Pencarian linier adalah metode pencarian berurutan, satu per satu. Saat Anda meninjau hasil pencarian Google dari atas ke bawah, Anda menggunakan pencarian linier. Contoh . Katakanlah kita mempunyai daftar angka: 2 4 0 5 3 7 8 1 Dan kita perlu mencari 0. Kita langsung melihatnya, namun program komputer tidak bekerja seperti itu. Dia mulai dari awal daftar dan melihat angka 2. Lalu dia memeriksa, 2=0? Bukan, jadi dia melanjutkan dan beralih ke karakter kedua. Kegagalan juga menantinya di sana, dan hanya di posisi ketiga algoritma menemukan nomor yang diperlukan. Kode semu untuk pencarian linier: Fungsi linearSearch menerima dua argumen sebagai input - kunci kunci dan array array[].Kuncinya adalah nilai yang diinginkan, pada contoh sebelumnya kunci = 0. Array adalah daftar angka yang kita akan memeriksanya. Jika kita tidak menemukan apa pun, fungsi tersebut akan mengembalikan -1 (posisi yang tidak ada dalam array). Jika pencarian linier menemukan elemen yang diinginkan, fungsi akan mengembalikan posisi elemen yang diinginkan berada dalam array. Hal yang baik tentang pencarian linier adalah ia dapat digunakan untuk array apa pun, apa pun urutan elemennya: kita akan tetap menelusuri seluruh array. Ini juga merupakan kelemahannya. Jika Anda perlu mencari angka 198 dalam larik 200 angka yang diurutkan secara berurutan, perulangan for akan melalui 198 langkah. Anda mungkin sudah menebak metode mana yang bekerja lebih baik untuk array yang diurutkan?

Pencarian biner dan pepohonan

Bayangkan Anda memiliki daftar karakter Disney yang diurutkan berdasarkan abjad dan Anda perlu menemukan Mickey Mouse. Secara linear akan memakan waktu yang lama. Dan jika kita menggunakan "metode merobek direktori menjadi dua", kita langsung menuju ke Jasmine, dan kita dapat dengan aman membuang paruh pertama daftar, menyadari bahwa Mickey tidak mungkin ada di sana. Dengan menggunakan prinsip yang sama, kita membuang kolom kedua. Melanjutkan strategi ini, kita akan menemukan Mickey hanya dalam beberapa langkah. Mari kita cari angka 144. Kita bagi daftarnya menjadi dua, dan kita mendapatkan angka 13. Kita evaluasi apakah angka yang kita cari lebih besar atau lebih kecil dari 13. 13 < 144, sehingga kita bisa mengabaikan semua angka di sebelah kiri 13 dan nomor ini sendiri. Sekarang daftar pencarian kita terlihat seperti ini: Ada jumlah elemen yang genap, jadi kita memilih prinsip dimana kita memilih "tengah" (mendekati awal atau akhir). Katakanlah kita memilih strategi kedekatan dengan awal. Dalam hal ini, "tengah" kita = 55. 55 < 144. Kita buang lagi bagian kiri daftar. Beruntung bagi kami, angka rata-rata berikutnya adalah 144. Kami menemukan 144 dalam array 13 elemen menggunakan pencarian biner hanya dalam tiga langkah. Pencarian linier akan menangani situasi yang sama dalam 12 langkah. Karena algoritme ini mengurangi jumlah elemen dalam array hingga setengahnya pada setiap langkah, algoritme ini akan menemukan elemen yang diperlukan dalam waktu asimtotik O(log n), dengan n adalah jumlah elemen dalam daftar. Artinya, dalam kasus kita, waktu asimtotik = O(log 13) (ini sedikit lebih dari tiga). Kode semu dari fungsi pencarian biner: Fungsi ini mengambil 4 argumen sebagai masukan: kunci yang diinginkan, larik larik data [], yang berisi larik yang diinginkan, min dan maks adalah penunjuk ke angka maksimum dan minimum dalam larik, yang kita sedang melihat langkah algoritma ini. Sebagai contoh kita, gambar berikut awalnya diberikan: Mari kita menganalisis kode lebih lanjut. titik tengah adalah bagian tengah array kita. Itu tergantung pada titik ekstrim dan berpusat di antara titik-titik tersebut. Setelah kita menemukan bagian tengahnya, kita periksa apakah kurang dari angka kunci kita. Jika ya, maka kuncinya juga lebih besar dari angka mana pun di sebelah kiri tengah, dan kita dapat memanggil fungsi binernya lagi, hanya saja sekarang min = titik tengah + 1. Jika ternyata kunci < titik tengah, kita dapat membuang nomor itu sendiri dan semua nomornya, terletak di sebelah kanannya. Dan kami memanggil pencarian biner melalui array dari angka min hingga nilainya (titik tengah – 1). Terakhir, cabang ketiga: jika nilai di titik tengah tidak lebih besar atau lebih kecil dari kunci, maka tidak ada pilihan selain menjadi angka yang diinginkan. Dalam hal ini, kami mengembalikannya dan menyelesaikan program. Terakhir, mungkin saja nomor yang Anda cari tidak ada dalam array sama sekali. Untuk mempertimbangkan kasus ini, kami melakukan pemeriksaan berikut: Dan kami kembali (-1) untuk menunjukkan bahwa kami tidak menemukan apa pun. Anda sudah tahu bahwa pencarian biner memerlukan pengurutan array. Jadi, jika kita memiliki array yang tidak disortir dan kita perlu mencari elemen tertentu, kita memiliki dua pilihan:

1. Urutkan daftar dan terapkan pencarian biner
2. Jaga agar daftar selalu diurutkan sekaligus menambahkan dan menghapus elemen darinya.

Salah satu cara untuk menjaga agar daftar tetap terurut adalah dengan menggunakan pohon pencarian biner. Pohon pencarian biner adalah struktur data yang memenuhi persyaratan berikut:

• Ini adalah pohon (struktur data yang meniru struktur pohon - ia memiliki akar dan simpul lain (daun) yang dihubungkan oleh “cabang” atau tepian tanpa siklus)
• Setiap node memiliki 0, 1 atau 2 anak
• Subpohon kiri dan kanan adalah pohon pencarian biner.
• Semua node pada subpohon kiri dari node X yang berubah-ubah memiliki nilai kunci data yang lebih kecil dari nilai kunci data dari node X itu sendiri.
• Semua node di subpohon kanan dari node X yang berubah-ubah memiliki nilai kunci data yang lebih besar atau sama dengan nilai kunci data dari node X itu sendiri.

Perhatian: akar pohon “programmer”, tidak seperti yang asli, ada di atas. Setiap sel disebut simpul, dan simpul-simpul tersebut dihubungkan oleh sisi-sisinya. Akar pohon adalah sel nomor 13. Subpohon kiri dari simpul 3 disorot dengan warna pada gambar di bawah ini: Pohon kita memenuhi semua persyaratan untuk pohon biner. Artinya setiap subpohon kirinya hanya berisi nilai yang lebih kecil atau sama dengan nilai simpulnya, sedangkan subpohon kanannya hanya berisi nilai yang lebih besar atau sama dengan nilai simpulnya. Subpohon kiri dan kanan merupakan subpohon biner. Metode membuat pohon biner bukan satu-satunya: di bawah gambar Anda melihat opsi lain untuk kumpulan angka yang sama, dan dalam praktiknya bisa ada banyak opsi. Struktur ini membantu melakukan pencarian: kami menemukan nilai minimum dengan berpindah dari atas ke kiri dan ke bawah setiap saat. Jika Anda perlu mencari angka maksimal, kita mulai dari atas ke bawah dan ke kanan. Menemukan angka yang bukan minimum atau maksimum juga cukup sederhana. Kita turun dari akar ke kiri atau ke kanan, tergantung apakah simpul kita lebih besar atau lebih kecil dari simpul yang kita cari. Jadi, jika kita perlu mencari angka 89, kita melalui jalur ini: Anda juga dapat menampilkan angka-angka tersebut dalam urutan pengurutan. Misalnya, jika kita ingin menampilkan semua angka dalam urutan menaik, kita ambil subpohon kiri dan, mulai dari titik paling kiri, naik ke atas. Menambahkan sesuatu ke pohon juga mudah. Hal utama yang perlu diingat adalah strukturnya. Katakanlah kita perlu menambahkan nilai 7 ke pohon. Mari kita pergi ke akar dan memeriksanya. Angka 7 < 13, jadi kita ke kiri. Kita melihat 5 di sana, dan kita ke kanan, karena 7 > 5. Selanjutnya, karena 7 > 8 dan 8 tidak mempunyai keturunan, kita buat sebuah cabang dari 8 ke kiri dan tempelkan 7 padanya. Anda juga dapat menghapus simpul dari pohon, tapi ini agak lebih rumit. Ada tiga skenario penghapusan berbeda yang perlu kita pertimbangkan.

1. Opsi paling sederhana: kita perlu menghapus sebuah simpul yang tidak memiliki anak. Misalnya angka 7 yang baru saja kita tambahkan. Dalam hal ini, kita cukup mengikuti jalur ke titik dengan nomor ini dan menghapusnya.
2. Sebuah simpul mempunyai satu simpul anak. Dalam hal ini, Anda dapat menghapus simpul yang diinginkan, tetapi turunannya harus terhubung ke “kakek”, yaitu simpul tempat nenek moyang terdekatnya tumbuh. Misalnya, dari pohon yang sama kita perlu menghapus angka 3. Dalam hal ini, kita gabungkan turunannya, satu, bersama dengan seluruh subpohon menjadi 5. Ini dilakukan dengan sederhana, karena semua simpul di sebelah kiri 5 akan menjadi kurang dari angka ini (dan kurang dari triple jarak jauh).
3. Kasus yang paling sulit adalah ketika simpul yang dihapus mempunyai dua anak. Sekarang hal pertama yang perlu kita lakukan adalah mencari titik di mana nilai berikutnya yang lebih besar disembunyikan, kita perlu menukarnya, lalu menghapus titik yang diinginkan. Perhatikan bahwa simpul dengan nilai tertinggi berikutnya tidak boleh memiliki dua anak, maka anak kirinya akan menjadi kandidat terbaik untuk nilai berikutnya. Mari kita hilangkan simpul akar 13 dari pohon kita. Pertama, kita mencari bilangan yang paling dekat dengan 13, yang mana lebih besar darinya. Ini 21. Tukar 21 dan 13 dan hapus 13.

Ada berbagai cara untuk membangun pohon biner, ada yang bagus, ada yang tidak begitu bagus. Apa yang terjadi jika kita mencoba membuat pohon biner dari daftar yang diurutkan? Semua nomor hanya akan ditambahkan ke cabang kanan yang sebelumnya. Jika kita ingin menemukan nomornya, kita tidak punya pilihan selain mengikuti rantainya ke bawah. Ini tidak lebih baik dari pencarian linier. Ada struktur data lain yang lebih kompleks. Tapi kami tidak akan mempertimbangkannya untuk saat ini. Anggap saja untuk menyelesaikan masalah pembuatan pohon dari daftar yang diurutkan, Anda dapat mencampur data masukan secara acak.

Algoritma pengurutan

Ada serangkaian angka. Kita perlu memilahnya. Untuk mempermudah, kita asumsikan kita mengurutkan bilangan bulat dalam urutan menaik (dari terkecil ke terbesar). Ada beberapa cara yang diketahui untuk mencapai proses ini. Selain itu, Anda selalu dapat memimpikan topik dan membuat modifikasi algoritme.

Menyortir berdasarkan pilihan

Ide utamanya adalah membagi daftar kita menjadi dua bagian, diurutkan dan tidak diurutkan. Pada setiap langkah algoritma, suatu bilangan baru dipindahkan dari bagian yang tidak diurutkan ke bagian yang diurutkan, dan seterusnya hingga semua bilangan berada di bagian yang diurutkan.

1. Temukan nilai minimum yang belum disortir.
2. Kami menukar nilai ini dengan nilai pertama yang tidak diurutkan, sehingga menempatkannya di akhir array yang diurutkan.
3. Jika masih ada nilai yang belum diurutkan, kembali ke langkah 1.

Pada langkah pertama, semua nilai tidak disortir. Sebut saja bagian yang tidak disortir sebagai Unsorted, dan bagian yang disortir sebagai Sorted (ini hanyalah kata-kata dalam bahasa Inggris, dan kami melakukan ini hanya karena Sorted jauh lebih pendek daripada “Sorted part” dan akan terlihat lebih baik dalam gambar). Kami menemukan jumlah minimum di bagian array yang tidak diurutkan (yaitu, pada langkah ini - di seluruh array). Nomor ini adalah 2. Sekarang kita mengubahnya dengan yang pertama di antara yang tidak diurutkan dan meletakkannya di akhir array yang diurutkan (pada langkah ini - di tempat pertama). Pada langkah ini, ini adalah angka pertama dalam array, yaitu 3. Langkah kedua. Kita tidak melihat nomor 2, itu sudah ada di subarray yang diurutkan. Kita mulai mencari minimumnya, mulai dari elemen kedua yaitu 5. Kita pastikan 3 adalah minimum di antara yang tidak disortir, 5 adalah yang pertama di antara yang tidak disortir. Kami menukarnya dan menambahkan 3 ke subarray yang diurutkan. Pada langkah ketiga , kita melihat bahwa angka terkecil pada subarray yang tidak diurutkan adalah 4. Kita mengubahnya dengan angka pertama di antara subarray yang tidak diurutkan - 5. Pada langkah keempat, kita menemukan bahwa dalam array yang tidak diurutkan, angka terkecil adalah 5. Kami mengubahnya dari 6 dan menambahkannya ke subarray yang diurutkan. Jika hanya satu angka yang tersisa di antara angka yang tidak diurutkan (yang terbesar), ini berarti seluruh larik telah terurut! Seperti inilah implementasi array dalam kode. Cobalah membuatnya sendiri. Dalam kasus terbaik dan terburuk, untuk menemukan elemen minimum yang tidak diurutkan, kita harus membandingkan setiap elemen dengan setiap elemen array yang tidak diurutkan, dan kita akan melakukannya pada setiap iterasi. Namun kita tidak perlu melihat keseluruhan daftar, melainkan hanya bagian yang belum disortir saja. Apakah ini mengubah kecepatan algoritma? Pada langkah pertama, untuk array yang terdiri dari 5 elemen, kita membuat 4 perbandingan, pada langkah kedua - 3, pada langkah ketiga - 2. Untuk mendapatkan jumlah perbandingan, kita perlu menjumlahkan semua angka ini. Kami mendapatkan jumlah Jadi, kecepatan yang diharapkan dari algoritma dalam kasus terbaik dan terburuk adalah Θ(n ² ). Bukan algoritma yang paling efisien! Namun, untuk tujuan pendidikan dan kumpulan data kecil, hal ini cukup dapat diterapkan.

Sortir gelembung

Algoritma bubble sort adalah salah satu yang paling sederhana. Kami menelusuri seluruh array dan membandingkan 2 elemen yang berdekatan. Jika urutannya salah, kami menukarnya. Pada lintasan pertama, elemen terkecil akan muncul (“float”) di akhir (jika kita mengurutkan dalam urutan menurun). Ulangi langkah pertama jika setidaknya satu pertukaran telah diselesaikan pada langkah sebelumnya. Mari kita urutkan arraynya. Langkah 1: telusuri array. Algoritme dimulai dengan dua elemen pertama, 8 dan 6, dan memeriksa apakah urutannya benar. 8 > 6, jadi kita tukar. Selanjutnya kita lihat elemen kedua dan ketiga, sekarang menjadi 8 dan 4. Untuk alasan yang sama, kita menukarnya. Untuk ketiga kalinya kita membandingkan 8 dan 2. Total kita melakukan tiga pertukaran (8, 6), (8, 4), (8, 2). Nilai 8 "melayang" ke akhir daftar pada posisi yang benar. Langkah 2: tukar (6,4) dan (6,2). 6 sekarang berada di posisi kedua dari belakang, dan tidak perlu membandingkannya dengan “ekor” daftar yang sudah diurutkan. Langkah 3: tukar 4 dan 2. Keempatnya “melayang” ke tempat yang seharusnya. Langkah 4: kita menelusuri array, tetapi tidak ada yang perlu diubah. Ini menandakan bahwa array telah terurut sepenuhnya. Dan ini adalah kode algoritmanya. Coba terapkan di C! Pengurutan gelembung membutuhkan waktu O(n ² ) dalam kasus terburuk (semua angka salah), karena kita perlu mengambil n langkah pada setiap iterasi, yang juga terdapat n. Faktanya, seperti pada algoritma pengurutan seleksi, waktunya akan lebih singkat (n ² /2 – n/2), namun hal ini dapat diabaikan. Dalam kasus terbaik (jika semua elemen sudah ada), kita dapat melakukannya dalam n langkah, yaitu Ω(n), karena kita hanya perlu mengulangi array satu kali dan memastikan bahwa semua elemen berada di tempatnya (yaitu bahkan n-1 elemen).

Sortir penyisipan

Ide utama dari algoritma ini adalah membagi array kita menjadi dua bagian, terurut dan tidak terurut. Pada setiap langkah algoritma, bilangan berpindah dari bagian yang tidak diurutkan ke bagian yang diurutkan. Mari kita lihat cara kerja penyisipan penyortiran menggunakan contoh di bawah ini. Sebelum kita mulai, semua elemen dianggap belum disortir. Langkah 1: Ambil nilai pertama yang belum disortir (3) dan masukkan ke dalam subarray yang telah diurutkan. Pada langkah ini, seluruh subarray yang diurutkan, awal dan akhirnya akan menjadi tiga ini. Langkah 2: Karena 3 > 5, kita akan memasukkan 5 ke dalam subarray yang telah diurutkan di sebelah kanan 3. Langkah 3: Sekarang kita akan memasukkan angka 2 ke dalam array yang telah diurutkan. Kita bandingkan 2 dengan nilai dari kanan ke kiri untuk menemukan posisi yang benar. Karena 2 < 5 dan 2 < 3 dan kita telah mencapai awal subarray yang diurutkan. Oleh karena itu, kita harus menyisipkan 2 di sebelah kiri 3. Untuk melakukan ini, pindahkan 3 dan 5 ke kanan sehingga ada ruang untuk 2 dan masukkan di awal array. Langkah 4. Kita beruntung: 6 > 5, jadi kita bisa memasukkan angka itu tepat setelah angka 5. Langkah 5. 4 < 6 dan 4 < 5, tetapi 4 > 3. Oleh karena itu, kita tahu bahwa 4 harus disisipkan ke di sebelah kanan 3. Sekali lagi, kita dipaksa untuk memindahkan 5 dan 6 ke kanan untuk membuat celah untuk 4. Selesai! Algoritma Umum: Ambil setiap elemen n yang tidak diurutkan dan bandingkan dengan nilai dalam subarray yang diurutkan dari kanan ke kiri hingga kita menemukan posisi yang cocok untuk n (yaitu, saat kita menemukan bilangan pertama yang kurang dari n) . Kemudian kita menggeser semua elemen yang diurutkan di sebelah kanan nomor ini ke kanan untuk memberi ruang bagi n kita, dan kita menyisipkannya di sana, sehingga memperluas bagian array yang diurutkan. Untuk setiap elemen yang tidak disortir n Anda memerlukan:

2. Tentukan lokasi di bagian array yang diurutkan di mana n harus disisipkan
3. Geser elemen yang diurutkan ke kanan untuk membuat celah untuk n
4. Masukkan n ke dalam celah yang dihasilkan di bagian array yang diurutkan.

Dan ini kodenya! Kami merekomendasikan untuk menulis program penyortiran versi Anda sendiri.

Kecepatan asimtotik dari algoritma

Dalam kasus terburuk, kita akan membuat satu perbandingan dengan elemen kedua, dua perbandingan dengan elemen ketiga, dan seterusnya. Jadi kecepatan kita adalah O(n ² ). Paling banter, kita akan bekerja dengan array yang sudah diurutkan. Bagian yang diurutkan, yang kita buat dari kiri ke kanan tanpa penyisipan dan pergerakan elemen, akan memakan waktu Ω(n).

Gabungkan semacam

Algoritme ini bersifat rekursif; ia memecah satu masalah pengurutan besar menjadi beberapa subtugas, yang pelaksanaannya membuatnya lebih dekat dengan penyelesaian masalah besar aslinya. Ide utamanya adalah untuk membagi array yang tidak disortir menjadi dua bagian dan mengurutkan masing-masing bagian secara rekursif. Katakanlah kita memiliki n elemen untuk diurutkan. Jika n < 2, kita selesaikan penyortiran, jika tidak, kita urutkan bagian kiri dan kanan array secara terpisah, lalu gabungkan keduanya. Mari kita urutkan arraynya, bagilah menjadi dua bagian, dan terus bagi hingga kita mendapatkan subarray berukuran 1, yang jelas sudah terurut. Dua subarray yang diurutkan dapat digabungkan dalam waktu O(n) menggunakan algoritma sederhana: hapus angka yang lebih kecil di awal setiap subarray dan masukkan ke dalam array yang digabungkan. Ulangi sampai semua elemen hilang. Pengurutan gabungan membutuhkan waktu O(nlog n) untuk semua kasus. Saat kita membagi array menjadi dua bagian di setiap level rekursi, kita mendapatkan log n. Kemudian, menggabungkan subarray hanya membutuhkan n perbandingan. Oleh karena itu O(nlog n). Kasus terbaik dan terburuk untuk pengurutan gabungan adalah sama, waktu berjalan yang diharapkan dari algoritma = Θ(nlog n). Algoritma ini adalah yang paling efektif di antara algoritma yang dipertimbangkan.