Dalam komentar untuk artikel sebelumnya, kadang-kadang ada celaan - mengapa bahkan mempelajari penyortiran lain, jika sudah ada semacam Quick tercepat di dunia. Mereka mengatakan bahwa semua eksotis fantastis ini tidak ada gunanya dan tidak ada yang perlu.


Percy Diaconis , yang mempelajari solitaire memilah-milah, percaya bahwa itu adalah cara tercepat untuk secara manual mengatur setumpuk kartu.

Jadi, jika seorang matematikawan yang disegani (dan penyihir kartu berpengalaman) tidak berbohong, maka dengan nilai praktis dari algoritma, semuanya beres.

Sekarang perhatikan tanganmu.

Tahap 1. Berbaring di tumpukan

Jadi, ambil cacing dari dek. Mereka akan mewakili array dari tiga belas elemen acak.



Kita perlu menguraikan kartu menjadi beberapa tumpukan, sehingga dalam setiap tumpukan kartu adalah urutan yang terurut.

Dengan kata lain, tugas kita pada tahap ini adalah dengan cepat membuat beberapa subarrays yang diurutkan dari array yang tidak disortir. Selain itu, sangat diinginkan bahwa jumlah subarrays ini lebih kecil, yang berarti Anda harus berusaha untuk memastikan bahwa subarrays lebih asli. Ini dilakukan sebagai berikut.

Kartu pertama adalah awal dari tumpukan pertama.



Kami mentransfer kartu ke tumpukan ini pada gilirannya, sampai kartu yang ditransfer berikutnya lebih kecil dari yang teratas di tumpukan.

Selain itu, setiap tumpukan adalah tumpukan - kami tidak bekerja dengan seluruh tumpukan, tetapi hanya dengan kartu teratas di dalamnya, yang terakhir.



Jika kartu saat ini lebih dari minimum dalam tumpukan, maka Anda harus membuat tumpukan baru, kartu saat ini membuka tumpukan baru.



Urutan tumpukan sangat penting! Jika jumlah mereka sudah lebih dari satu, maka kita meletakkan kartu berikutnya bukan di tumpukan terakhir, tetapi di tumpukan paling kiri, di mana kita bisa meletakkannya.

Sekarang, setelah wanita itu, saya harus melampirkan sembilan di suatu tempat. Secara mekanis, saya ingin meletakkan kartu di tumpukan kedua, tetapi di tumpukan pertama kartu teratas lebih dari sembilan. Jadi, kita dapat melanjutkan tumpukan pertama tanpa melanggar urutannya. Tiga berikutnya, yang mengikuti sembilan, juga omong-omong, pergi ke tumpukan pertama.



Tujuh dan enam tidak dapat ditambahkan ke tumpukan pertama (mereka lebih besar dari kartu teratas di dalamnya), tetapi mereka masih memiliki tempat di tumpukan kedua.



Ace memulai tumpukan baru. Agak yang tersisa jatuh ke baki yang berbeda, tergantung pada seberapa jauh ke kiri adalah tumpukan di mana ia bisa dimasukkan.



Hasilnya, kartu-kartu tersebut diletakkan dalam beberapa tumpukan. Di setiap tumpukan, kartu adalah urutan menurun, di atas adalah kartu terkecil. Tumpukan adalah tumpukan.

Karena kami mencoba untuk mengisi tumpukan yang ada di sebelah kiri, kami membentuk jumlah sekecil mungkin. Jika kita hanya berjalan di sekitar array dan mengekstrak subarrays yang berkurang darinya, maka heap secara alami akan menjadi jauh lebih besar.

Tahap 2. Baris bawah

Pindahkan kartu teratas yang tersedia sedikit sehingga berdiri di baris yang terpisah. Jika tumpukan adalah tumpukan, maka kami akan bekerja dengan baris bawah seperti dengan antrian.



Yang penting, kartu teratas yang tersedia di tumpukan juga merupakan urutan yang dipesan. Baris bawah sudah diurutkan dalam urutan menaik. Yang tidak mengejutkan - ketika membentuk tumpukan kartu, kartu yang lebih kecil dikirim ke kiri.

Di masa depan, sampai akhir penyortiran, kami tidak tertarik pada semua kartu yang diletakkan di atas meja. Hanya ini yang dibutuhkan:

• Kartu paling kiri (sebut saja kartu saat ini) di baris bawah antrian.
• Di tumpukan-tumpukan, kami hanya bekerja dengan kartu teratas yang tersedia. Dalam hal ini, hanya tumpukan yang terletak langsung di peta saat ini dan ke kiri yang diperlukan. Tumpukan yang ada di kanan saat ini tidak diperlukan.

Di baris bawah, kami mengurutkan kartu dari kiri ke kanan kartu. Paling kiri adalah minimum saat ini, kami mengembalikannya ke baris atas asli. Pada saat yang sama, setiap kali kami kembali ke pangkalan kartu lain, perlu untuk menempatkan yang lain di tempatnya. Darimana mendapatkannya? Dari tumpukan yang berada di atas peta saat ini dan di sebelah kiri - di antara kartu yang tersedia, minimum dipilih yang bergerak ke posisi kosong dari kartu kiri saat ini di baris bawah, dan dari sana ke array utama.

Dua dalam array segera kembali. Tempat kosong diambil oleh triple (kami memindahkannya dari tumpukan pertama ke baris bawah), dan dari baris bawah triple, sebagai minimum saat ini, pergi ke array utama. Dalam dua tumpukan pertama, minimum dicari lagi - ini adalah empat - yang juga pulang. Lima menjadi minimum saat ini, dll.



Menggabungkan pekerjaan dengan urutan antrian dan urutan tumpukan dengan sangat cepat, kami mendapatkan semua elemen dari minimum hingga maksimum. Sesuatu seperti itu, secara umum.

Animasi proses ini.



Jika Anda menerjemahkan semua hal di atas ke dalam Python, Anda mendapatkan ini:

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles]) 

Referensi

Penyortiran kesabaran ( Google-translate )

Sumber penyortiran kesabaran

Princeton CS: Selanjutnya meningkat terpanjang

Combinatorics of pile sorting pile ( Google-translate )

Wiki abstrak: pemilahan pasien

Word Aligned ( Google-translate )

Artikel Seri:

• Aplikasi Excel AlgoLab.xlsm
• Pertukaran macam
• Urutan Penyisipan
  • Sortir Pustakawan
  • Sortir Solitaire
  • Sortir "Menara Hanoi"
  • Penyortiran meja muda
  • Balikkan Sortir
  • Masukkan Sortir Perbandingan
• Sortir berdasarkan pilihan
• Gabungkan Urusan
• Urutkan berdasarkan distribusi
• Sortasi Hibrid

Di aplikasi AlgoLab, pengurutan ini sekarang aktif. Pada saat yang sama, visualisasi dimungkinkan dalam dua mode: dalam bentuk peta (mode default) dan hanya dalam bentuk angka. Namun, untuk gaya kartu, perlu bahwa perbedaan antara elemen maksimum dan minimum dalam array kurang dari 54 (jumlah kartu di dek, termasuk dua pelawak). Jika kondisi ini tidak terpenuhi atau mode kartu dimatikan sama sekali (untuk ini, Anda perlu menulis kartu = 0 di komentar untuk sel dengan nama sortir), maka visualisasi akan dalam bentuk angka kusam.

Gugatan dipertimbangkan dalam urutan senioritas preferensi: puncak <klub <rebana <hati.


Artinya, setiap kartu dari setelan rebana dari rebana lebih besar dari kartu jas klub, kartu apa pun dari jas hati lebih besar dari kartu apa pun dari setelan puncak, dll. Jika kita menggambar analogi dengan angka, maka puncaknya adalah dari 0 hingga 9, klub dari 10 hingga 19, berlian dari 20 hingga 29, jantung adalah dari 30 hingga 39 (ya, tentu saja, di dalam jas jumlah kartu tidak tepat sepuluh, tetapi Anda mengerti apa yang dimaksud). Adapun senioritas dalam gugatan itu, akan menjadi biasa: dari deuce ke ace. Anda juga dapat mengambil pelawak yang lebih tua dari semua kartu lainnya. Dalam hal ini, joker merah lebih berbobot daripada hitam.

Artikel ini ditulis dengan dukungan EDISON Software, sebuah perusahaan pengembangan web profesional yang baru-baru ini mendesain ulang situs webnya.