Menambahkan elemen ke array yang diurutkan

Apa cara tercepat untuk melakukan ini (dari perspektif algoritmik, dan juga masalah praktis)?

Saya sedang memikirkan sesuatu seperti itu.

Saya bisa menambahkan ke akhir array dan kemudian menggunakan bubblesort karena memiliki kasus terbaik (array yang benar-benar diurutkan di awal) yang dekat dengan ini, dan memiliki waktu berjalan linier (dalam kasus terbaik).

Di sisi lain, jika saya tahu bahwa saya mulai dengan array yang diurutkan, saya bisa menggunakan pencarian biner untuk mengetahui titik penyisipan untuk elemen yang diberikan.

Firasat saya adalah bahwa cara kedua hampir optimal, tetapi ingin tahu apa yang ada di luar sana.

Bagaimana ini bisa dilakukan?

Kami menghitung jumlah elemen array yang dibaca dan ditulis. Untuk melakukan bubble sort, Anda perlu akses (penulisan awal hingga akhir, kemudian, dalam kasus terburuk, dua membaca dan dua menulis untuk melakukan n swap). Untuk melakukan pencarian biner, kita membutuhkan 2 log n + 2 n + 1 ( 2 log n untuk pencarian biner, kemudian, dalam kasus terburuk, 2 n untuk menggeser elemen array ke kanan, lalu 1 untuk menulis elemen array ke posisi yang tepat).$1 + 4n$$n$$2\log n + 2n + 1$$2\log n$$2n$

Jadi kedua metode memiliki kompleksitas yang sama untuk implementasi array, tetapi metode pencarian biner membutuhkan lebih sedikit akses array dalam jangka panjang ... tanpa gejala, setengah dari jumlah tersebut. Ada faktor-faktor lain yang berperan, secara alami.

Sebenarnya, Anda bisa menggunakan implementasi yang lebih baik dan hanya menghitung akses array aktual (bukan akses ke elemen yang akan dimasukkan). Anda bisa melakukan untuk bubble sort, dan log n + 2 n + 1 untuk pencarian biner ... jadi jika akses mendaftar / cache murah dan akses array mahal, mencari dari akhir dan pergeseran sepanjang jalan (cerdas semacam gelembung untuk penyisipan) bisa lebih baik, meskipun tidak asimtotik.$2n + 1$$\log n + 2n + 1$

Solusi yang lebih baik mungkin melibatkan penggunaan struktur data yang berbeda. Array memberi Anda O (1) akses (akses acak), tetapi penyisipan dan penghapusan mungkin dikenakan biaya. Tabel hash dapat memiliki penyisipan & penghapusan O (1), akan dikenakan biaya. Opsi lain termasuk BST dan heap, dll. Ini bisa bermanfaat mengingat kebutuhan penggunaan aplikasi Anda untuk penyisipan, penghapusan dan akses, dan memilih struktur yang lebih khusus.

Perhatikan juga bahwa jika Anda ingin menambahkan elemen ke array yang diurutkan dari elemen n , ide yang baik mungkin untuk mengurutkan item m secara efisien , kemudian menggabungkan dua array; juga, array yang diurutkan dapat dibangun secara efisien menggunakan misal heaps (heap sort).$m$$n$$m$

Jika Anda memiliki alasan untuk tidak menggunakan tumpukan, pertimbangkan untuk menggunakan Penyisipan Urutan, bukan Urutan Gelembung. Lebih baik bila Anda memiliki beberapa elemen yang tidak disortir.

Karena Anda menggunakan array, biayanya untuk menyisipkan item - ketika Anda menambahkan sesuatu ke tengah array, misalnya, Anda harus menggeser semua elemen setelahnya dengan satu sehingga array tetap diurutkan .$O(n)$

Cara tercepat untuk mencari tahu di mana harus meletakkan item seperti yang Anda sebutkan, pencarian biner, yaitu , jadi total kompleksitasnya adalah O ( n + lg n ) , yang ada di urutan O ( n ) .$O(\lg n)$$O(n + \lg n)$$O(n)$

$O(1)$

Lagi pula, saya tidak melihat alasan untuk mengeluarkan bubble untuk masalah ini.

Patrick87 menjelaskan ini dengan sangat baik. Tetapi satu optimasi tambahan yang bisa Anda lakukan adalah menggunakan sesuatu seperti buffer melingkar: Anda dapat memindahkan item tepat dari posisi elemen yang dimasukkan ke kanan, seperti biasa. Tetapi Anda juga dapat memindahkan item ke kiri dari posisi yang benar ke kiri. Untuk melakukan ini, Anda perlu memperlakukan array sebagai lingkaran, yaitu item terakhir tepat sebelum yang pertama dan itu juga mengharuskan Anda untuk menjaga indeks tempat item saat ini mulai.

Jika Anda melakukan ini, itu bisa berarti Anda membuat sekitar setengah lebih banyak akses array (dengan asumsi distribusi seragam dari indeks yang Anda masukkan). Dalam hal melakukan pencarian biner untuk menemukan posisi, itu sepele untuk memilih apakah akan bergeser ke kiri atau ke kanan. Dalam hal bubble sort, Anda perlu "menebak" dengan benar sebelum memulai. Tetapi melakukan itu sederhana: hanya membandingkan item yang dimasukkan dengan median array, yang dapat dilakukan dalam akses array tunggal.

Saya telah menggunakan algoritme penyisipan secara efektif untuk masalah ini. Pada suatu waktu kami memiliki masalah kinerja dengan objek tabel hash, saya menulis objek baru yang menggunakan pencarian biner sebagai gantinya yang meningkatkan kinerja secara signifikan. Untuk menjaga daftar diurutkan, itu akan melacak jumlah item yang ditambahkan sejak pengurutan terakhir (yaitu jumlah item yang tidak disortir,) ketika daftar perlu diurutkan karena permintaan pencarian, itu melakukan semacam penyisipan atau pengurutan cepat tergantung pada persentase item yang tidak disortir. Penggunaan jenis penyisipan adalah kunci dalam meningkatkan kinerja.