Urutan Penyisipan vs. Urutan Seleksi

Saya mencoba untuk memahami perbedaan antara Insertion Sort dan Selection Sort.

Keduanya tampaknya memiliki dua komponen: daftar yang tidak diurutkan dan daftar yang diurutkan. Mereka berdua tampaknya mengambil satu elemen dari daftar yang tidak diurutkan dan memasukkannya ke dalam daftar yang diurutkan di tempat yang tepat. Saya telah melihat beberapa situs / buku yang mengatakan bahwa jenis seleksi melakukan ini dengan menukar satu per satu sementara jenis penyisipan hanya menemukan tempat yang tepat dan memasukkannya. Namun, saya telah melihat artikel lain mengatakan sesuatu, mengatakan bahwa jenis penyisipan juga bertukar. Akibatnya, saya bingung. Apakah ada sumber kanonik?

Urutan Pilihan:

Diberikan daftar, ambil elemen saat ini dan tukarkan dengan elemen terkecil di sisi kanan elemen saat ini.

Sortir Penyisipan:

Diberikan daftar, ambil elemen saat ini dan sisipkan di posisi yang sesuai dari daftar, sesuaikan daftar setiap kali Anda menyisipkan. Ini mirip dengan menyusun kartu dalam permainan Kartu.

Kompleksitas Waktu dari urutan pemilihan selalu n(n - 1)/2, sedangkan jenis penyisipan memiliki kompleksitas waktu yang lebih baik sebagai kompleksitas kasus terburuknya n(n - 1)/2. Biasanya akan membutuhkan perbandingan yang lebih rendah atau sama n(n - 1)/2.

Sumber: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

Baik pengurutan penyisipan dan pengurutan pilihan memiliki loop luar (di atas setiap indeks), dan loop dalam (di atas subset indeks). Setiap lintasan loop dalam memperluas wilayah yang diurutkan dengan satu elemen, dengan mengorbankan wilayah yang tidak diurutkan, hingga kehabisan elemen yang tidak diurutkan.

Perbedaannya terletak pada fungsi loop dalam:

• Dalam seleksi sort, loop dalam berada di atas unsorted elemen yang tidak . Setiap lulus memilih satu elemen, dan memindahkannya ke lokasi akhirnya (di ujung wilayah yang diurutkan saat ini).

• Dalam semacam penyisipan, setiap lintasan loop dalam melakukan iterasi atas elemen yang diurutkan . Elemen yang diurutkan dipindahkan hingga loop menemukan tempat yang tepat untuk menyisipkan elemen yang tidak diurutkan berikutnya.

Jadi, dalam sortir pilihan, elemen yang diurutkan ditemukan dalam urutan keluaran, dan tetap tinggal setelah ditemukan. Sebaliknya, dalam penyisipan sort, unsorted elemen yang tidak tetap ada hingga dikonsumsi dalam urutan masukan, sementara elemen dari wilayah yang diurutkan terus dipindahkan.

Sejauh menyangkut swapping: selection sort melakukan satu swap per lintasan loop dalam. Jenis penyisipan biasanya menyimpan elemen yang akan disisipkan seperti temp sebelum loop dalam, menyisakan ruang untuk loop dalam untuk menggeser elemen yang diurutkan ke atas satu, lalu menyalin tempke titik penyisipan setelahnya.

PILIHAN SELEKSI
Asumsikan bahwa ada deretan angka yang ditulis dengan gaya tertentu / acak dan katakanlah kita harus menyusunnya dalam urutan yang meningkat .. jadi, ambil satu nomor pada satu waktu dan gantikan dengan no terkecil. tersedia dalam daftar. dengan melakukan langkah ini pada akhirnya kita akan mendapatkan hasil yang diinginkan.

SORT INSERTION
Mempertahankan asumsi yang sama tetapi satu-satunya perbedaan adalah bahwa kali ini kami memilih satu nomor pada satu waktu dan memasukkannya ke bagian yang dipilah, yang mengurangi perbandingan dan karenanya lebih efisien.

Mungkin saja kebingungannya adalah karena Anda membandingkan deskripsi pengurutan daftar tertaut dengan deskripsi pengurutan array . Tapi saya tidak bisa yakin, karena Anda tidak mengutip sumber Anda.

Cara termudah untuk memahami algoritme pengurutan adalah dengan mendapatkan deskripsi mendetail tentang algoritme (bukan hal yang tidak jelas seperti "jenis ini menggunakan swap. Di suatu tempat. Saya tidak mengatakan di mana"), dapatkan beberapa kartu remi (5-10 sudah cukup untuk algoritma pengurutan sederhana), dan menjalankan algoritma dengan tangan.

Sortir pilihan: memindai data yang tidak disortir untuk mencari elemen terkecil yang tersisa, lalu menukarnya ke posisi segera setelah data yang diurutkan. Ulangi sampai selesai. Jika mengurutkan daftar, Anda tidak perlu menukar elemen terkecil ke posisinya, Anda dapat menghapus node daftar dari posisi lama dan menyisipkannya di posisi baru.

Jenis penyisipan: ambil elemen segera setelah data yang diurutkan, pindai melalui data yang diurutkan untuk menemukan tempat untuk meletakkannya, dan meletakkannya di sana. Ulangi sampai selesai.

Jenis penyisipan dapat menggunakan swap selama fase "pindai", tetapi tidak harus dan itu bukan cara yang paling efisien kecuali Anda mengurutkan larik dari tipe data yang: (a) tidak dapat dipindahkan, hanya disalin atau ditukar; dan (b) lebih mahal untuk disalin daripada ditukar. Jika penyisipan semacam memang menggunakan swap, cara kerjanya adalah Anda secara bersamaan mencari tempat dan meletakkan elemen baru di sana, dengan berulang kali menukar elemen baru dengan elemen tepat sebelumnya, selama elemen sebelumnya lebih besar dari Itu. Setelah Anda mencapai elemen yang tidak lebih besar, Anda telah menemukan lokasi yang benar dan Anda beralih ke elemen baru berikutnya.

Logika untuk kedua algoritma ini sangat mirip. Keduanya memiliki sub-larik yang diurutkan sebagian di awal larik. Satu-satunya perbedaan adalah bagaimana mereka mencari elemen berikutnya untuk dimasukkan ke dalam array yang diurutkan.

• Jenis penyisipan : menyisipkan elemen berikutnya pada posisi yang benar;

• Jenis pilihan : memilih elemen terkecil dan menukarnya dengan item saat ini;

Juga, Sortir Penyisipan stabil, berbeda dengan Sortir Pilihan .

Saya menerapkan keduanya dengan python, dan perlu dicatat betapa miripnya mereka:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Dengan sedikit perubahan dimungkinkan untuk membuat algoritma Sortir Seleksi.

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Singkatnya, saya berpikir bahwa sortir seleksi mencari nilai terkecil dalam array terlebih dahulu, dan kemudian melakukan swap sedangkan sortir penyisipan mengambil nilai dan membandingkannya dengan setiap nilai yang tersisa (di belakangnya). Jika nilainya lebih kecil, itu bertukar. Kemudian, nilai yang sama dibandingkan lagi dan jika lebih kecil dari nilai di belakangnya, nilai tersebut akan ditukar lagi. Saya harap itu masuk akal!

Pendeknya,

Urutan pilihan: Pilih elemen pertama dari larik yang tidak diurutkan dan bandingkan dengan elemen yang tidak diurutkan lainnya. Ini mirip dengan Bubble sort, tetapi alih-alih menukar setiap elemen yang lebih kecil, pertahankan indeks elemen terkecil diperbarui dan tukar di akhir setiap loop .

Insertion sort: Ini berlawanan dengan Selection sort dimana ia mengambil elemen pertama dari sub-larik yang tidak diurutkan dan membandingkannya dengan sub-larik yang diurutkan dan menyisipkan elemen terkecil di mana ditemukan dan menggeser semua elemen yang diurutkan dari kanan ke elemen tanpa urutan pertama.

Saya akan mencobanya lagi: pertimbangkan apa yang terjadi dalam kasus keberuntungan dari array yang hampir diurutkan.

Saat mengurutkan, larik dapat dianggap memiliki dua bagian: sisi kiri - diurutkan, sisi kanan - tidak diurutkan.

Sortir penyisipan - pilih elemen pertama yang tidak diurutkan dan coba temukan tempatnya di antara bagian yang sudah diurutkan. Karena Anda menelusuri dari kanan ke kiri, kemungkinan besar elemen yang diurutkan pertama yang Anda bandingkan (yang terbesar, paling kanan di bagian kiri) lebih kecil daripada elemen yang dipilih sehingga Anda dapat segera melanjutkan dengan elemen yang tidak diurutkan berikutnya.

Sortir pilihan - pilih elemen pertama yang tidak diurutkan dan coba temukan elemen terkecil dari seluruh bagian yang tidak diurutkan, dan tukar keduanya jika diinginkan. Masalahnya adalah, karena bagian kanan tidak disortir, Anda harus memikirkan setiap elemen setiap saat, karena Anda tidak mungkin memastikan apakah ada atau tidak elemen yang lebih kecil daripada yang dipilih.

Btw., Ini tepatnya yang ditingkatkan heapsort pada jenis pilihan - ia dapat menemukan elemen terkecil jauh lebih cepat karena heap .

Sortir Pilihan: Saat Anda mulai membuat sublist yang diurutkan, algoritme memastikan bahwa sublist yang diurutkan selalu diurutkan secara lengkap, tidak hanya dalam hal elemennya sendiri tetapi juga dalam hal array lengkap, yaitu sublist yang diurutkan dan tidak diurutkan. Dengan demikian, elemen terkecil baru yang pernah ditemukan dari sublist yang tidak diurutkan hanya akan ditambahkan di akhir sublist yang diurutkan.

Sortasi Penyisipan: Algoritme sekali lagi membagi array menjadi dua bagian, tetapi di sini elemen diambil dari bagian kedua dan disisipkan pada posisi yang benar ke bagian pertama. Hal ini tidak pernah menjamin bahwa bagian pertama diurutkan sesuai dengan larik lengkap, meskipun tentu saja di lintasan terakhir setiap elemen berada pada posisi pengurutan yang benar.

Kedua algoritma tersebut umumnya bekerja seperti ini

Langkah 1: ambil elemen tak disortir berikutnya dari daftar tak disortir

Langkah 2: letakkan di tempat yang tepat di daftar yang diurutkan.

Salah satu langkahnya adalah lebih mudah untuk satu algoritma dan sebaliknya.

Jenis penyisipan : Kami mengambil elemen pertama dari daftar yang tidak diurutkan, meletakkannya di daftar yang diurutkan, di suatu tempat . Kita tahu di mana harus mengambil elemen berikutnya (posisi pertama dalam daftar yang tidak disortir), tetapi membutuhkan kerja keras untuk menemukan di mana harus meletakkannya (di suatu tempat ). Langkah 1 itu mudah.

Jenis pilihan : Kami mengambil elemen di suatu tempat dari daftar yang tidak diurutkan, lalu meletakkannya di posisi terakhir dari daftar yang diurutkan. Kita perlu menemukan elemen berikutnya (kemungkinan besar tidak ada di posisi pertama daftar yang tidak diurutkan, melainkan di suatu tempat daftar yang tidak diurutkan ) lalu meletakkannya tepat di akhir daftar yang diurutkan. Langkah 2 itu mudah

Loop dalam dari penyisipan semacam melewati elemen yang telah diurutkan (berlawanan dengan jenis pilihan). Hal ini memungkinkannya untuk membatalkan loop dalam ketika posisi yang tepat ditemukan . Artinya, bahwa:

1. Loop dalam hanya akan melewati setengah dari elemennya dalam kasus rata-rata.
2. Loop dalam akan dibatalkan lebih cepat jika array hampir diurutkan.
3. Loop dalam akan segera dibatalkan jika array sudah diurutkan, membuat kompleksitas penyisipan linier dalam kasus ini.

Jenis seleksi harus selalu melalui semua elemen loop dalam. Itulah mengapa jenis penyisipan lebih disukai daripada jenis pemilihan. Namun, di sisi lain, pemilihan jenis melakukan lebih sedikit pertukaran elemen, yang mungkin lebih penting dalam beberapa kasus.

Pada dasarnya pengurutan penyisipan bekerja dengan membandingkan dua elemen sekaligus dan pengurutan seleksi memilih elemen minimum dari seluruh larik dan mengurutkannya.

Secara konseptual penyisipan sort terus mengurutkan sub list dengan membandingkan dua elemen hingga seluruh array diurutkan sementara seleksi sort memilih elemen minimum dan menukarnya ke posisi pertama elemen minimum kedua ke posisi kedua dan seterusnya.

Jenis penyisipan dapat ditampilkan sebagai:

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Urutan pilihan dapat ditampilkan sebagai:

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

Pilihan dari 2 algoritma pengurutan ini tergantung pada struktur data yang digunakan.

Saat Anda menggunakan array, gunakan selection sort (meskipun mengapa, saat Anda bisa menggunakan qsort?). Saat Anda menggunakan daftar tertaut, gunakan semacam penyisipan.

Hal ini karena:

• Traversal daftar tertaut lebih mahal daripada array.
• Penyisipan daftar tertaut jauh lebih murah daripada array.

Urutan penyisipan memasukkan nilai baru ke tengah segmen yang diurutkan. Karenanya, data perlu "didorong kembali". Namun, saat Anda menggunakan daftar tertaut, dengan memutar 2 petunjuk, Anda telah secara efektif mendorong kembali seluruh daftar. Dalam sebuah array, Anda harus melakukan n - i swap untuk mendorong kembali nilainya, yang bisa sangat mahal.

Sortir pilihan selalu ditambahkan di akhir, jadi tidak ada masalah ini saat menggunakan array. Karenanya, data tidak perlu "didorong kembali".

Penjelasan sederhananya bisa seperti di bawah ini:

Diberikan : Array atau daftar angka yang tidak diurutkan.

Pernyataan Masalah : Untuk mengurutkan daftar / larik angka dalam urutan menaik untuk memahami perbedaan antara Sortir Pilihan dan Urutan Penyisipan.

Sortir Penyisipan:Anda melihat daftarnya dari atas ke bawah untuk memudahkan pemahaman. Kami menganggap elemen pertama sebagai nilai minimum awal kami. Sekarang, idenya adalah kita melintasi setiap indeks dari daftar / larik itu secara linier untuk mengetahui apakah ada elemen lain pada indeks mana pun yang memiliki nilai lebih rendah dari nilai minimum awal. Jika kita menemukan nilai seperti itu, kita hanya menukar nilai pada indeksnya, misalkan 15 adalah nilai awal minimum pada indeks 1 dan selama traversal linier dari indeks, kita menemukan angka dengan nilai yang lebih rendah, katakanlah 7 pada indeks 9 Sekarang, nilai 7 ini pada indeks 9 ditukar dengan indeks 1 yang memiliki nilai 15. Traversal ini akan terus melakukan perbandingan dengan nilai indeks saat ini dengan indeks yang tersisa untuk ditukar dengan nilai yang lebih kecil. Ini berlanjut hingga indeks terakhir kedua dari daftar / larik,

Urutan Pilihan:Mari asumsikan bahwa elemen indeks pertama dari list / array diurutkan. Sekarang dari elemen di indeks kedua, kami membandingkannya dengan indeks sebelumnya untuk melihat apakah nilainya lebih kecil. Traversal dapat divisualisasikan menjadi dua bagian, diurutkan dan tidak diurutkan. Satu akan memvisualisasikan pemeriksaan perbandingan dari yang tidak disortir ke yang diurutkan untuk indeks tertentu dalam daftar / larik. Misalkan Anda memiliki nilai 19 pada indeks 1 dan nilai 10 pada indeks 3. Kami menganggap traversal dari yang tidak disortir ke yang diurutkan, yaitu dari kanan ke kiri. Jadi, katakanlah kita harus mengurutkan pada indeks 3. Kita melihat bahwa nilainya lebih rendah daripada indeks 1 jika dibandingkan dari kanan ke kiri. Setelah diidentifikasi, kita tinggal menempatkan angka 10 dari indeks 3 ini di tempat indeks 1 yang memiliki nilai 19. Nilai asli 19 pada indeks 1 bergeser satu tempat ke kanan.

Saya belum menambahkan kode apa pun karena pertanyaannya tampaknya tentang memahami konsep metode traversal.

Jenis penyisipan tidak menukar sesuatu. Meskipun menggunakan variabel temp, Inti dari penggunaan temp var adalah ketika kami menemukan nilai pada indeks lebih kecil dibandingkan dengan nilai indeks sebelumnya, kami menggeser nilai yang lebih besar ke tempat nilai yang lebih rendah indeks yang akan menulis sesuatu. Kemudian kami menggunakan temp var untuk diganti pada indeks sebelumnya. Contoh: 10, 20, 30, 50, 40. iterasi 1: 10, 20, 30, 50, 50. [temp = 40] iterasi 2: 10,20, 30, 40 (nilai temp), 50. Jadi, kita cukup masukkan nilai pada posisi yang diinginkan dari beberapa variabel.

Tetapi ketika kita mempertimbangkan pemilihan jenis, kita pertama-tama menemukan indeks memiliki nilai yang lebih rendah dan menukar nilai itu dengan nilai dari indeks pertama dan terus bertukar berulang kali sampai semua indeks tersortir. Ini persis sama dengan pertukaran tradisional dua angka. Contoh: 30, 20, 10, 40, 50. Iterasi 1: 10, 20, 30, 40, 50. Disini temp var digunakan secara eksklusif untuk swapping.

Jenis penyisipan melakukan lebih banyak pertukaran pilihan itu. Berikut ini contohnya:

Apa yang sama-sama mereka miliki adalah bahwa keduanya menggunakan partisi untuk membedakan antara bagian yang diurutkan dari larik dan yang tidak disortir.

Perbedaannya adalah, dengan selection sort, Anda dijamin bahwa bagian yang diurutkan dari larik tidak akan berubah saat menambahkan elemen ke partisi yang diurutkan.

Alasannya adalah, karena pemilihan mencari minimum dari set yang tidak diurutkan dan menambahkannya tepat setelah elemen terakhir dari set yang diurutkan, sehingga meningkatkan set yang diurutkan dengan 1.

Penyisipan di sisi lain, hanya peduli tentang elemen berikutnya yang ditemui, yang merupakan elemen pertama di bagian array yang tidak disortir. Ini akan mengambil elemen ini dan memasukkannya ke tempat yang tepat di set yang diurutkan.

Pengurutan penyisipan biasanya akan selalu menjadi kandidat yang lebih baik untuk larik yang hanya diurutkan sebagian karena Anda membuang-buang operasi untuk menemukan jumlah minimum.

Kesimpulan:

Sortir pilihan secara bertahap menambahkan elemen ke akhir dengan mencari elemen minimum di bagian yang tidak diurutkan.

Sortir penyisipan menyebarkan elemen pertama yang ditemukan di bagian yang tidak disortir ke mana saja di bagian yang diurutkan.

Meskipun Time Complexity dari seleksi sort dan insertion sort sama, yaitu n (n - 1) / 2. Jenis penyisipan kinerja rata-rata lebih baik. Diuji pada i5 cpu saya dengan 30000 bilangan bulat acak, urutan pemilihan rata-rata memakan waktu 1,5 detik, sedangkan jenis penyisipan rata-rata 0,6 detik.

Dalam istilah awam, (dan mungkin cara termudah untuk mencapai pemahaman masalah tingkat tinggi)

Jenis gelembung mirip dengan berdiri dalam barisan dan mencoba menyortir diri Anda berdasarkan ketinggian. Anda terus berpindah dengan orang di sebelah Anda sampai Anda berada di tempat yang tepat. Ini berlangsung dari kiri (atau kanan tergantung pada implementasinya) dan Anda terus beralih hingga semua orang tersortir.

Dalam pemilihan jenis, bagaimanapun, apa yang Anda lakukan mirip dengan mengatur kartu. Anda melihat kartu-kartu itu, mengambil yang terkecil, meletakkannya ke kiri, dan seterusnya.

seleksi -memilih item tertentu (terendah) dan menukarnya dengan elemen ke-i (tidak ada iterasi). (yaitu, pertama, kedua, ketiga .......) karenanya, buatlah daftar yang diurutkan pada satu sisi.

penyisipan- membandingkan pertama dengan kedua membandingkan ketiga dengan kedua & pertama membandingkan keempat dengan ketiga, kedua & pertama ......

tautan tempat semua penyortiran dibandingkan