Pertanyaan Apa perbedaan antara memesan dan menyortir?


Tidak, itu bukan pertanyaan dari kelas, saya mempelajari pohon dan tumpukan (pohon biner sebagian disortir) oleh saya sendiri dan saya bertanya-tanya bagaimana benar mendefinisikan ini 2 properti / tindakan dalam kaitannya dengan struktur data generik.


21
2018-06-21 16:22


asal


Jawaban:


  • Sebuah "pemesanan"Pada dasarnya adalah seperangkat aturan yang menentukan item apa yang datang sebelum, atau setelah, apa item lain. IE: item order relatif akan muncul jika mereka diurutkan. Untuk koleksi yang menegakkan pemesanan, pemesanan itu umumnya ditentukan dalam hal operator perbandingan (khususnya <), antarmuka (a la Java's Comparable<T>), atau perbandingan callback dan / atau objek fungsi (seperti C ++ std::less).

    Ada juga koleksi yang dideskripsikan sebagai "koleksi pesanan". Penggunaan kata yang sedikit berbeda, tetapi arti yang terkait. Apa itu artinya adalah bahwa koleksi mewakili a urutan item, dan dengan demikian memiliki beberapa konsep inbuilt pesanan. (Kontras dengan, katakanlah, tabel hash. Anda menambahkan sesuatu ke tabel hash, Anda tidak tahu di mana itu akan muncul jika pernah Anda iterate atas isinya. Dengan koleksi teratur, Anda tahu.) Daftar, vektor, array, dll adalah koleksi pesanan klasik. Untuk contoh non-daftar, meskipun, "array" jenis PHP sebenarnya adalah "peta yang dipesan" - jenis kamus di mana urutan kunci dipertahankan. Kunci muncul dalam urutan di mana mereka pertama kali disisipkan (atau urutan terakhir Anda menempatkannya dengan ksort() atau sejenisnya) ketika Anda melakukan iterasi melalui array.

  • "Penyortiran"adalah proses untuk mengatur urutan item sesuai dengan pemesanan yang diberikan. Ini biasanya hanya dilakukan dengan koleksi yang dipesan ... karena tidak masuk akal untuk menempatkan satu item sebelum yang lain dalam penampung yang tidak memiliki konsep "sebelum" atau tidak akan membiarkan Anda mengatur ulang barang-barang di tempat pertama. (Struktur seperti set dan tumpukan dapat menggunakan pemesanan juga, dan menambahkan dan menghapus entri mengubah pohon yang mendasari berdasarkan pada pemesanan. Orang bisa berdebat mereka "menyortir "Sedikit demi sedikit. Tapi kata ini biasanya digunakan untuk mewakili operasi yang melakukan pengaturan ulang sekaligus.)


17
2018-06-21 16:26



Berbicara dengan sangat kasar, pemesanan menentukan elemen mana yang harus dipesan sebelum elemen lain dalam beberapa urutan. Penyortiran adalah proses menempatkan koleksi elemen-elemen tersebut ke dalam urutan yang ditentukan oleh suatu pemesanan.

(Sedikit membingungkan, juga dimungkinkan untuk berbicara tentang "memesan" urutan elemen, yang berarti hal yang sama dengan menyortirnya ke dalam beberapa urutan yang ditentukan oleh pemesanan.)


MEMPERBARUI:

Dalam hal penerapan, contoh yang baik adalah kontainer standar (misalnya peta, http://en.cppreference.com/w/cpp/container/map), yang mengambil parameter templat ekstra yang memasok pemesanan. Ini default untuk std::less<Key> dalam hal peta. Jika Anda ingin memesan sendiri, Anda menggunakan jenis pembanding yang berbeda saat membuat peta dan yang digunakan sebagai gantinya. Cara umum untuk menyediakan pembanding Anda sendiri adalah dengan menerapkan struct kecil yang memiliki bool operator()(const Key& lhs, const Key& rhs) const.


16
2018-06-21 16:26



IBM membuat perbedaan antara set yang disortir dan yang diurutkan:

Set dapat diurutkan atau dipesan:

  • Kumpulan yang dipesan adalah himpunan yang unsur-unsurnya diatur dalam urutan di mana mereka ditambahkan ke himpunan. Perhatikan bahwa ini adalah bagaimana set dibuat secara default. Sebagai contoh:

    {int} S1 = {3,2,5}; 
    

    dan

    ordered {int} S1 = {3,2,5};
    

    ekuivalen.

  • Satu set yang diurutkan adalah satu set di mana elemen-elemen disusun dalam urutan alami, naik (atau menurun). Untuk string, tatanan alam adalah urutan leksikografi. Urutan alam juga tergantung pada sistem lokal. Sebagai contoh:

    sorted {int} sortedS = {3,2,5};
    

    dan

    ordered {int} orderedS = {2,3,5};
    

    ekuivalen, dan iterasi diurutkan atau diurutkan akan memiliki perilaku yang sama.   Untuk menentukan urutan menurun, Anda menambahkan kata kunci terbalik.

Juga, Kemitraan Informasi Nasional Kemitraan mengusulkan interpretasi istilah kepada Institut Standar dan Teknologi Nasional pada tahun 2002:

ISU:

Apa perbedaan antara istilah "pengurutan" dan "pemesanan"?     Terkadang kata-kata itu digunakan secara bergantian.

PERNYATAAN

Meskipun istilah "penyortiran" dan "pemesanan" terkadang digunakan     secara bergantian dalam diskusi sistem TI, mereka agak berbeda     makna. Ketika satu macam, satu memisahkan item ke dalam berbagai jenis atau     kelas; ketika satu pesanan, satu mengatur barang-barang tertentu     memesan.


10
2018-06-21 16:35



Saya pikir ini membantu untuk memikirkan hal ini dalam istilah atau menyortir algoritma. Beberapa algoritma penyortiran menjaga urutan sementara yang lain tidak. Sebagai contoh, perhatikan dua jenis sorting algoritma sortir dan sortir yang naif dan tidak efisien. Semacam gelembung dijamin untuk mempertahankan urutan dan pemilihan semacam tidak. Melestarikan pesanan berarti elemen yang identik tidak ditukar.

Melestarikan pesanan penting terutama ketika item berisi data lain yang tidak disortir. Misalnya jika Anda menyortir pada usia orang-orang mereka mungkin memiliki usia yang sama tetapi nama yang berbeda dan Anda mungkin ingin mempertahankan pesanan asli.

Lihat algoritma penyortiran di wiki mereka memberikan kompleksitas waktu dan stabilitasnya. Stabil berarti pesanan asli dipertahankan.
https://en.wikipedia.org/wiki/Sorting_algorithm


1
2018-06-21 17:45



Peringkat: perbandingan untuk pengaturan penentu sebagian dari satu set; tabrakan dimungkinkan

rank1 = max({foo1.bar, foo2.bar})
rank2 = min({foo2.kite, foo2.kite})

Pengurutan: komposisi peringkat tertimbang yang memungkinkan satu set untuk sepenuhnya dan secara unik diatur tanpa tabrakan laten; urutan penyisipan sering kali merupakan resolusi mundur ketika peringkat eksplisit saja tidak memadai untuk subkumpulan

order = {
   ordering1 = (foo1.bar != foo2.bar) ? rank1(foo1, foo2) : ordering2(foo1, foo2)
   ordering2 = (foo1.kite != foo2.kite) ? rank2(foo1, foo2) : fallback(foo1, foo2)
}

Menyortir: pengaturan dari satu set dengan perintah menggunakan akses khusus dan strategi partisi

 sort1 = strand(foo, order)
 sort2 = bubble(foo, order)

Diurutkan: keadaan pengaturan biner untuk satu set sesuai dengan perintah (benar atau salah)

is_sorted = {
  for (each foo)
    (is_ordered(foo(n), foo(n-1)) ? continue : return false;
  return true;
}

1
2018-06-21 20:56



Relasi urutan bersifat transitif. Hubungan pemilahan tidak.
Anda dapat memesan urutan bilangan bulat. Anda hanya dapat mengurutkan satu set yang berisi pisang, apel, buah ...


1
2018-06-21 21:06



Tusukan saya ini ... Pengurutan ditentukan oleh pengguna. Misalnya Anda mungkin memesan serangkaian string berdasarkan yang paling diakses, paling populer, dll. Menyortir "umumnya" berasal dari satu set metode OS yang ada. Contohnya termasuk menyortir satu set string berdasarkan abjad berdasarkan string lokal.

Cara saya melihatnya adalah sebagai berikut. Jika saya memesan koleksi saya menetapkan predikat yang menentukan di mana dalam koleksi barang akan ada. Jika saya mengurutkan koleksi saya melakukan ini biasanya karena saya ingin cepat mencari. Penyortiran biasanya menghasilkan waktu mencari yang cepat untuk item tertentu dari koleksi. Ini berlaku untuk orang-orang seperti string, integer dan sebagainya.

Melihat jawaban saya, saya pikir memesan dan menyortir hampir dapat dipertukarkan. Namun, saya masih akan mengatakan bahwa pemesanan didefinisikan oleh pengguna, menyortir adalah konsep yang dikenal. Misalnya, kita semua tahu bahwa menyortir daftar nama menghasilkan abjad. Jika saya ingin mengurutkan daftar nama berdasarkan algoritme saya sendiri, katakan berdasarkan popularitas, saya memperkenalkan algoritme pengurutan saya sendiri yang memerintahkan string sesuai keinginan saya. Jadi, saya akan mengatakan jika Anda memperkenalkan algoritme yang menyortir tetapi memerintahkan pengurutan berdasarkan persyaratan Anda sendiri maka Anda memesan.


1
2018-06-21 21:15