Clever Geek Handbook

Sortir seleksi

Halo. Saya menulis artikel ini khusus untuk peluncuran kursus "Algoritma dan Struktur Data" dari OTUS.







pengantar



Menyortir sebuah array adalah salah satu masalah serius pertama yang dipelajari dalam kursus klasik "Algoritma dan Struktur Data" dari disiplin ilmu komputer. Dalam hal ini, tugas menulis macam-macam dan pertanyaan yang sesuai sering ditemui dalam wawancara sebagai pengembang magang atau junior.



Perumusan masalah



Secara tradisional, ada baiknya memulai presentasi solusi untuk masalah dengan pernyataannya. Biasanya tugas menyortir melibatkan memesan beberapa bilangan bulat dalam urutan naik. Tetapi pada kenyataannya, ini agak terlalu disederhanakan. Algoritme yang dijelaskan dalam bagian ini dapat digunakan untuk memesan array dari objek apa pun di mana hubungan pemesanan dibuat (yaitu, untuk dua elemen yang dapat kita katakan: yang pertama lebih besar dari yang kedua, yang kedua lebih besar dari yang pertama, atau mereka sama). Anda dapat mengurutkannya dalam urutan naik dan turun. Kami akan menggunakan penyederhanaan standar.



Sortir seleksi



Salah satu jenis yang paling sederhana adalah jenis pilihan.



Deskripsi Algoritma



Menyortir array dengan pemilihan dilakukan sebagai berikut: array dibagi menjadi dua bagian. Satu bagian disebut diurutkan dan yang lainnya tidak disortir. Algoritma ini mengasumsikan melintasi seluruh array sehingga panjang bagian yang diurutkan menjadi sama dengan panjang seluruh array. Dalam setiap iterasi, kami menemukan minimum di bagian array yang tidak disortir dan menukar minimum ini dengan elemen pertama dari bagian array yang tidak disortir. Kemudian kita menambah panjang bagian array yang diurutkan berdasarkan satu. Contoh satu iterasi disajikan di bawah ini:

1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8



Penerapan



Saya sarankan melihat implementasi algoritma ini di C: 



void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        // 
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}


Analisis



Saya mengusulkan untuk menganalisis algoritma ini. Tubuh loop dalam itu sendiri membutuhkan O (1), yaitu, itu tidak tergantung pada ukuran array yang diurutkan. Ini berarti bahwa untuk memahami asimtotik dari algoritma, perlu untuk menghitung berapa kali tubuh ini dieksekusi. Pada iterasi pertama dari loop luar, ada (n - 1) iterasi dari loop dalam. Pada iterasi kedua loop luar - (n - 2) iterasi loop dalam. Melanjutkan alasan ini lebih jauh, kita sampai pada hal berikut:

T(n)=(n−1)∗O(1)+(n−2)∗O(1)+...+O(1)=O((n−1)+(n−2)+...+1)=O((n−1)∗n/2)=O(n2)





Dalam proses perhitungan, pertama - tama kita menggunakan properti notasi O, dan kemudian rumus untuk menghitung jumlah dari perkembangan aritmatika.



Untuk pemesanan, perlu juga memperkirakan memori tambahan yang diperlukan untuk menjalankan algoritma. Semuanya jauh lebih sederhana di sini: kami mengalokasikan memori hanya untuk loop counters dan variabel - buffer, yang memungkinkan swapping 2 elemen array. Karena itu:

M(n)=O(1)





Sebagai hasil dari analisis, kami sampai pada kesimpulan bahwa kompleksitas waktu dari algoritma tergantung pada ukuran array input secara kuadratik. Oleh karena itu, penyortiran ini milik kelas macam kuadrat . Hasil analisis tidak tergantung pada konten array: itu benar terbaik, terburuk, dan rata-rata.



Penting juga untuk dicatat bahwa pemilihan sortir kuat dalam implementasi ini . Biarkan saya mengingatkan Anda bahwa penyortiran disebut stabil.jika urutan elemen yang sama tidak berubah selama eksekusi. Properti ini tidak terlalu penting untuk tugas pendidikan seperti mengurutkan array angka, tetapi jika kami mengurutkan beberapa objek yang lebih kompleks dengan relasi pemesanan yang mapan, mungkin penting. Kita dapat mempertimbangkan contoh serupa kapan kita berbicara tentang penyortiran radix.



Jenis seleksi dua sisi



Optimalisasi algoritma yang diterapkan di atas mungkin menarik: saat berjalan melalui bagian array yang tidak disortir, Anda dapat mencari maksimum secara paralel dengan elemen minimum. Dengan demikian, setelah iterasi, Anda dapat mengurangi bagian array yang tidak disortir bukan dengan satu, tetapi dua. Algoritme tidak meningkat secara asimptotik, namun demikian, kecepatan eksekusi mungkin sedikit meningkat, jumlah perbandingan juga berlipat ganda.



Jenis seleksi rekursif



Sebagai latihan, Anda dapat mencoba menulis algoritma yang tidak menggunakan loop, tetapi menggunakan rekursi. Di java mungkin terlihat seperti ini: 



public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}


Ringkasan



Kami melihat salah satu dari jenis kuadratik: jenis seleksi, melihat implementasi yang stabil menggunakan loop, rekursi, membahas optimasi algoritma dengan pengurangan dua arah dari bagian array yang tidak disortir. Penyortiran murni bersifat mendidik dan belum banyak diterapkan dalam praktik.





Jika Anda ingin mempelajari lebih lanjut tentang kursus ini, saya mengundang semua orang ke webinar gratis, yang akan diadakan pada 10 Juli .





More articles:


All Articles