{"entities":{"Q7361882":{"pageid":31521185,"ns":120,"title":"Item:Q7361882","lastrevid":105423953,"modified":"2026-10-08T13:45:55Z","type":"item","id":"Q7361882","labels":{"en":{"language":"en","value":"The number of comparisons in QuickSort"}},"descriptions":{"en":{"language":"en","value":"AFP entry Quick_Sort_Cost"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74d17c9061f23202ab216612f1e40afd6bfcd6f8","datavalue":{"value":"https://isa-afp.org/entries/Quick_Sort_Cost.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361882$445320EB-9584-467E-A240-835B504BC242","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361882$FAA945EC-29EA-4F99-9F38-626DF7DF8662","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d4d358f4266c5409c44cc00ac8bdee23f9e43ad","datavalue":{"value":"We give a formal proof of the well-known results about the number of comparisons performed by two variants of QuickSort: first, the expected number of comparisons of randomised QuickSort (i. e. QuickSort with random pivot choice) is 2 (n+1) H n - 4 n , which is asymptotically equivalent to 2 n ln n ; second, the number of comparisons performed by the classic non-randomised QuickSort has the same distribution in the average case as the randomised one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361882$1FD5BADD-7CB3-4D99-9AEF-BCBC3EB9B9BF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb1247f88c76a84b67cc8b7e0e4a397a4cdf25bc","datavalue":{"value":{"entity-type":"item","numeric-id":5904100,"id":"Q5904100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$1A5DAF8C-E3A0-4FE7-A717-498C17AD7DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78e45533c2c1d6189b02a9113edc41e2b51daab","datavalue":{"value":{"entity-type":"item","numeric-id":1225454,"id":"Q1225454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$B1E1D445-89CE-4D7E-A621-AA4DCF863109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de5f5cc6013435ce96d7f29cbb4233f9eea4aeae","datavalue":{"value":{"entity-type":"item","numeric-id":3638257,"id":"Q3638257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$A0FDD375-A733-47EA-8FBC-E5F0B1B0B4E0","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"9ac6eca1bc3d489b80eeaf5cfad7b175f5f00f3f","datavalue":{"value":{"entity-type":"item","numeric-id":7361878,"id":"Q7361878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$651A0802-EB9F-4E27-9DDE-02AA33B270EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"4e61d5c4974522a5fe3780c9295027ba96d92743","datavalue":{"value":{"entity-type":"item","numeric-id":7361487,"id":"Q7361487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$E82575C8-B1FF-48E0-B0D9-394BC7445FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0b5465b6a0d9e05645cdb7168eee1aaf7eb2845","datavalue":{"value":{"entity-type":"item","numeric-id":7361518,"id":"Q7361518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$60F4FB6D-FD8A-47AE-88D4-CA249C9F4C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"a0e462408f240420e2b3f4dd5e025dcac9e4a9cd","datavalue":{"value":{"entity-type":"item","numeric-id":7361044,"id":"Q7361044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$0C29F240-3301-4CD7-B79F-4A2E74625EDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df40c95188c41d28e5f7c0a0b44ffb08645bbac7","datavalue":{"value":{"time":"+2017-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361882$E81CEB0C-489C-465D-9746-4A791D1BA753","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c98489f63682014edff8ffb42a27d6c7cd52dfeb","datavalue":{"value":{"text":"The number of comparisons in QuickSort","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361882$9BB502BE-3CCE-417C-AFB1-5B2C12E92F5F","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$3AD3FE90-4D70-4EF3-8FC2-62438B4B52DB","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"1157f6239d5752bb0ad1cee836272bd46c6bf40f","datavalue":{"value":{"entity-type":"item","numeric-id":7360772,"id":"Q7360772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$784F5C2D-10A0-4AEC-95E0-B5A11CE4318D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$DAA9AF60-DC1B-41C1-919E-466E7BF60DA4","rank":"normal"}],"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"c0c59fd18dc304b89b3b0e7e48773a841898ff5b","datavalue":{"value":"28641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361882$B25D29A2-3A47-4A89-920E-DC0F341FB323","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361882$C049A9F3-02A4-44F3-A170-9E67DCFD85F0","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03bedb439d5ea402bd9603d3cdfe1813f9fa06ca","datavalue":{"value":{"entity-type":"item","numeric-id":40356,"id":"Q40356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$071E62FA-E4E5-4413-9163-6115217C7F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$00CEB852-688B-417C-8C32-6B48E9C06473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"3a073d1e3162db58b1a890386d8dbe9eebb4637c","datavalue":{"value":{"entity-type":"item","numeric-id":40373,"id":"Q40373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$3B795661-6CCC-4D88-80D6-93CE36BE1134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"244ebbac6461f60bed6d50e50ce8194b0e233968","datavalue":{"value":{"entity-type":"item","numeric-id":40296,"id":"Q40296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$A0BC3A6F-515E-4E85-A5C1-B45C9E7C8A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"b74075817e632ca235b8b1333580f4f12e29f9fd","datavalue":{"value":{"entity-type":"item","numeric-id":40372,"id":"Q40372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$81264E15-4796-4C73-BA1B-FA8C4759C8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"868d665ea0607bf8bd28ea3e3872eb2ea87bd3d3","datavalue":{"value":{"entity-type":"item","numeric-id":40371,"id":"Q40371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$0C9F2BAD-2BAB-4F23-B566-325BA51178DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"246d8bcd4bf1600a7c6d2b07f9f11f8689d33486","datavalue":{"value":{"entity-type":"item","numeric-id":40320,"id":"Q40320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$FBD3B7BE-79FF-450A-80F6-30F92DC34CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"6bbc316d4497e097d8fb3e48fd57f7643b44826c","datavalue":{"value":{"entity-type":"item","numeric-id":40246,"id":"Q40246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$D5244D6C-9C79-478C-9105-3F912AA2FCF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$12EA06FF-51E2-4165-A266-B29494983707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$AF719188-1A6F-4A59-AAE6-0D12DDCC1609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$13033C72-BC8C-4EF0-8AC9-0C1B0690E37A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03281999c3208b8f3a62eaceadadf1ce834fe219","datavalue":{"value":{"entity-type":"item","numeric-id":12929,"id":"Q12929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$54D6791E-74E6-4AC0-B66D-41AAF6549AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"8dde418bf28e22fefe1976bd953eb7c8ec5b548d","datavalue":{"value":{"entity-type":"item","numeric-id":16770,"id":"Q16770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$BDF70109-8095-4FB4-8843-6644415F32E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"02b329e86bd44e002b407e5543cbe998c79c263a","datavalue":{"value":{"entity-type":"item","numeric-id":13928,"id":"Q13928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$D0215006-1A04-4D1C-9019-3F7A2B0953AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"74afd8a3b10bf054bf31ff15012404c74fd8d4f2","datavalue":{"value":{"entity-type":"item","numeric-id":53726,"id":"Q53726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$99032D36-C6CE-4CCE-8449-DE93CEBC468C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"10fef36c72ce6737e4d52153b38693318e8540dd","datavalue":{"value":{"entity-type":"item","numeric-id":53725,"id":"Q53725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$54AE184F-276E-4648-8D62-F5EF3DA3D5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"dd25ad249c2b0bfc0ae57f791baa0d6fded59cb3","datavalue":{"value":{"entity-type":"item","numeric-id":32511,"id":"Q32511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$A3D1302B-8EED-4295-8910-ECAE77B87C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"255d1eab6148b0a0149f5ba251f819f772375a4c","datavalue":{"value":{"entity-type":"item","numeric-id":23492,"id":"Q23492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361882$7A3BBE0C-76B9-460A-965F-37EF458051DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The number of comparisons in QuickSort","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_number_of_comparisons_in_QuickSort"}}}}}