Teknik Sorting Struktur Data

Sorting

Sorting adalah kunci teori CS, tapi mudah lupa. Aku punya tips untuk meninjau algoritma, dan di sini adalah saya akan membahasnya:

Pengalaman tingkat tinggi
Beberapa algoritma (seleksi, bubble, heapsort) bekerja dengan menggerakkan elemen untuk posisi akhir mereka, satu per satu. Anda mengurutkan array berukuran N, menempatkan 1 item di tempat, dan terus menyortir sebuah array berukuran N - 1 (heapsort sedikit berbeda).

Beberapa algoritma (penyisipan, quicksort, penghitungan, radix) menempatkan item ke posisi sementara, dekat (r) ke posisi akhir mereka. Anda menelusuri ulang, item lebih dekat ke posisi akhir dengan setiap iterasi bergerak.

Salah satu teknik adalah untuk memulai dengan "daftar diurutkan" dari satu elemen, dan menggabungkan item disortir ke dalamnya, satu per satu.

Kompleksitas dan waktu berjalan

Faktor: kompleksitas algoritmik, biaya startup, kebutuhan ruang tambahan, penggunaan rekursi (panggilan funtion mahal dan makan ruang stack), perilaku terburuk, asumsi tentang input data, caching, dan perilaku pada yang sudah diurutkan data.

Perilaku terburuk penting untuk sistem real-time yang membutuhkan kinerja dijamin. Untuk keamanan, Anda ingin guratantee bahwa data dari penyerang tidak memiliki kemampuan untuk mengalahkan mesin Anda.

Caching

Caching - algoritma dengan perbandingan berurutan mengambil keuntungan dari lokalitas spasial dan prefetching, yang baik untuk caching.

Waktu Algoritmik vs real time

Waktu algoritmik vs real time - Algoritma sederhana mungkin O (N ^ 2), tetapi memiliki overhead rendah. Mereka bisa lebih cepat untuk menyortir data set kecil (<10 item). Satu kompromi adalah dengan menggunakan metode penyortiran yang berbeda tergantung pada ukuran masukan.

Perbandingan semacam ini tidak membuat asumsi pada data dan membandingkan semua elemen terhadap satu sama lain (mayoritas macam). O (N lg N) waktu adalah ideal "terburuk" skenario (jika itu masuk akal - O (N lg N) adalah hukuman terkecil yang dapat Anda harapkan dalam kasus terburuk). Heapsort memiliki perilaku ini.

O (N) waktu adalah mungkin jika kita membuat asumsi tentang data dan tidak perlu membandingkan elemen terhadap satu sama lain (yaitu, kita tahu data jatuh ke kisaran tertentu atau memiliki beberapa distribusi). O (N) jelas adalah memilah waktu minimum mungkin, karena kita harus memeriksa setiap elemen setidaknya sekali (bagaimana Anda dapat mengurutkan item Anda bahkan tidak memeriksa?).

Catatan

Asumsikan kita menyortir daftar atau array elemen NSetelah diurutkan, item yang lebih kecil berada di sebelah kiri (item pertama) dan item yang lebih besar di sebelah kanan (item terakhir)

Bubbble Sort [Terbaik: O (n), Terburuk: O (N ^ 2)]

Mulai di sebelah kiri, membandingkan item yang berdekatan dan menjaga "menggelegak" yang lebih besar ke kanan (itu di tempat akhir). Bubble sort N tersisa -1 item.
Meskipun "sederhana" Saya menemukan semacam gelembung trivial. Secara umum, macam mana Anda iterate mundur (penurunan beberapa indeks) yang kontra-intuitif bagi saya. Dengan gelembung-macam, baik Anda item gelembung "maju" (kiri ke kanan) dan memindahkan titik akhir mundur (menurun), atau item bubble "terbelakang" (kanan-ke-kiri) dan meningkatkan titik akhir kiri. Either way, beberapa indeks menurun.Anda juga perlu melacak endpoint berikutnya-untuk-terakhir, sehingga Anda tidak menukar dengan barang tidak punah.

Selection Sort [Terbaik / Terburuk: O (N ^ 2)]

Memindai semua item dan menemukan terkecil. Swap ke posisi sebagai item pertama. Ulangi semacam seleksi pada sisa N-1 item.

Saya menemukan ini yang paling intuitif dan mudah untuk menerapkan - Anda selalu iterate maju (i dari 0 sampai N-1), dan swap elemen terkecil (selalu i).

Insertion Sort [Terbaik: O (N), Terburuk: O (N ^ 2)]

Mulailah dengan daftar diurutkan dari 1 elemen di sebelah kiri, dan N-1 item disortir di sebelah kanan. Mengambil item disortir pertama (elemen 2 #) dan masukkan ke dalam daftar diurutkan, bergerak elemen yang diperlukan. Kami sekarang memiliki daftar diurutkan dari ukuran 2, dan N -2 elemen disortir. Ulangi untuk semua elemen.
Seperti bubble sort, saya menemukan kontra-intuitif ini karena Anda langkah "mundur"Ini adalah seperti semacam gelembung kecil untuk memindahkan barang-barang, kecuali bila Anda menemukan item lebih kecil dari Anda, Anda berhenti. Jika data reverse-diurutkan, setiap item harus melakukan perjalanan ke kepala daftar, dan ini menjadi bubble-sort.Ada berbagai cara untuk memindahkan item ke kiri - Anda dapat melakukan swap pada setiap iterasi, atau menyalin setiap item lebih tetangganya.

Quicksort [Terbaik: O (N lg N), rata-rata: O (N lg N), Terburuk: O (N ^ 2)]

Ada mungkin versi Quicksort, yang merupakan salah satu metode pengurutan yang paling populer karena kecepatan (O (N LGN) rata-rata, tapi O (N ^ 2) kasus terburuk).

Mungkin hanya itu yang dapat saya bagikan tentang Teknik Sorting Struktur Data, semoga teman-teman bisa membagikan ke yang lain, dan lebih semangat lagi dalam belajar struktur data. Sekian dan terima kasih :)