{"entities":{"Q1889895":{"pageid":1900637,"ns":120,"title":"Item:Q1889895","lastrevid":71683773,"modified":"2026-04-13T23:52:12Z","type":"item","id":"Q1889895","labels":{"en":{"language":"en","value":"Comparing algorithms for sorting with \\(t\\) stacks in series"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2121819"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889895$11A1D6D4-9E62-49F8-86F1-B720F707C820","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bca13c172e46d01f12ba4ab429febc2c9fd54dd4","datavalue":{"value":{"text":"Comparing algorithms for sorting with \\(t\\) stacks in series","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1889895$03E58E9B-A282-4329-8730-FA41A558B316","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e009ba9700a9290f1169d88365614edcac65030","datavalue":{"value":"1055.05001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$0A810D1B-5EEA-4C55-8569-E9C1C8C502EA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889895$F4DEBF0D-01B1-4AAF-8234-5636AEA188DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"710cc084d2ed0d09beceb5d2d7c52611268d6193","datavalue":{"value":{"entity-type":"item","numeric-id":159225,"id":"Q159225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889895$FB3D7195-9C3B-43D2-A1D2-09195DFBD785","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1801fd38eb81fc4d3237d55e24c2e5c8b6b08b15","datavalue":{"value":{"time":"+2004-12-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1889895$2A4F5431-5B1C-4954-817B-30300602A35E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec498d543cf94e3237591ad34fb9ed1f7b870cd3","datavalue":{"value":"https://arxiv.org/abs/math/0404176","type":"string"},"datatype":"url"},"type":"statement","id":"Q1889895$053D039F-E1D8-409F-A9A5-265A184B6B0D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9281d7dca7931464fe87e400083b76eaa15b4203","datavalue":{"value":"Consider a series of stacks and an input permutation of \\(\\{1,\\dots,n\\}\\) on the far right. In one move we can remove the first element from the input and push it to the rightmost stack, or pop an element from a non-empty stack and push it to the stack to its left, or pop an element from the leftmost stack and append it to the output permutation on the far left. Such a move is legal if all non-empty stacks remain sorted with the least element on top. For each permutation \\(p\\) exists a \\(t\\) such that \\(p\\) can be sorted by \\(t\\) stacks in series. \\textit{M. B\u00f3na} [Electron. J. Comb. 9, Research paper A1 (2003; Zbl 1028.05003)] gives a survey of stack sorting.  A permutation that can be sorted by the right-greedy algorithm can be sorted by the left-greedy algorithm using the same number of stacks. At least \\(t!(t+1)^{n-t}\\) permutations of \\(\\{1,\\dots,n\\}\\) can be sorted by the left-greedy algorithm using \\(t\\) stacks. This algorithm is not optimal. It does not define a closed class of permutations for \\(t>2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889895$2E786321-305F-4599-AA35-D105840DD11C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$D68027CB-EAA2-4AA3-97BD-71293DAD3859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$13FEE4C1-135F-47B5-93CB-FE451F8F5C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1bcdc2a107fd2414d151e8610f3471a8784e75bf","datavalue":{"value":"68W01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$511DFCF6-EBF4-4221-8805-FAB7487C9053","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"697e6a3368519d4654d8ba85648e5eb5d83fac5d","datavalue":{"value":"2121819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$9F65332E-5CAB-4B56-BFD7-C94C3B15C7EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889895$723BE497-18D3-4B67-93F6-4A359FFA75AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f9d78447eb16628bd0196c3cefb3e317ae5ff0a","datavalue":{"value":"stack sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889895$6B7F5505-2A96-4B88-AE94-80260E493BE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10ccd0d07fdbfff2935c5c920942bcc0683f6847","datavalue":{"value":"sorting in series","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889895$7CD7A831-B3EB-4821-BD21-E7BE0175D501","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889895$6840314A-66D6-4BF3-A921-AA28D407BF3E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a4b27e4dac851ec09ed6003b7063aece71c4e7c0","datavalue":{"value":"W2082782379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$906DD59F-04B3-465F-8DD7-55DCFF77346A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1d739928700b42c02446f3c702df799c69cca2e6","datavalue":{"value":"10.1007/S00026-004-0209-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889895$9DB539AB-F311-48FE-9237-D904159C4530","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b1f83dcbc7767d438b937a5f13dfb1245c11e5b","datavalue":{"value":{"entity-type":"item","numeric-id":1408520,"id":"Q1408520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"044ff7c0a56fa91bf7fd6180c016e2d25a500736","datavalue":{"value":{"amount":"+0.87313503","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$F0111D60-06C7-4654-80F6-22233E83E20C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"050d65691acfc3fea47b81487c801195db881f88","datavalue":{"value":{"entity-type":"item","numeric-id":1115198,"id":"Q1115198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e511af47dd9b75522235e2d371ad1107733a01","datavalue":{"value":{"amount":"+0.8544053","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$AF1B081F-82A9-4B80-B39B-F221953AF837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4f713f3e950792482de9004742a51a415cedbad","datavalue":{"value":{"entity-type":"item","numeric-id":1365941,"id":"Q1365941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aee8918861e607f2fe525dcd4ae50ce848a0ce1e","datavalue":{"value":{"amount":"+0.85183835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$18FFF447-8419-4902-9C54-F4B4EFA3A16B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16b29d2c9603805d9a40147bf42fbedb8def0859","datavalue":{"value":{"entity-type":"item","numeric-id":2848974,"id":"Q2848974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdda9399657867db213ac4a2da68388b83f05e3b","datavalue":{"value":{"amount":"+0.85148406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$53FDC41C-4DFC-46BD-82E1-64F0B2648F9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e4c16b23d503ebd882498b62de0547670b657fc","datavalue":{"value":{"entity-type":"item","numeric-id":2035992,"id":"Q2035992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69701966d3d8960770e7032c47ef52259d7c314f","datavalue":{"value":{"amount":"+0.85032225","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$8B02D31B-30E6-405A-9B11-F4548265D99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"638d7ed795cec248f9e02851b0c3be7d50b2b105","datavalue":{"value":{"entity-type":"item","numeric-id":3801082,"id":"Q3801082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc748c972352a97f235a2dbc52ad4df060ed96e","datavalue":{"value":{"amount":"+0.8440285","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$DCB2BF56-EF40-4FDB-96D6-DE5DD4BB5432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b4952e58c6f4776cbe009150790c8e2ff70875b","datavalue":{"value":{"entity-type":"item","numeric-id":3343451,"id":"Q3343451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"837cacdf1af4d501260ce9464fa230e80dbdfa3b","datavalue":{"value":{"amount":"+0.8421896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$9D4BB835-B4CF-4047-88B8-578F8F89020B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7bd5a460e6d657e1fcd13c58d644c92f615e8d8","datavalue":{"value":{"entity-type":"item","numeric-id":5364228,"id":"Q5364228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e81433ad3417bdb1f03efca1f50f741acb7f69bf","datavalue":{"value":{"amount":"+0.84112203","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$6CF32F0B-504C-4FE0-8EF9-18A342974B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebdf6cdf323f4546b276eab7e569143b5480e98a","datavalue":{"value":{"entity-type":"item","numeric-id":5757092,"id":"Q5757092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98e5874c6b8549da1818683e0d785fc481256692","datavalue":{"value":{"amount":"+0.83596295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889895$F722A892-15F4-4E5F-AF5E-5E7DF6DCC5A1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Comparing algorithms for sorting with \\(t\\) stacks in series","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Comparing_algorithms_for_sorting_with_%5C(t%5C)_stacks_in_series"}}}}}