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).
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.
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?).
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 :)
0 Response to "Teknik Sorting Struktur Data "
Post a Comment