Perbandingan algoritma pengurutan pertukaran

Artikel ini membahas berbagai opsi untuk menyortir pertukaran, dan juga menjelaskan aplikasi grafis sederhana ( processing.js ) dengan contoh-contoh macam.

Sebelum membaca, saya sarankan Anda membaca artikel oleh pengguna valemak :

→ Penyortiran pertukaran
→ Bubble Sort dan All-All-All
→ Semacam konyol dan beberapa lainnya lebih pintar

Sortir Bubble

Opsi paling sederhana adalah beralih dari array dari elemen pertama ke elemen tetangga yang bertukar (jika perlu).

→ Periksa di sini


Untuk memindahkan slider, Anda perlu mengklik tombol abu-abu di sudut kiri bawah.
Ketika Anda mengklik tombol, gerakkan slider satu langkah ke kanan

slider++; 

Selanjutnya, kita periksa: sudahkah kita mencapai akhir array (lalu lompat ke awal), lalu membandingkan (menukar) elemen-elemen tetangga


Processing.js menggunakan struktur data Java, kemudian kode tersebut diterjemahkan ke dalam javascript ( tautan ), sehingga deklarasi array instance dari kelas Module, yang bertanggung jawab untuk merender elemen dan menginisialisasi instance, terjadi seperti ini

Fungsi utama menggambar void draw () adalah loop tak terbatas di mana instance kelas diurutkan

 for (Module mod : mods) { mod.display(); } 

Tambahkan fungsi randFoo () , yang mengembalikan nilai acak. Untuk memastikan bahwa nilai-nilai tidak diulang, kami akan menambahkannya ke ArrayLis t dalam daftar listRand , dan dalam fungsi randFoo () , periksa apakah nomor acak baru ada di daftar listRand

 int randFoo(){ newRand = int(random(1,11)); if(!listRand.contains(newRand) ) listRand.add(newRand ); else newRand=randFoo(); return newRand; } 

→ Periksa di sini

Sortir Pixel

Pixel sorting (di sini) adalah implementasi dari bubble sorting.
Kami akan menggeser piksel yang lebih hangat / lebih terang ke satu sisi, dan yang lebih gelap / lebih dingin ke yang lain

 void draw(){ while (i <= height) { c=get(i,j); //    cTemp=c; //      i++; //     c=get(i,j); //     if(cTemp>c) { //   fill(c); //    rect(i-1,j,1,1); fill(cTemp); rect(i,j,1,1); } } if(mousePressed) { if(j>=width) j=0; } //      if(i >= height) {j++; i=0;} } 

→ Periksa di sini
Untuk mulai menyortir, klik pada gambar dan tahan tombol.
Anda dapat membaca lebih lanjut tentang jenis pixel di sini .
Video tentang penyortiran piksel pada saluran resmi The Coding Train di sini

Pembatas dan bendera

Anda dapat mengurangi jumlah iterasi jika Anda tidak mengulangi item yang sudah diurutkan. Untuk melakukan ini, tambahkan limiter ke ujung array, yang akan bergeser ke awal array setelah setiap iterasi

 if(slider>=limiter) { slider=1; limiter--; if(limiter<1) limiter=1; } 

→ Periksa di sini

Cara lain untuk mengurangi jumlah payudara dapat ditemukan di artikel Bubble Sort (Wikipedia). Jika selama bagian dari array kita tidak pernah mengganti elemen tetangga, array diurutkan dan siklus dapat diselesaikan (kondisi Iverson ).

Tambahkan bendera bendera , yang dimunculkan ketika kita bertemu beberapa elemen yang perlu dipertukarkan. Jika bendera dinaikkan, beralih lagi ke array. Jika tidak, akhiri siklus. Keadaan bendera ditampilkan di konsol.



→ Periksa di sini

Jika Anda meletakkan pembatas di sebelah kiri dan menggunakan elemen dengan pembatas sebagai referensi / minimum, kami mendapatkan pengurutan berdasarkan pilihan.

Tambahkan variabel min di mana nilai minimum akan dimuat. Misalkan pada awalnya elemen paling kiri minimal: selama pass pertama array, jika sebuah elemen kurang dari minimum, maka kita menyimpan elemen ini sendiri dalam variabel min

 if(mods[slider-1].rectHight < min){ min=mods[slider-1].rectHight; } 

lalu tukar elemen pertama dan minimum

 if (mods[limiterL-1].rectHight>min) { vTemp= mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[slider-1].rectHight; mods[slider-1].rectHight=vTemp; } 

Jika slider mencapai tepi kanan array, maka limiter bergerak satu langkah ke kanan, dan slider bergerak ke limiter

 if(slider==moduleSize){ if(limiterL<moduleSize) limiterL++; min=mods[limiterL-1].rectHight; incPaddle=limiterL-1; } 

→ Periksa di sini
Jumlah tindakan dapat dikurangi jika pada awal pencarian kami membandingkan (menukar) elemen saat ini dan elemen paling kanan dari array

 if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight) { vTemp=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight; mods[moduleSize-1].rectHight=vTemp; } 

Maka Anda tidak dapat memeriksa elemen paling kanan dari array

 //if(slider==moduleSize){ if(slider==moduleSize-1){ //if(limiterL<moduleSize) limiterL++; limiterL++; min=mods[limiterL-1].rectHight; slider=limiterL-1; } // slider++; if(slider<moduleSize) slider++; 

→ Periksa di sini

Di sini Anda dapat menambahkan pengurutan bagian kanan array dalam urutan menurun dengan menambahkan elemen maksimum maks - kami mendapatkan pengocok berdasarkan pilihan. Lihat bagian menyortir shaker di akhir artikel.

Sortir cepat

Mekanisme pemilihan elemen pendukung juga digunakan dalam penyortiran cepat. Algoritma ini melibatkan pemilihan elemen referensi awal dengan mana semua elemen array dibandingkan. Waktu eksekusi algoritma tergantung pada pilihan elemen awal. Dalam gif di atas, elemen awal adalah nomor 3 . Anda dapat membaca lebih lanjut tentang memilih elemen dukungan awal di artikel (Wikipedia).
Video tentang penyortiran cepat tersedia di saluran youtube resmi dari bahasa pemrosesan dan p5.js. Di sini Anda dapat melihat visualisasi algoritma.
Jika elemen pertama adalah dasar, maka Anda dapat memasukkan elemen lebih kecil dari yang dasar di depannya, maka array akan dibagi menjadi dua bagian, elemen di sebelah kiri akan lebih kecil dari dasar, di sebelah kanan - lebih. Untuk metode semacam itu, lihat bagian menyortir berdasarkan sisipan di bawah ini.

Sortir Kurcaci

Pada dasarnya, gnome melihat pot taman berikutnya dan sebelumnya: jika mereka berada dalam urutan yang benar, ia melangkah maju satu pot, jika tidak ia menukar mereka dan mundur satu pot.

Setelah menaikkan flag, simpan koordinat slider di variabel limiterR dan kembalikan slider ke awal array dalam langkah-langkah

 slider--; 

Setelah di awal array, reset flag dan letakkan slider di sel dengan koordinat yang kita simpan di variabel limiterR

 if(slider==0){ flag=false; slider=limiterR; } 

→ Periksa di sini

Dengan mengubah algoritma ini, kita mendapatkan " pengurutan berdasarkan sisipan ."
Dalam mengurutkan berdasarkan sisipan, elemen referensi / minimum dipilih, kemudian di bagian array yang tidak disortir, elemen dipilih, lebih kecil dari referensi dan dimasukkan sebelum referensi

Mari kita memiliki tempat pertukaran elemen minimal dengan yang sebelumnya, hingga yang referensi, dan seterusnya. dimasukkan di depan referensi.
Tambahkan sebuah kondisi

 if(slider==limiterR-1 && mods[slider-1].rectHight<mods[limiterR-1].rectHight){ flag=false; slider=limiterR; } 

→ Periksa di sini


Penyortiran penyisipan "Cepat"

Dalam algoritma ini, array dibagi menjadi dua bagian oleh elemen pendukung.
Biarkan elemen pertama menjadi referensi: bandingkan, mulai dari yang kedua, elemen array dengan referensi, jika elemen lebih kecil dari referensi

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight) 

masukkan elemen yang ditemukan sebelum referensi

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight){ flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; } 

Jika bendera dinaikkan, gerakkan penggeser ke kiri dalam beberapa langkah hingga kami memenuhi elemen dukungan

 if(flag){ slider--; if(slider<pivot){ flag=false; //   pivot++; slider=pivot; } } 

T.O. array dibagi menjadi dua bagian, di sebelah kiri - elemen lebih kecil dari referensi, di sebelah kanan - lebih

→ Periksa di sini

Jika, setelah setiap enumerasi, koordinat elemen pendukung disimpan dalam ext. pivotsArr array, maka ketika elemen referensi mencapai tepi kanan, kita mendapatkan array yang diurutkan berdasarkan level / langkah. Elemen di setiap level selanjutnya akan lebih besar dari elemen di level sebelumnya. Batas-batas level akan dimuat dalam add. array pivotsArr
Setiap kali Anda mengklik tombol, kami akan menampilkan array pivotsArr ke konsol

 for(int i=0;i<pivotsArr.length;i++){ print(" "); print(pivotsArr[i]); print(" "); } 

Tambahkan fungsi acak randFoo () ke akhir program.

→ Periksa di sini

Sekarang Anda perlu mengurutkan elemen-elemen dari setiap level secara terpisah (hanya tinggal menambahkan kondisi untuk mengakhiri siklus)

→ Periksa di sini
Penyortiran ini dapat digambarkan sebagai penyortiran berdasarkan level.
, karena setelah setiap enumerasi, data numerik disusun dalam level, jumlah setiap level berikutnya melebihi angka pada yang sebelumnya.

Penyortiran ganjil

Kami akan memindahkan slider dengan dua langkah, membandingkan elemen-elemen tetangga

 slider=slider+2; 

T.O. kita membandingkan elemen 0 dan 1, 2 dan 3, 4 dan 5, 6 dan 7, dll.
Jika slider mencapai tepi array, maka biarkan limiter bergerak satu langkah ke kiri, dan slider bergerak ke awal array.
Selanjutnya, kita membandingkan elemen 1 dan 2, 3 dan 4, 5 dan 6, 7 dan 8, dll.
Setelah mencapai pembatas, kami menggesernya satu langkah ke kanan, meletakkan slider di awal array.

→ Periksa di sini

Urutkan sikat rambut

Biarkan slider berada di awal array dan pembatas kanan di akhir. Bandingkan elemen (tukar). Kami memindahkan limiter satu langkah ke kiri dan menyimpan indeksnya dalam variabel limiterStore

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

Pindahkan slider dengan berhenti ke ujung array dalam langkah-langkah

 if(limiter!=moduleSize) { //  limiter     limiter++; slider++; } 

Setelah mencapai ujung array sebagai limiter, letakkan slider di awal array, dan masukkan limiter di limiterStore-1

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

→ Periksa di sini

Semacam pengocok

Tambahkan limiter kiri limiterL ke awal array.
Biarkan bendera bendera naik ketika slider mencapai limiter kanan limiterR , lalu limiter bergerak satu langkah ke kiri. Selanjutnya, ketika bendera dinaikkan, slider bergerak mundur ke limiter kiri limiterL - limiter bergerak satu langkah ke kanan - slider bergerak bertahap ke kanan


→ Periksa di sini

Shaker disortir berdasarkan pilihan
Tambahkan ke semacam gelembung dengan pembatas kanan pembatas kiri. Pada setiap pergeseran slider ke kanan, kami memeriksa (swap), yang lebih besar - elemen saat ini atau pembatas

 if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=vTemp; } 

Ketika slider mencapai limiter limiterR kanan, limiter kanan bergerak satu langkah ke kiri, limiter kiri bergerak satu langkah ke kanan, slider kembali ke limiter kiri

 if(slider>=limiterR){ limiterL++; slider=limiterL; limiterR--; } 

→ Periksa di sini

PS Di sinilah aplikasi dijelaskan yang membuat mempelajari algoritma dan struktur data jauh lebih menarik .
Visualisasi lain dari sejumlah algoritma dan struktur data.
Artikel ini menyebutkan situs lain tempat Anda dapat melihat bagaimana data diurutkan berdasarkan algoritma yang berbeda.
Artikel ini memberikan penilaian tentang kompleksitas penyortiran gelembung.
Lebih lanjut tentang penilaian kompleksitas dapat dibaca di sini , di sini , di sini , di sini .