{"id":452848,"date":"2025-03-23T15:08:32","date_gmt":"2025-03-23T15:08:32","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=452848"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=452848","title":{"rendered":"<span>\u0422\u0440\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u0445<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/414\/56a\/06f\/41456a06f104d72917fd9747198e5090.png\" alt=\"\u041f\u043e\u0433\u043e\u0434\u0438, \u0447\u0442\u043e? GCC std::sort \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438? WTF???\" title=\"\u041f\u043e\u0433\u043e\u0434\u0438, \u0447\u0442\u043e? GCC std::sort \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438? WTF???\" width=\"1080\" height=\"643\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/414\/56a\/06f\/41456a06f104d72917fd9747198e5090.png\"\/><\/p>\n<div><figcaption>\u041f\u043e\u0433\u043e\u0434\u0438, \u0447\u0442\u043e? GCC std::sort \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438? WTF???<\/figcaption><\/div>\n<\/figure>\n<p>\u042f \u0437\u043d\u0430\u044e \u043c\u043d\u043e\u0433\u0438\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432 \u0438 \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u0432 IT \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u044f\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u0434\u043e\u043b\u044e\u0431\u043b\u0438\u0432\u0430\u044e\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0432 \u0438 \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u0447\u0438\u0442\u0430\u044e\u0442 \u0438\u0445 \u0434\u0430\u043b\u0451\u043a\u0438\u043c\u0438 \u043e\u0442 \u0436\u0438\u0437\u043d\u0438 \u0438\u0434\u0438\u043e\u0442\u0430\u043c\u0438 \u0438\u0437-\u0437\u0430 \u0438\u0445 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0439 \u0432 \u0434\u0443\u0445\u0435 &#171;\u043d\u0435\u043b\u044c\u0437\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0437\u0430 nlogn&#187; &#8212; \u0432\u0435\u0434\u044c \u044d\u0442\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0435\u0432\u0435\u0440\u043d\u043e, \u0435\u0441\u0442\u044c \u0436\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u043e\u043c \u0438 radix sort. \u041d\u044e\u0430\u043d\u0441 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0435 \u0432\u044b\u0448\u0435 &#8212; \u044d\u0442\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u0430\u044f \u043d\u0435\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0430\u044f \u0442\u0440\u0430\u043a\u0442\u043e\u0432\u043a\u0430 \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0445 \u0442\u0435\u043e\u0440\u0435\u043c \u043e\u0431 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043e\u043a, \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a: &#171;\u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u043b \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 <em>n<\/em> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0443\u044e \u043a \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u044e\u0449\u0435\u043c\u0443 \u043f\u043e\u0440\u044f\u0434\u043a\u0443, \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0447\u0435\u043c \u0437\u0430 nlogn <strong>\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0433\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f<\/strong>&#171;. \u0412 \u044d\u0442\u043e\u043c \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u043b\u043e\u0432, \u043e\u043d\u043e \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u043e \u0432 \u043f\u043b\u0430\u043d\u0435 \u043a\u043e\u0433\u043d\u0438\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u044f\u0442\u0438\u044f, \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043b \u0436\u0438\u0440\u043d\u044b\u043c \u0448\u0440\u0438\u0444\u0442\u043e\u043c, \u0447\u0443\u0432\u0441\u0442\u0432\u0443\u0435\u0442\u0435 \u0440\u0430\u0437\u043d\u0438\u0446\u0443?<\/p>\n<p>\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0445\u043e\u0447\u0443 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043e\u0431 \u044d\u0442\u043e\u0439 \u0442\u0435\u043e\u0440\u0435\u043c\u0435 \u0438 \u0435\u0449\u0451 \u043e \u0434\u0432\u0443\u0445, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u043d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043a\u043e\u0433\u0434\u0430 \u0432\u0435\u043b \u0437\u0430\u043d\u044f\u0442\u0438\u044f \u043f\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435 \u0432 9-11 \u043a\u043b\u0430\u0441\u0441\u0430\u0445 \u0431\u0443\u0434\u0443\u0447\u0438 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u043c \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u043a\u0443\u0440\u0441\u043e\u0432. \u042d\u0442\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0434\u043b\u044f \u043c\u0435\u043d\u044f \u0431\u044b\u043b\u0438 \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u043e\u0442\u043a\u0440\u044b\u0442\u0438\u0435\u043c, \u0440\u0430\u0434\u043e\u0432\u0430\u043b\u0441\u044f \u0432\u043d\u0435 \u0441\u0435\u0431\u044f \u043a\u043e\u0433\u0434\u0430 \u0432\u044b\u0432\u0435\u043b \u0441\u0430\u043c \u043e\u0434\u043d\u0443 \u0438\u0437 \u043d\u0438\u0445 &#8212; \u0435\u0451 \u044f \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u043b \u043d\u0438 \u0432 \u043e\u0434\u043d\u043e\u043c \u0443\u0447\u0435\u0431\u043d\u0438\u043a\u0435 \u043f\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435. \u0412 \u043f\u043e\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0438 \u0432\u0441\u0435 \u0442\u0440\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0431\u044b\u043b\u0438 \u043d\u0430\u0439\u0434\u0435\u043d\u044b \u0432 \u043d\u0435\u0434\u0440\u0430\u0445 \u041a\u043d\u0443\u0442\u0430, \u043d\u043e \u0447\u0451\u0440\u0442 \u043f\u043e\u0431\u0435\u0440\u0438, \u0438\u0445 \u043f\u043e\u0438\u0441\u043a \u0431\u044b\u043b \u0441\u043b\u043e\u0436\u043d\u0435\u0435, \u0447\u0435\u043c \u0432\u044b\u0432\u043e\u0434!<\/p>\n<p>\u0415\u0441\u043b\u0438 \u044f \u0435\u0449\u0451 \u043d\u0435 \u0443\u0431\u0435\u0434\u0438\u043b \u0412\u0430\u0441 \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e, \u0442\u043e \u0432\u043e\u0442 \u043c\u043e\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044f\u044f \u043f\u043e\u043f\u044b\u0442\u043a\u0430: \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u044e \u043f\u043e\u0447\u0435\u043c\u0443 \u043f\u0443\u0437\u044b\u0440\u0451\u043a &#8212; \u044d\u0442\u043e \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u0430\u044f \u0444\u0438\u0433\u043d\u044f, \u043d\u043e \u0432\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0442\u0430\u043a\u0436\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 &#8212; \u044d\u0442\u043e \u0441\u0443\u043f\u0435\u0440 \u0432\u0430\u0436\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430, \u044f\u0432\u043b\u044f\u044e\u0449\u0430\u044f\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e std::sort \u0432 MSVC, GCC \u0438 Clang. \u0420\u0430\u0441\u0441\u043a\u0430\u0436\u0443, \u043a\u0430\u043a\u0438\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c, \u044f\u0432\u043b\u044f\u044e\u0449\u0430\u044f\u0441\u044f \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u043a\u0430\u043a \u043f\u0443\u0437\u044b\u0440\u0451\u043a.<\/p>\n<h2>\u0422\u0435\u043e\u0440\u0435\u043c\u0430 \u21161<\/h2>\n<p>\u0417\u0434\u0435\u0441\u044c \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0441\u044e\u0440\u043f\u0440\u0438\u0437\u043e\u0432 &#8212; \u0442\u0430 \u0441\u0430\u043c\u0430\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u043f\u0440\u043e nlogn, \u043d\u043e \u0432\u0441\u0451-\u0442\u0430\u043a\u0438 \u044f \u0435\u0451 \u0440\u0430\u0441\u043f\u0438\u0448\u0443 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e, \u043d\u0430 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043a\u0430\u0440\u0442\u0438\u043d\u044b<\/p>\n<p><strong>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 1. <\/strong><em><u>\u041f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u043e\u0439 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 n<\/u><\/em> \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"p_0, p_1, \\ldots, p_{n-1}\\in\\{0, 1, \\ldots, n-1\\}~~i\\neq j\\Rightarrow p_i\\neq p_j\" alt=\"p_0, p_1, \\ldots, p_{n-1}\\in\\{0, 1, \\ldots, n-1\\}~~i\\neq j\\Rightarrow p_i\\neq p_j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b6b\/bba\/b82\/b6bbbab82f5a29022d3240638c991145.svg\" width=\"424\" height=\"23\"\/><\/p>\n<p>\u041d\u0435\u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 &#8212; \u044d\u0442\u043e \u0432\u0437\u044f\u043b\u0438 0, 1, &#8230; , n-1 \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u0430\u043b\u0438. \u0412 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u0445 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u0443\u0434\u043e\u0431\u043d\u043e \u0438\u0437\u0443\u0447\u0430\u0442\u044c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043e\u043a: \u043f\u043e \u0441\u0443\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u0443\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0434\u0430\u0451\u0442 \u043d\u0435\u0443\u0431\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a. \u0422\u0435\u043f\u0435\u0440\u044c \u043c\u044b \u0433\u043e\u0442\u043e\u0432\u044b \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0435\u043e\u0440\u0435\u043c\u0443<\/p>\n<p><em>\u041d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u0438\u043d\u044b n<\/em><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"a_0, a_1, a_2, \\ldots, a_{n-1}\" alt=\"a_0, a_1, a_2, \\ldots, a_{n-1}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cc5\/26f\/2a8\/cc526f2a8ddc264bfc34eced51a907b7.svg\" width=\"155\" height=\"16\"\/><\/p>\n<p><em>\u043d\u0430\u0445\u043e\u0434\u0438\u043b \u0431\u044b \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 p \u0442\u0430\u043a\u0443\u044e, \u0447\u0442\u043e<\/em><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"a_{p_0}\\leq a_{p_1}\\leq \\ldots \\leq a_{p_{n-1}} \" alt=\"a_{p_0}\\leq a_{p_1}\\leq \\ldots \\leq a_{p_{n-1}} \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c2c\/e45\/cbe\/c2ce45cbe14dbfbafbb3ec31d3e84f8b.svg\" width=\"189\" height=\"22\"\/><\/p>\n<p><em>\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c<\/em><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\mathcal{O}(n\\log n)\" alt=\"\\mathcal{O}(n\\log n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4bf\/878\/7df\/4bf8787dfc3145e58a6e984779d9e495.svg\" width=\"85\" height=\"22\"\/><\/p>\n<p><em>\u043f\u043e\u043f\u0430\u0440\u043d\u044b\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u0442.\u0435. \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0434\u0432\u0443\u0445 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/em><\/p>\n<p>\u0414\u043b\u044f \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430 \u044d\u0442\u043e\u0433\u043e \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044f \u044f \u043b\u044e\u0431\u043b\u044e \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u044e: \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0432\u044b \u0438\u0433\u0440\u0430\u0435\u0442\u0435 \u0432 \u0438\u0433\u0440\u0443 \u0441\u043e \u0441\u0432\u043e\u0438\u043c \u043a\u043e\u043b\u043b\u0435\u0433\u043e\u0439. \u041e\u043d \u0437\u0430\u0433\u0430\u0434\u044b\u0432\u0430\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0435\u0434\u043c\u0435\u0442, \u0430 \u0432\u044b \u0437\u0430\u0434\u0430\u0451\u0442\u0435 \u0432\u043e\u043f\u0440\u043e\u0441 \u043f\u0440\u043e \u044d\u0442\u043e\u0442 \u043f\u0440\u0435\u0434\u043c\u0435\u0442, \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0442\u0432\u0435\u0442 \u0434\u0430\/\u043d\u0435\u0442. \u0412\u0430\u0448\u0430 \u0446\u0435\u043b\u044c \u043e\u0442\u0433\u0430\u0434\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u043c\u0435\u0442. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u044d\u0442\u043e\u0439 \u0438\u0433\u0440\u044b \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u0430\u044f: \u0435\u0441\u0442\u044c \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>\u0425<\/em>, \u043f\u0435\u0440\u0432\u044b\u0439 \u0438\u0433\u0440\u043e\u043a \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>y<\/em>, \u0432\u0442\u043e\u0440\u043e\u0439 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u0434\u0430\u0432\u0430\u0442\u044c \u0432\u043e\u043f\u0440\u043e\u0441\u044b \u0432\u0438\u0434\u0430 &#171;\u041f\u0440\u0430\u0432\u0434\u0430, \u0447\u0442\u043e <em>y<\/em> \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0443 <em>A<\/em>?&#187;. \u0412\u043e\u043f\u0440\u043e\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u0442\u044c &#8212; \u043a\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f \u0432\u044b\u0431\u043e\u0440\u0430 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432\/\u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u0434\u043b\u044f \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0438\u0433\u0440\u043e\u043a\u0430 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u0442 \u043a \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432 \u0434\u043b\u044f \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 <em>y<\/em>?<\/p>\n<p>\u041e\u0442\u0432\u0435\u0442 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c: \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0443\u0436\u043d\u043e \u0437\u0430\u0434\u0430\u0442\u044c &#8212; \u044d\u0442\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 <em>X<\/em><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\lceil \\log_2|X| \\rceil\" alt=\"\\lceil \\log_2|X| \\rceil\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/62b\/151\/5f0\/62b1515f0f398c0a29a7d71c6c49bfe8.svg\" width=\"81\" height=\"22\"\/><\/p>\n<p>\u0418\u0434\u0435\u044f \u043f\u0440\u043e\u0441\u0442\u0430\u044f: \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u0437\u0430\u0434\u0430\u0451\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u0430\u0432 \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>A <\/em>\u043c\u044b \u0434\u0435\u043b\u0438\u043c <em>X<\/em> \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438: \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 <em>A<\/em> \u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0435 \u0438\u0437 <em>A.<\/em> \u041f\u043e\u043b\u0443\u0447\u0438\u0432 \u043e\u0442\u0432\u0435\u0442 \u043e\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0438\u0433\u0440\u043e\u043a\u0430 \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043a \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u043d\u043e \u0443\u0436\u0435 \u043d\u0435 \u0441 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c <em>X<\/em>, \u0430 \u0441 <em>A<\/em> \u0438\u043b\u0438 <em>X\\A <\/em>(\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 <em>X<\/em> \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 <em>A<\/em>)<em>. <\/em>\u0412\u0440\u043e\u0434\u0435 \u0431\u044b \u0438\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u0447\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e, \u0442\u0435\u043c \u0441\u043b\u043e\u0436\u043d\u0435\u0435 \u0432 \u044d\u0442\u043e\u0439 \u0438\u0433\u0440\u0435 \u043d\u0430\u0439\u0442\u0438 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0432 \u043e\u0442\u0432\u0435\u0442 \u043c\u044b \u043e\u0441\u0442\u0430\u043d\u0435\u043c\u0441\u044f \u0441 \u0431\u041e\u043b\u044c\u0448\u0438\u043c \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c, \u0432\u0441\u0435 \u0447\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0439 \u0438\u0433\u0440\u043e\u043a &#8212; \u044d\u0442\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>A<\/em> \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u043e \u0434\u0435\u043b\u0438\u043b\u043e <em>X<\/em> \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u043e\u043f\u043e\u043b\u0430\u043c. \u0421 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0435\u0439 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0435\u0441\u0442\u044c <em>y <\/em>\u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430, \u0435\u0441\u043b\u0438 \u0431\u044b\u0442\u044c \u0442\u043e\u0447\u043d\u0435\u0435 \u0442\u043e \u0432\u0441\u0435 \u0442\u0430\u043a\u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"n\\rightarrow\\frac{n+1}{2}\" alt=\"n\\rightarrow\\frac{n+1}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b1\/6aa\/c6c\/3b16aac6ce4d3edcf7d9231a49890b95.svg\" width=\"93\" height=\"42\"\/><\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 1, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f <em>y<\/em>, \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u0447\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u043e \u0447\u0442\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 &#8212; \u044d\u0442\u043e <em>y <\/em>\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0438 \u0438\u0441\u043a\u0430\u043b\u0438. \u0412 \u0438\u0442\u043e\u0433\u0435 \u0438\u043c\u0435\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435: \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u0435\u0440\u0430 <em>n<\/em> \u043d\u0443\u0436\u043d\u043e \u0443\u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0438\u0442\u044c (\u0438\u043b\u0438 \u0435\u0441\u043b\u0438 \u0431\u044b\u0442\u044c \u0442\u043e\u0447\u043d\u0435\u0435 \u0443\u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0438\u0442\u044c \u0441 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435\u043c \u0432\u0432\u0435\u0440\u0445), \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u043e \u0441\u0442\u0430\u043b\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 1? \u042d\u0442\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438 \u0435\u0441\u0442\u044c <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\lceil \\log_2n\\rceil\" alt=\"\\lceil \\log_2n\\rceil\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0f7\/5ca\/ac3\/0f75caac37c010e51d4b7b1bff9a1ce2.svg\" width=\"65\" height=\"22\"\/><\/p>\n<p>\u041a\u0430\u043a \u0432\u0441\u0451 \u044d\u0442\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u043c, \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430\u043c \u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c\u0443 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044e? \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u044f \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043c\u044b \u043a\u043e\u0441\u0432\u0435\u043d\u043d\u043e \u0434\u0435\u043b\u0438\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 &#171;\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435&#187; \u0438 &#171;\u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435&#187;, \u043d\u0430 \u0442\u0430\u043a\u0438\u0435, \u0433\u0434\u0435 \u044d\u0442\u0438 \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043d\u0443\u0436\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0438 \u0442\u0435, \u0433\u0434\u0435 \u044d\u0442\u0438 \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0430 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u0442\u043e\u0447\u043d\u043e \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u043b\u043e\u0438\u043a\u0443 \u0438\u0437 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0438 &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c, &#8212; \u044d\u0442\u043e <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\lceil \\log_2n!\\rceil\" alt=\"\\lceil \\log_2n!\\rceil\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b96\/358\/dec\/b96358dec766b50ba2b668ec42f5f015.svg\" width=\"71\" height=\"22\"\/><\/p>\n<p>\u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u044d\u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 &#8212; \u044d\u0442\u043e <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%A1%D1%82%D0%B8%D1%80%D0%BB%D0%B8%D0%BD%D0%B3%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0421\u0442\u0438\u0440\u043b\u0438\u043d\u0433\u0430<\/a>, \u043d\u043e \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432\u043e\u0442 \u0442\u0430\u043a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\lceil \\log_2n!\\rceil\\geq \\left\\lceil \\log_2\\left(\\frac{n}{2}\\right)^\\frac{n}{2}\\right\\rceil= \\left\\lceil \\frac{n}{2}\\log_2\\left(\\frac{n}{2}\\right)\\right\\rceil=\\mathcal{O}(n\\log n)\" alt=\"\\lceil \\log_2n!\\rceil\\geq \\left\\lceil \\log_2\\left(\\frac{n}{2}\\right)^\\frac{n}{2}\\right\\rceil= \\left\\lceil \\frac{n}{2}\\log_2\\left(\\frac{n}{2}\\right)\\right\\rceil=\\mathcal{O}(n\\log n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c7\/73e\/bba\/4c773ebbad44af5ac97c8f4bec8f7a6f.svg\" width=\"461\" height=\"49\"\/><\/p>\n<h2>\u0422\u0435\u043e\u0440\u0435\u043c\u0430 \u21162<\/h2>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u0447\u0442\u043e \u043c\u044b \u0443\u043c\u0435\u0435\u043c \u043c\u0435\u043d\u044f\u0442\u044c \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438? \u041b\u0438\u0447\u043d\u043e \u044f \u043e\u0431\u044b\u0447\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u043b, \u0447\u0442\u043e \u044d\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0430 \u043a\u0430\u043a\u043e\u043c-\u043d\u0438\u0431\u0443\u0434\u044c \u043a\u043e\u043d\u0432\u0435\u0439\u0435\u0440\u0435 \u0433\u0434\u0435 \u043b\u044e\u0434\u0438 \u0437\u0430\u0447\u0435\u043c-\u0442\u043e \u0440\u0443\u043a\u0430\u043c\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u0435 \u0438 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0447\u0442\u043e-\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043a\u0440\u043e\u043c\u0435 \u043a\u0430\u043a \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439.<\/p>\n<p>\u0412 \u0442\u0430\u043a\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0432\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e <em>\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u0443\u0437\u044b\u0440\u044c\u043a\u043e\u043c \u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0434\u0435\u043b\u0430\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u0432\u043e\u043f\u043e\u0432. \u0415\u0441\u043b\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0441\u0434\u0435\u043b\u0430\u043b\u0430 m \u0441\u0432\u043e\u043f\u043e\u0432 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438\u0437 \u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 n+m-1.<\/em> <\/p>\n<p>\u0412\u043e\u0442 \u044d\u0442\u043e \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u0432 \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0434\u0435\u043b\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043f\u0443\u0437\u044b\u0440\u044c\u043a\u043e\u043c \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0439, \u0432 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u0432\u0441\u0435\u043c\u0435\u0441\u0442\u043d\u043e \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043a\u0430\u0440\u0442\u0438\u043d\u044b \u043f\u0440\u0438\u0432\u043e\u0436\u0443 \u043a\u043e\u0434 \u043e\u0431\u0435\u0438\u0445 (\u043a\u043e\u0434 \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0439, \u0432 \u043f\u0440\u043e\u0434\u0435 \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c)<\/p>\n<pre><code class=\"python\">def bubble_sort(array):     comparisons = 0     swaps = 0     for i in range(len(array) - 1):         for j in range(len(array) - 1 - i):             comparisons += 1             if array[j] &gt; array[j + 1]:                 swaps += 1                 array[j], array[j + 1] = array[j + 1], array[j]     return comparisons, swaps<\/code><\/pre>\n<pre><code class=\"python\">def insertion_sort(array):     comparisons = 0     swaps = 0          for i in range(0, len(array)):         j = i         while j &gt; 0 and array[j - 1] &gt; array[j]:             comparisons += 1             swaps += 1             array[j - 1], array[j] = array[j], array[j - 1]             j -= 1         if j &gt; 0:             comparisons += 1     return comparisons, swaps<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u043f\u0440\u043e\u0433\u043d\u0430\u0442\u044c insertion_sort \u043d\u0430 \u0443\u0436\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438\u0437 <em>n<\/em> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043d\u043e \u044d\u0442\u043e\u0442 \u043a\u043e\u0434 \u0432\u044b\u0434\u0430\u0441\u0442 n-1 comparisons \u0438 0 swaps. \u041f\u0443\u0437\u044b\u0440\u0435\u043a \u0436\u0435 \u0432\u044b\u0434\u0430\u0441\u0442 n(n-1)\/2 comparisons, \u0447\u0442\u043e \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435. <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043f\u043e\u043d\u044f\u0442\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0436\u0435 \u0438\u043c\u0435\u043d\u043d\u043e \u0441\u0432\u043e\u043f\u043e\u0432 \u0434\u0435\u043b\u0430\u044e\u0442 \u044d\u0442\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0438 \u043f\u043e\u0447\u0435\u043c\u0443 \u044d\u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0432\u043e\u043f\u043e\u0432 (\u043e\u043f\u044f\u0442\u044c \u0436\u0435 \u0432 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0435\u0441\u043b\u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0432\u043e\u043f\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445). \u041d\u0430\u043c \u0431\u0443\u0434\u0443\u0442 \u043d\u0443\u0436\u043d\u044b \u043f\u0430\u0440\u0430 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u0439.<\/p>\n<p><strong>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 2. <\/strong><em><u>\u0418\u043d\u0432\u0435\u0440\u0441\u0438\u0435\u0439<\/u><\/em> \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435<em> p <\/em>\u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0430\u044f \u043f\u0430\u0440\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0439 <code>i<\/code> \u0438 <code>j<\/code>, \u0447\u0442\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"i&lt;j, p_i&gt;p_j\" alt=\"i&lt;j, p_i&gt;p_j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/214\/ac4\/b8f\/214ac4b8fe9d5e54f5593748c9a2b9bd.svg\" width=\"108\" height=\"21\"\/><\/p>\n<p>\u0412\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u043d\u043d\u044b\u0445 \u0441\u0432\u043e\u043f\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u043e\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 &#8212; \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a. \u041f\u0440\u0435\u0436\u0434\u0435, \u0447\u0435\u043c \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u044d\u0442\u043e \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u044d\u0442\u043e\u043c<\/p>\n<details class=\"spoiler\">\n<summary>\u041a\u043e\u0434 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">def calc_inversions_simple(array):     result = 0     for i, x in enumerate(array):         for j in range(i + 1, len(array)):             if array[j] &lt; x:                 result += 1     return result  def calc_inversions_fast(array):     tree_size = 1     while tree_size &lt; len(array):         tree_size *= 2     tree_size = tree_size     tree = [0 for i in range(2 * tree_size)]          def tree_insert(i):         i += tree_size         while i &gt; 0:             tree[i] += 1             i \/\/= 2          def get_less_count(i):         if i == tree_size - 1:             return tree[1]         i += tree_size         result = 0         while i &gt; 0:             if i % 2 == 0:                 result += tree[i]             i = (i - 1) \/\/ 2         return result          pos = dict()     for i, x in enumerate(sorted(array)):         pos[x] = i              result = 0     for i in reversed(range(len(array))):         result += get_less_count(pos[array[i]])         tree_insert(pos[array[i]])     return result  def test_insertion_sort_versus_inversiond(array):     comparisons, swaps = insertion_sort(array)     print(f\"Inversions: {calc_inversions_fast(array)}\")     print(f\"Comparisons: {comparisons}\")     print(f\"Swaps:       {swaps}\")<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<p>\u0418\u0442\u0430\u043a \u0442\u0435\u043e\u0440\u0435\u043c\u0430 #2<\/p>\n<p><em>\u0414\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0432\u043e\u043f\u043e\u0432 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0434\u043b\u044f \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 p \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0435\u0439 \u0430 \u0432 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u044e\u0449\u0438\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a<\/em><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"a_{p_0}&lt;a_{p_1}&lt;\\ldots&lt;a_{p_{n-1}}\" alt=\"a_{p_0}&lt;a_{p_1}&lt;\\ldots&lt;a_{p_{n-1}}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ffa\/73d\/2a6\/ffa73d2a69de5d2361eb02318c98fa1e.svg\" width=\"189\" height=\"20\"\/><\/p>\n<p>\u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u043b\u0438\u0441\u044c \u0443\u043f\u0440\u043e\u0449\u0430\u044e\u0442 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 &#8212; \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430. \u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f: \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0441\u0432\u043e\u043f\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0442\u0430\u043a: \u043c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 0, 1, 2, &#8230;, n-1, \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0442\u044c \u0432 \u043d\u0435\u0439 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u0432 \u043a\u043e\u043d\u0446\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0443\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 <em>p. <\/em>\u0423 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 0. \u0415\u0441\u043b\u0438 \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c\u0441\u044f, \u0442\u043e \u043e\u0434\u043d\u0430 \u0437\u0430\u043c\u0435\u043d\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043b\u0438\u0431\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u043d\u0430 1, \u043b\u0438\u0431\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u043d\u0430 1 &#8212; \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u0441\u0440\u0430\u0437\u0443 \u0441\u043b\u0435\u0434\u0443\u0435\u0442, \u0447\u0442\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0447\u0435\u043c \u0437\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f. \u0412\u043e\u043f\u0440\u043e\u0441, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u043b\u0438 \u0440\u043e\u0432\u043d\u043e \u0437\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 \u044d\u0442\u043e\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0442.\u0435. \u0435\u0441\u043b\u0438 \u043c\u044b \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0432\u043e\u043f\u043e\u0432 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438\u0437 <em>p <\/em>\u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443, \u0442\u043e \u0432\u044b\u0431\u0438\u0440\u0430\u044f \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0430\u043a\u0438\u0435 \u0441\u0432\u043e\u043f\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u044e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439, \u043c\u044b \u0432 \u0438\u0442\u043e\u0433\u0435 \u043f\u0440\u0438\u0434\u0435\u043c \u043a \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0441 0 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 &#8212; \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439. \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0432\u0438\u043d\u0442\u0438\u043a \u0432 \u044d\u0442\u043e\u043c \u043f\u0430\u0437\u043b\u0435 &#8212; \u044d\u0442\u043e \u0442\u043e, \u0447\u0442\u043e \u0443 \u043b\u044e\u0431\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u043a\u0440\u043e\u043c\u0435 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0436\u043d\u0430 \u043d\u0430\u0439\u0442\u0438\u0441\u044c \u043f\u0430\u0440\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u044e, \u0441\u0432\u043e\u043f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439.<\/p>\n<p>\u041d\u0430\u043a\u043e\u043d\u0435\u0446 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f\u0441\u044c \u043e\u0442 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u043a \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u043c \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0441\u0432\u043e\u043f\u044b \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0445\u0441\u044f \u0432 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 &#8212; \u044d\u0442\u043e \u043a\u0430\u043a \u0440\u0430\u0437 &#171;\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435&#187; \u0441\u0432\u043e\u043f\u044b. \u0418\u0437 \u0442\u0435\u043e\u0440\u0435\u043c\u044b #2 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0442\u0430\u043a\u043e\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0435 \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435<\/p>\n<p><em>\u041b\u044e\u0431\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u043f\u043e \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0443 &#171;\u043f\u043e\u043a\u0430 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043b\u044e\u0431\u0443\u044e \u0442\u0430\u043a\u0443\u044e \u043f\u0430\u0440\u0443 \u0438 \u043c\u0435\u043d\u044f\u0435\u043c \u043c\u0435\u0441\u0442\u0430\u043c\u0438&#187;, \u0432\u0441\u0435\u0433\u0434\u0430 \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f \u0437\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0448\u0430\u0433\u043e\u0432, \u0440\u0430\u0432\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u0443 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0438 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a.<\/em><\/p>\n<p>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u0443\u0437\u044b\u0440\u0435\u043a \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043e\u0442\u043d\u043e\u0441\u044f\u0442\u0441\u044f \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0442\u0430\u043a\u043e\u0433\u043e \u0442\u0438\u043f\u0430, \u043d\u043e \u043f\u0443\u0437\u044b\u0440\u0435\u043a \u0442\u0440\u0430\u0442\u0438\u0442 \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043d\u0430 \u043f\u043e\u0438\u0441\u043a &#171;\u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445&#187; \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u0430\u0440. \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430 \u0432\u0441\u044f \u044d\u0442\u0430 \u0438\u0441\u0442\u043e\u0440\u0438\u044f \u0441 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u044f\u043c\u0438 \u0435\u0449\u0435 \u0442\u0435\u043c, \u0447\u0442\u043e \u0447\u0435\u043c \u0431\u043b\u0438\u0436\u0435 \u043a \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c\u0443 \u043f\u043e\u0440\u044f\u0434\u043a\u0443, \u0447\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0442\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438. \u0422\u0430\u043a\u043e\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 <em>\u0430\u0434\u0430\u043f\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c\u044e<\/em> &#8212; \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441 \u0442\u0430\u043a\u0438\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u043f\u043e\u043b\u0435\u0437\u043d\u044b \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0434\u0430\u043d\u043d\u044b\u0435 \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b. \u0418 \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0442\u0430\u043a\u0430\u044f \u043f\u043e\u043b\u0435\u0437\u043d\u0430\u044f.<\/p>\n<p>\u041d\u0430 \u041a\u0414\u041f\u0412 \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u043a\u043e\u0434 GCC \u043e\u0442\u0432\u0435\u0447\u0430\u044e\u0449\u0438\u0439 \u0437\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 std::sort. \u0412 GCC, MSVC \u0438 Clang \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043e\u0434\u043d\u0430 \u0438 \u0442\u0430 \u0436\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430:<\/p>\n<ul>\n<li>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c quicksort<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0443 quicksort \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u043c\u043d\u043e\u0433\u043e \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u0432\u044b\u0437\u043e\u0432\u043e\u0432 &#8212; \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0430\u0435\u043c\u0441\u044f \u043d\u0430 heapsort<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u043b\u043e\u043a\u0430 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0439 &#8212; \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438<\/p>\n<\/li>\n<\/ul>\n<p>\u041a\u0430\u0436\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0432\u044b\u0435 \u043a \u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0438\u0448\u043b\u0438 LLVM, \u043f\u043e\u0442\u043e\u043c \u043f\u043e\u0434\u0445\u0432\u0430\u0442\u0438\u043b\u0438 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435, LLVM \u0441\u0443\u0434\u044f \u043f\u043e \u0432\u0441\u0435\u043c\u0443 \u0432\u043f\u0435\u0440\u0435\u0434\u0438 \u043f\u043b\u0430\u043d\u0435\u0442\u044b \u0432\u0441\u0435\u0439, \u0443 \u043d\u0438\u0445 \u0442\u0430\u043c \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u0431\u044b\u043b \u043b\u044e\u0442\u0435\u0439\u0448\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f &#8212; \u0432\u044b\u0436\u0430\u043b\u0438 2-3% \u043d\u0430\u0439\u0434\u044f \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u0441\u0435\u0442\u0438 \u0434\u043b\u044f \u0431\u043b\u043e\u043a\u043e\u0432 <a href=\"https:\/\/github.com\/llvm\/llvm-project\/commit\/194d1965d2c841fa81e107d19e27fae1467e7f11\" rel=\"noopener noreferrer nofollow\">\u0440\u0430\u0437\u043c\u0435\u0440\u0430 3 \u0438 5<\/a> \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e AlphaDev.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 \u043a\u043e\u0434 <a href=\"https:\/\/github.com\/microsoft\/STL\/blob\/main\/stl\/inc\/algorithm#L8595\" rel=\"noopener noreferrer nofollow\">std::sort \u0432 MSVC<\/a>, \u0442\u043e \u043b\u0435\u0433\u043a\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435 \u043b\u043e\u0433\u0438\u043a\u0443. \u0410 \u0432\u043e\u0442 \u0432 <a href=\"https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/stl_algo.h#L1884\" rel=\"noopener noreferrer nofollow\">GCC<\/a> \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0435\u0435: \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0438\u0434\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u043e\u0442 Introsort, \u0430 \u043d\u0435 \u0432\u043d\u0443\u0442\u0440\u0438 \u043d\u0435\u0451. \u041a\u0430\u043a \u0442\u0430\u043a? \u042d\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u043e\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0430\u0434\u0430\u043f\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0438 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u0440\u0430\u0431\u043e\u0442\u044b quicksort: \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0437\u0434\u0435\u0441\u044c <a href=\"https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/stl_algo.h#L1864\" rel=\"noopener noreferrer nofollow\">\u043d\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u0442 \u0431\u043b\u043e\u043a\u0438 \u043c\u0435\u043d\u044c\u0448\u0435 16<\/a>, \u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u0435\u0442 \u0438\u0445. \u041d\u043e \u043f\u043e \u0443\u0441\u0442\u0440\u043e\u0439\u0441\u0442\u0432\u0443 \u0431\u044b\u0441\u0442\u0440\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043d\u0435\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0431\u043b\u043e\u043a\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u043e\u0441\u0442\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0442\u0435\u0445 \u0436\u0435 \u043c\u0435\u0441\u0442\u0430\u0445, \u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0437\u0430 \u0441\u0447\u0435\u0442 \u0441\u0432\u043e\u0435\u0439 \u0430\u0434\u0430\u043f\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u044d\u0442\u0438 \u0431\u043b\u043e\u043a\u0438 \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0451\u0442. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432 \u0438\u0442\u043e\u0433\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b MSVC \u0438 GCC \u0434\u0435\u043b\u0430\u044e\u0442 \u043e\u0434\u043d\u043e \u0438 \u0442\u043e\u0436\u0435. \u041a\u0430\u043a\u043e\u0439 \u0438\u0437 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u043b\u0443\u0447\u0448\u0435 &#8212; \u043d\u0430\u0434\u043e \u0437\u0430\u043c\u0435\u0440\u044f\u0442\u044c. \u0412\u0440\u043e\u0434\u0435 \u043a\u0430\u043a \u0441 \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b GCC \u0434\u0435\u043b\u0430\u0435\u0442 \u043b\u0438\u0448\u043d\u0438\u0439 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0440\u043e\u0445\u043e\u0434, \u043d\u043e \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u0437\u0430 \u0441\u0447\u0435\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043c\u044b \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0432\u0435\u0441\u044c \u043c\u0430\u0441\u0441\u0438\u0432, \u0430 \u043d\u0435 \u0435\u0433\u043e \u043e\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043a\u0443\u0441\u043e\u0447\u043a\u0438, \u043f\u0440\u043e\u0449\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<h2>\u0422\u0435\u043e\u0440\u0435\u043c\u0430 \u21163<\/h2>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u0447\u0442\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0432\u043e\u043f \u043b\u044e\u0431\u044b\u0445 \u0434\u0432\u0443\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0430 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445, \u043d\u043e \u043e\u043d \u0434\u043e\u0440\u043e\u0433\u043e\u0439. \u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u043c\u044b \u043a\u0430\u043a-\u0442\u043e \u043f\u043e\u043c\u0435\u043d\u044c\u0448\u0435 \u0438\u0445 \u0434\u0435\u043b\u0430\u0442\u044c? \u0418 \u043a\u0430\u043a \u043f\u043e\u043d\u044f\u0442\u044c \u0437\u0430 \u043a\u0430\u043a\u043e\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u0432\u043e\u043f\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u043f\u0443\u0441\u0442\u044c \u0434\u0430\u0436\u0435 \u0441\u0434\u0435\u043b\u0430\u0432 \u043f\u043e\u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439?<\/p>\n<p>\u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u0432\u043e\u043f\u043e\u0432 \u043d\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438\u0437 <em>n <\/em>\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442\u044c n-1, \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u044d\u0442\u043e\u0439 \u043e\u0446\u0435\u043d\u043a\u0438 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442: \u043d\u0430\u0448\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0443\u043c &#8212; \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0441\u0440\u0435\u0434\u0438 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0445\u0441\u044f \u043d\u0430\u0448\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0443\u043c &#8212; \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u0435 \u043c\u0435\u0441\u0442\u043e \u0438 \u0442.\u0434. <\/p>\n<pre><code class=\"python\">def selection_sort(array):     comparisons = 0     swaps = 0     for i in range(len(array) - 1):         mini = i         for j in range(len(array) - i - 1):             comparisons += 1             if array[mini] &gt; array[j + i + 1]:                 mini = j + i + 1                      if i != mini:             swaps += 1             array[mini], array[i] = array[i], array[mini]     return comparisons, swaps<\/code><\/pre>\n<p>\u041d\u043e \u0432\u043e\u0442 \u0432\u0441\u0435-\u0442\u0430\u043a\u0438 \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0432\u043e\u043f\u0440\u043e\u0441, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043c\u0435\u043d\u044c\u0448\u0435? \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u043b\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0441\u0432\u043e\u043f\u043e\u0432 \u043d\u0435 \u043d\u0430\u0434\u043e \u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u043d\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043d\u0435 \u0441\u0434\u0435\u043b\u0430\u0435\u0442, \u0430 \u0447\u0442\u043e \u043f\u043e \u043f\u043e\u0432\u043e\u0434\u0443 \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445? \u0421\u0445\u043e\u0434\u0443 \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e. <\/p>\n<p>\u0427\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043e\u043f\u044f\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c\u0441\u044f \u043a \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430\u043c, \u043d\u043e \u043f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u0438\u0441\u0442\u043e\u0440\u0438\u044f \u043a\u0430\u043a \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u21163 \u043f\u043e\u044f\u0432\u0438\u043b\u0430\u0441\u044c. \u041a\u0430\u043a-\u0442\u043e \u044f \u0434\u0430\u0432\u0430\u043b \u0440\u043e\u0432\u043d\u043e \u044d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u0441\u0442\u0430\u0440\u0448\u0435\u043a\u043b\u0430\u0441\u0441\u043d\u0438\u043a\u0430\u043c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0443\u043f\u0440\u0430\u0436\u043d\u0435\u043d\u0438\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438. \u041d\u0430 \u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442 \u0443 \u043c\u0435\u043d\u044f \u0431\u044b\u043b\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0447\u0438\u0441\u043b\u043e\u043c \u0441\u0432\u043e\u043f\u043e\u0432 &#8212; \u043e\u043d \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u043b\u0441\u044f \u0432 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0432\u0435\u0440\u0445 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a, \u043e \u043d\u0435\u043c \u0447\u0443\u0442\u044c \u043f\u043e\u0437\u0436\u0435. \u0422\u0430\u043a \u0432\u043e\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u043b\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430\u043c\u0438 &#8212; \u043e\u043d \u0431\u044b\u043b \u0441\u043b\u043e\u0436\u043d\u0435\u0435 \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f, \u0447\u0435\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c, \u043d\u043e \u0432\u0441\u0435-\u0442\u0430\u043a\u0438 \u043f\u043e \u0441\u0438\u043b\u0430\u043c \u0443\u0447\u0435\u043d\u0438\u043a\u0430\u043c. \u042f \u0431\u044b\u043b \u0447\u0435\u0441\u0442\u043d\u044b\u043c \u043f\u0440\u0435\u043f\u043e\u0434\u0430\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u0438 \u043d\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b &#171;\u0440\u043e\u0432\u043d\u043e \u0432\u043e\u0442 \u044d\u0442\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435&#187;, \u0435\u0441\u043b\u0438 \u0431\u044b \u0437\u0430\u0434\u0430\u0447\u0443 \u0440\u0435\u0448\u0438\u043b\u0438 \u043a\u0430\u043a-\u0442\u043e \u043f\u043e-\u0434\u0440\u0443\u0433\u043e\u043c\u0443 \u044f \u0431\u044b\u043b \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u0435 \u043f\u0440\u043e\u0442\u0438\u0432. \u0421\u0430\u043c\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u044b\u043b\u0430 \u0432 \u043e\u043b\u0438\u043c\u043f\u0438\u0430\u0434\u043d\u043e\u043c \u0444\u043e\u0440\u043c\u0430\u0442\u0435 \u0441 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0442\u0435\u0441\u0442\u043e\u0432, \u0447\u0442\u043e \u043f\u043e\u0447\u0442\u0438 \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0418 \u0432\u043e\u0442 \u0441\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c \u0442\u043e, \u0447\u0435\u0433\u043e \u044f \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043c\u043e\u0433 \u043e\u0436\u0438\u0434\u0430\u0442\u044c: \u0432\u0441\u0435 \u0443\u0447\u0435\u043d\u0438\u043a\u0438 \u0440\u0435\u0448\u0438\u043b\u0438 \u044d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 &#8230; \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c &#8212; \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435\u043c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0432\u044b\u0431\u043e\u0440\u043e\u043c. \u0421\u043a\u0440\u0438\u043f\u044f \u0437\u0443\u0431\u0430\u043c\u0438 \u044f \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043b \u0432\u0441\u0435\u043c \u043f\u044f\u0442\u0451\u0440\u043a\u0438 \u0438 \u043f\u043e\u0448\u0435\u043b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f, \u043f\u0440\u043e\u0432\u043e\u0437\u0438\u0432\u0448\u0438\u0441\u044c \u0434\u043e\u043b\u0433\u043e \u043d\u0430\u0434 \u044d\u0442\u0438\u043c \u044f \u0432 \u0438\u0442\u043e\u0433\u0435 \u0432 \u044d\u0439\u0444\u043e\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043d\u0430\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u043f\u0440\u0438\u0448\u0435\u043b \u043a \u0442\u0435\u043e\u0440\u0435\u043c\u0435 #3<\/p>\n<p><em>\u041f\u0440\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438\u0437 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u0434\u0435\u043b\u0430\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u0432\u043e\u043f\u043e\u0432<\/em><\/p>\n<p>\u042f \u043d\u0435 \u0443\u0432\u0435\u0440\u0435\u043d, \u0431\u0443\u0434\u0435\u0442 \u043b\u0438 \u043e\u043d\u0430 \u0432\u0441\u0451 \u0435\u0449\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0440\u0438 \u043d\u0430\u043b\u0438\u0447\u0438\u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u043e\u0432, \u043d\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u043b \u0438 \u043d\u0435 \u0443\u043c\u0435\u044e \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c. \u0418\u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043e\u0431\u044a\u0435\u043a\u0442<\/p>\n<p><strong>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 3. <\/strong><em><u>\u0426\u0438\u043a\u043b\u043e\u043c \u0434\u043b\u0438\u043d\u044b k<\/u> <\/em>\u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435<em> p <\/em>\u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"i_0, \\ldots, i_{k-1}\" alt=\"i_0, \\ldots, i_{k-1}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/928\/434\/c6b\/928434c6bee9c14e2cde5590892e6e9e.svg\" width=\"91\" height=\"20\"\/><\/p>\n<p>\u0442\u0430\u043a\u0430\u044f, \u0447\u0442\u043e<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"p_{i_j}=i_{j+1},~~p_{i_{k-1}}=i_0\" alt=\"p_{i_j}=i_{j+1},~~p_{i_{k-1}}=i_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2bf\/83d\/d8c\/2bf83dd8cc319bc1f9dc5e9e755f63d8.svg\" width=\"174\" height=\"22\"\/><\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"1, 5, 4, 3, 2, 0\" alt=\"1, 5, 4, 3, 2, 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/256\/e64\/cf1\/256e64cf161937b2f556431da1c99dbe.svg\" width=\"101\" height=\"20\"\/><\/p>\n<p>\u0422\u0440\u0438 \u0446\u0438\u043a\u043b\u0430 [1, 5, 0], [3] \u0438 [2, 4].<\/p>\n<p><strong>\u041b\u0435\u043c\u043c\u0430.<\/strong> <em>\u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430<\/em><\/p>\n<p>\u0414\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0435: \u0431\u0435\u0440\u0435\u043c \u043a\u0430\u043a\u0443\u044e \u043d\u0438\u0431\u0443\u0434\u044c \u043f\u043e\u0437\u0438\u0446\u0438\u044e <em>i  <\/em>\u0438 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"i\\rightarrow p_i\" alt=\"i\\rightarrow p_i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/361\/ae6\/91b\/361ae691bf30012f78af40d2ad32fb64.svg\" width=\"53\" height=\"19\"\/><\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0432 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043c\u043e\u043c\u0435\u043d\u0442 \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u043e\u043f\u0430\u0441\u0442\u044c \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u044e, \u0433\u0434\u0435 \u0443\u0436\u0435 \u0431\u044b\u043b\u0438. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u043d\u0435 \u0441 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0435\u0439, \u0442\u043e \u0442\u043e\u0433\u0434\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 &#8212; \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0435 \u0431\u044b\u0432\u0430\u0435\u0442, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0432\u0442\u043e\u0440 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043d\u0430 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438. \u042d\u0442\u043e\u0442 \u0436\u0435 \u0446\u0438\u043a\u043b \u043c\u044b \u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0435\u0441\u043b\u0438 \u0431\u044b \u043d\u0430\u0447\u0430\u043b\u0438 \u0438\u0437 \u043b\u044e\u0431\u043e\u0433\u043e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u043f\u0440\u043e\u0448\u043b\u0438. \u041d\u0430\u0447\u0430\u0432 \u0438\u0437 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435 \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u0446\u0438\u043a\u043b\u0430 \u0432 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0439 \u0446\u0438\u043a\u043b \u043c\u044b \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0451\u043c \u0438\u0437 \u0442\u0435\u0445 \u0436\u0435 \u0441\u043e\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439, \u0447\u0442\u043e \u044d\u0442\u043e \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u043b\u043e \u0431\u044b \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b. \u0415\u0441\u043b\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0446\u0438\u043a\u043b\u044b, \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430\u0447\u0430\u043b\u043e\u043c, \u043d\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u0435 \u0438\u0437 \u043e\u0434\u043d\u0438\u0445 \u0438 \u0442\u0435\u0445 \u0436\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u043b\u0435\u043c\u043c\u044b.<\/p>\n<p>\u0422\u0430\u043a, \u043d\u0443 \u0445\u043e\u0440\u043e\u0448\u043e, \u0430 \u043a\u0430\u043a \u043d\u0430\u043c \u044d\u0442\u0438 \u0446\u0438\u043a\u043b\u044b \u043f\u043e\u043c\u043e\u0433\u0443\u0442? \u041c\u043e\u0436\u043d\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0443 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0438\u0437 <em>n <\/em>\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0440\u043e\u0432\u043d\u043e <em>n <\/em>\u0446\u0438\u043a\u043b\u043e\u0432 \u0438 \u044d\u0442\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0441 <em>n<\/em> \u0446\u0438\u043a\u043b\u0430\u043c\u0438. \u0412\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u0443\u0436\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u0434\u043e\u0433\u0430\u0434\u0430\u0442\u044c\u0441\u044f \u043a \u0447\u0435\u043c\u0443 \u0432\u0441\u0435 \u0438\u0434\u0435\u0442. \u0411\u043e\u043b\u0435\u0435 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u21163 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a<\/p>\n<p><em>\u0415\u0441\u043b\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 p \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0430 \u0434\u043b\u0438\u043d\u044b n \u0438\u043c\u0435\u0435\u0442 k \u0446\u0438\u043a\u043b\u043e\u0432, \u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u0432\u043e\u043f\u043e\u0432, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u0434\u043b\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 &#8212; \u044d\u0442\u043e n-k \u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u0434\u0435\u043b\u0430\u0435\u0442 \u0440\u043e\u0432\u043d\u043e n-k \u0441\u0432\u043e\u043f\u043e\u0432.<\/em><\/p>\n<p>\u0414\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e \u0441\u0445\u043e\u0436\u0435 \u0441 \u0442\u0435\u043e\u0440\u0435\u043c\u043e\u0439 \u21162, \u043d\u043e \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0446\u0438\u043a\u043b\u043e\u043c \u0432\u043c\u0435\u0441\u0442\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439. \u041b\u044e\u0431\u043e\u0439 \u0441\u0432\u043e\u043f \u043b\u0438\u0431\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0438\u043a\u043b\u043e\u0432 \u043d\u0430 1, \u043b\u0438\u0431\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u043d\u0430 1. \u041a\u043e\u0433\u0434\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u0434\u0435\u043b\u0430\u0435\u0442 \u0441\u0432\u043e\u043f, \u0442\u043e \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0438\u0437 \u0446\u0438\u043a\u043b\u043e\u0432 \u0434\u043b\u0438\u043d\u0430 l&gt;1 \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u0446\u0438\u043a\u043b \u0434\u043b\u0438\u043d\u044b l-1 \u0438 \u0446\u0438\u043a\u043b \u0434\u043b\u0438\u043d\u044b 1, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0438\u043a\u043b\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 1. \u0414\u0435\u0442\u0430\u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044e \u0434\u043e\u0434\u0443\u043c\u0430\u0442\u044c \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u043e \u0435\u0441\u043b\u0438 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u043e\u0441\u0442\u0430\u0432\u043b\u044e \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u044b\u0439 \u0430\u043d\u0433\u043b\u043e\u044f\u0437\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b.<\/p>\n<p>\u0414\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043a\u0430\u0440\u0442\u0438\u043d\u044b \u043f\u0440\u0438\u0432\u043e\u0436\u0443<\/p>\n<details class=\"spoiler\">\n<summary>\u041a\u043e\u0434 \u0434\u043b\u044f \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0446\u0438\u043a\u043b\u043e\u0432<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">def decompose_cycles(permutation):     n = len(permutation)     marked = [False for x in permutation]     cycles = []     for x in permutation:         if x &lt; 0 or x &gt;= n:             return \"Not a permutation\"      for i, x in enumerate(permutation):         if marked[x]:             continue         marked[x] = True         cur = permutation[x]         cycle = [x]         while cur != x:             if marked[cur]:                 return \"Not a permutation\"             marked[cur] = True             cycle.append(cur)             cur = permutation[cur]         cycles.append(cycle)              return cycles  def calc_minimum_number_of_swaps(array):     pos = dict()     for i, x in enumerate(sorted(array)):         pos[x] = i        num_cycles = len(decompose_cycles([pos[x] for x in array]))     return len(array) - num_cycles  def test_selection_sort_versus_cycles(array):     expected_swaps = calc_minimum_number_of_swaps(array)     comparisons, swaps = selection_sort(array)     \/\/ expected_swaps should equals swaps<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<p>\u042d\u0442\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043c\u0435\u043d\u044f \u0432\u043f\u043e\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0438 \u0441\u0442\u0430\u043b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0432\u043e\u0442 \u0432 \u043a\u0430\u043a\u043e\u043c \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435. \u042f \u0447\u0430\u0441\u0442\u043e \u0441\u043b\u044b\u0448\u0443 \u043e\u0442 \u043b\u044e\u0434\u0435\u0439 \u0447\u0442\u043e-\u0442\u043e \u0432 \u0434\u0443\u0445\u0435: &#171;\u0411\u043b\u0438\u043d, \u044f \u0432\u043e\u0442 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u0438\u0437\u0443\u0447\u0430\u043b \u0432\u043e\u0442 <em>\u044d\u0442\u0443 \u0445\u0440\u0435\u043d\u044c<\/em> \u0438 \u043e\u043d\u0430 \u043c\u043d\u0435 \u043f\u043e\u0442\u043e\u043c \u0432 \u0436\u0438\u0437\u043d\u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u043b\u0430\u0441\u044c&#187;. \u0412\u044b\u0448\u0435\u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0434\u0440\u0443\u0433\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043d\u0430 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e. \u0412\u044b\u0441\u043e\u043a\u0430 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c, \u0447\u0442\u043e \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0412\u0430\u0448\u0443 \u043d\u0435\u043b\u044e\u0431\u043e\u0432\u044c \u043a <em>\u044d\u0442\u043e\u0439 \u0445\u0440\u0435\u043d\u0438<\/em>, \u0443 \u0412\u0430\u0441 \u0442\u0430\u043a\u0438 \u0431\u044b\u043b\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c <em>\u044d\u0442\u0443 \u0445\u0440\u0435\u043d\u044c<\/em> \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c, \u043d\u043e \u043e\u043d\u0430 \u043f\u0440\u043e\u0448\u043b\u0430 \u0443 \u0432\u0430\u0441 \u043f\u0440\u044f\u043c\u043e \u043f\u043e\u0434 \u043d\u043e\u0441\u043e\u043c, \u0430 \u0412\u044b \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0437\u0430\u043c\u0435\u0442\u0438\u043b\u0438 \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u043b\u043e\u0445\u043e <em>\u044d\u0442\u0443 \u0445\u0440\u0435\u043d\u044c<\/em> \u043f\u043e\u043d\u0438\u043c\u0430\u043b\u0438.<\/p>\n<h2>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h2>\n<p>\u0422\u0435\u043e\u0440\u0435\u043c \u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u0445 \u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u043d\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u0438 \u0442\u0440\u0438 \u0437\u0430\u043f\u0430\u043b\u0438 \u043c\u043d\u0435 \u0432 \u0434\u0443\u0448\u0443 \u043f\u043e \u0440\u0430\u0437\u043d\u044b\u043c \u043f\u0440\u0438\u0447\u0438\u043d\u0430\u043c. \u041f\u0435\u0440\u0432\u0430\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u0434\u0430\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e\u0439, \u0432\u0442\u043e\u0440\u0430\u044f \u0438 \u0442\u0440\u0435\u0442\u044c\u044f \u043f\u043e\u0434\u043c\u0435\u0447\u0430\u044e\u0442 \u043d\u0435\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0445 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043e\u043a. \u0412\u0441\u0435 \u0442\u0440\u0438 \u0437\u0430\u0442\u0440\u0430\u0433\u0438\u0432\u0430\u044e\u0442 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438, \u043d\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044f\u0445, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430\u043c\u0438. \u0418\u0437-\u0437\u0430 \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u0435 \u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u043e\u043d\u0438 \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u043e \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u044f\u044e\u0442 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0443\u0447\u0435\u0431\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430. \u0421\u0432\u043e\u044e \u043f\u0440\u0435\u043f\u043e\u0434\u0430\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0443\u044e \u0434\u0435\u044f\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432 \u0448\u043a\u043e\u043b\u0430\u0445 \u043d\u0430 \u043c\u043e\u043c\u0435\u043d\u0442 &#171;\u043e\u0442\u043a\u0440\u044b\u0442\u0438\u044f&#187; \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u21163 \u044f \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u043b, \u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0442\u043e\u0433\u0434\u0430 \u043a\u043e\u043b\u043b\u0435\u0433\u0430\u043c \u0445\u0432\u0430\u0441\u0442\u0430\u043b\u0441\u044f \u043e\u0431 \u044d\u0442\u043e\u043c. \u0421\u043f\u0443\u0441\u0442\u044f \u0432\u0440\u0435\u043c\u044f \u0431\u044b\u043b \u043f\u0440\u0438\u044f\u0442\u043d\u043e \u0443\u0434\u0438\u0432\u043b\u0435\u043d, \u043a\u043e\u0433\u0434\u0430 \u0437\u0430\u0439\u0434\u044f \u043d\u0430 \u0437\u0430\u0447\u0435\u0442 \u043f\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435 \u0434\u043b\u044f \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u043a\u043b\u0430\u0441\u0441\u043e\u0432  \u0443 \u043a\u043e\u043b\u043b\u0435\u0433 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432 \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 &#171;\u0422\u0440\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u0445&#187;.<\/p>\n<p>\u041d\u0443 \u0438 \u043d\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u043a, \u043f\u0438\u0448\u0438\u0442\u0435 \u043d\u0430\u0434\u0451\u0436\u043d\u044b\u0435 \u0442\u0435\u0441\u0442\u044b, \u043c\u043e\u0442\u0438\u0432\u0438\u0440\u0443\u0439\u0442\u0435 \u043b\u044e\u0434\u0435\u0439 \u043f\u0440\u043e\u044f\u0432\u043b\u044f\u0442\u044c \u0442\u0432\u043e\u0440\u0447\u0435\u0441\u043a\u0443\u044e \u043d\u0430\u0442\u0443\u0440\u0443, \u0430 \u043d\u0435 &#171;\u043d\u0435\u0442, \u044f \u0445\u043e\u0447\u0443, \u0447\u0442\u043e\u0431\u044b \u0412\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u0432\u043e\u0442 \u0442\u0430\u043a\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u0430 \u043d\u0435 \u044d\u0442\u0438\u043c&#187;, \u0438 \u0442\u043e\u0433\u0434\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0438 \u0412\u0430\u0441 \u0436\u0434\u0443\u0442 \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0442\u043a\u0440\u044b\u0442\u0438\u044f \ud83d\ude42 \u0423\u0441\u043f\u0435\u0445\u043e\u0432!<\/p>\n<p>\u0421\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e\u0435 \u0438 \u0431\u043e\u043b\u0435\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0432\u044b\u0448\u0435\u0438\u0437\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0433\u043e \u0441 \u043a\u043e\u0434\u043e\u043c<\/p>\n<p><a href=\"https:\/\/github.com\/Malkovsky\/interactive-visualization\/blob\/master\/examples\/sorts.ipynb\" rel=\"noopener noreferrer nofollow\">https:\/\/github.com\/Malkovsky\/interactive-visualization\/blob\/master\/examples\/sorts.ipynb<\/a><\/p>\n<h2>P. S.<\/h2>\n<p>\u041c\u0435\u043d\u044f \u0442\u0430\u043a\u0438 \u0442\u043e\u0436\u0435 \u043f\u043e\u043a\u0443\u0441\u0430\u043b\u0438 \u0431\u043b\u043e\u0433\u0435\u0440\u044b, \u0438 \u044f \u0441\u0430\u043c \u0442\u0430\u043a\u0438\u043c \u0441\u0442\u0430\u043b<\/p>\n<details class=\"spoiler\">\n<summary>\u0420\u0435\u043a\u043b\u0430\u043c\u0430 \u0441\u0432\u043e\u0435\u0433\u043e \u0422\u0413<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0421\u043e\u0432\u0441\u0435\u043c \u043d\u0435\u0434\u0430\u0432\u043d\u043e <a href=\"https:\/\/t.me\/a_nahui_eto_nuzhno\" rel=\"noopener noreferrer nofollow\">\u0437\u0430\u0432\u0435\u043b \u0422\u0413<\/a> \u0441 \u0446\u0435\u043b\u044c\u044e \u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u043e \u0442\u043e, \u0447\u0442\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u0443\u043c\u0435\u044e &#8212; \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b\/\u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443.<\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/893452\/\"> https:\/\/habr.com\/ru\/articles\/893452\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\">\n<div><figcaption>\u041f\u043e\u0433\u043e\u0434\u0438, \u0447\u0442\u043e? GCC std::sort \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438? WTF???<\/figcaption><\/div>\n<\/figure>\n<p>\u042f \u0437\u043d\u0430\u044e \u043c\u043d\u043e\u0433\u0438\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432 \u0438 \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u0439 \u0432 IT \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u044f\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u0434\u043e\u043b\u044e\u0431\u043b\u0438\u0432\u0430\u044e\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0432 \u0438 \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u0447\u0438\u0442\u0430\u044e\u0442 \u0438\u0445 \u0434\u0430\u043b\u0451\u043a\u0438\u043c\u0438 \u043e\u0442 \u0436\u0438\u0437\u043d\u0438 \u0438\u0434\u0438\u043e\u0442\u0430\u043c\u0438 \u0438\u0437-\u0437\u0430 \u0438\u0445 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0439 \u0432 \u0434\u0443\u0445\u0435 &#171;\u043d\u0435\u043b\u044c\u0437\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0437\u0430 nlogn&#187; &#8212; \u0432\u0435\u0434\u044c \u044d\u0442\u043e \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0435\u0432\u0435\u0440\u043d\u043e, \u0435\u0441\u0442\u044c \u0436\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u043e\u043c \u0438 radix sort. \u041d\u044e\u0430\u043d\u0441 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0435 \u0432\u044b\u0448\u0435 &#8212; \u044d\u0442\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u0430\u044f \u043d\u0435\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0430\u044f \u0442\u0440\u0430\u043a\u0442\u043e\u0432\u043a\u0430 \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0445 \u0442\u0435\u043e\u0440\u0435\u043c \u043e\u0431 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043e\u043a, \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a: &#171;\u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u043b \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 <em>n<\/em> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0443\u044e \u043a \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u044e\u0449\u0435\u043c\u0443 \u043f\u043e\u0440\u044f\u0434\u043a\u0443, \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0447\u0435\u043c \u0437\u0430 nlogn <strong>\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0433\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f<\/strong>&#171;. \u0412 \u044d\u0442\u043e\u043c \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u043b\u043e\u0432, \u043e\u043d\u043e \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u043e \u0432 \u043f\u043b\u0430\u043d\u0435 \u043a\u043e\u0433\u043d\u0438\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u044f\u0442\u0438\u044f, \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043b \u0436\u0438\u0440\u043d\u044b\u043c \u0448\u0440\u0438\u0444\u0442\u043e\u043c, \u0447\u0443\u0432\u0441\u0442\u0432\u0443\u0435\u0442\u0435 \u0440\u0430\u0437\u043d\u0438\u0446\u0443?<\/p>\n<p>\u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0445\u043e\u0447\u0443 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u043e\u0431 \u044d\u0442\u043e\u0439 \u0442\u0435\u043e\u0440\u0435\u043c\u0435 \u0438 \u0435\u0449\u0451 \u043e \u0434\u0432\u0443\u0445, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u043d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043a\u043e\u0433\u0434\u0430 \u0432\u0435\u043b \u0437\u0430\u043d\u044f\u0442\u0438\u044f \u043f\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435 \u0432 9-11 \u043a\u043b\u0430\u0441\u0441\u0430\u0445 \u0431\u0443\u0434\u0443\u0447\u0438 \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u043c \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u043a\u0443\u0440\u0441\u043e\u0432. \u042d\u0442\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0434\u043b\u044f \u043c\u0435\u043d\u044f \u0431\u044b\u043b\u0438 \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u043e\u0442\u043a\u0440\u044b\u0442\u0438\u0435\u043c, \u0440\u0430\u0434\u043e\u0432\u0430\u043b\u0441\u044f \u0432\u043d\u0435 \u0441\u0435\u0431\u044f \u043a\u043e\u0433\u0434\u0430 \u0432\u044b\u0432\u0435\u043b \u0441\u0430\u043c \u043e\u0434\u043d\u0443 \u0438\u0437 \u043d\u0438\u0445 &#8212; \u0435\u0451 \u044f \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u043b \u043d\u0438 \u0432 \u043e\u0434\u043d\u043e\u043c \u0443\u0447\u0435\u0431\u043d\u0438\u043a\u0435 \u043f\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u043a\u0435. \u0412 \u043f\u043e\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0438 \u0432\u0441\u0435 \u0442\u0440\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0431\u044b\u043b\u0438 \u043d\u0430\u0439\u0434\u0435\u043d\u044b \u0432 \u043d\u0435\u0434\u0440\u0430\u0445 \u041a\u043d\u0443\u0442\u0430, \u043d\u043e \u0447\u0451\u0440\u0442 \u043f\u043e\u0431\u0435\u0440\u0438, \u0438\u0445 \u043f\u043e\u0438\u0441\u043a \u0431\u044b\u043b \u0441\u043b\u043e\u0436\u043d\u0435\u0435, \u0447\u0435\u043c \u0432\u044b\u0432\u043e\u0434!<\/p>\n<p>\u0415\u0441\u043b\u0438 \u044f \u0435\u0449\u0451 \u043d\u0435 \u0443\u0431\u0435\u0434\u0438\u043b \u0412\u0430\u0441 \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e, \u0442\u043e \u0432\u043e\u0442 \u043c\u043e\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044f\u044f \u043f\u043e\u043f\u044b\u0442\u043a\u0430: \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u044e \u043f\u043e\u0447\u0435\u043c\u0443 \u043f\u0443\u0437\u044b\u0440\u0451\u043a &#8212; \u044d\u0442\u043e \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u0430\u044f \u0444\u0438\u0433\u043d\u044f, \u043d\u043e \u0432\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0442\u0430\u043a\u0436\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 &#8212; \u044d\u0442\u043e \u0441\u0443\u043f\u0435\u0440 \u0432\u0430\u0436\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430, \u044f\u0432\u043b\u044f\u044e\u0449\u0430\u044f\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e std::sort \u0432 MSVC, GCC \u0438 Clang. \u0420\u0430\u0441\u0441\u043a\u0430\u0436\u0443, \u043a\u0430\u043a\u0438\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u044b\u0431\u043e\u0440\u043e\u043c, \u044f\u0432\u043b\u044f\u044e\u0449\u0430\u044f\u0441\u044f \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u043a\u0430\u043a \u043f\u0443\u0437\u044b\u0440\u0451\u043a.<\/p>\n<h2>\u0422\u0435\u043e\u0440\u0435\u043c\u0430 \u21161<\/h2>\n<p>\u0417\u0434\u0435\u0441\u044c \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0441\u044e\u0440\u043f\u0440\u0438\u0437\u043e\u0432 &#8212; \u0442\u0430 \u0441\u0430\u043c\u0430\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u043f\u0440\u043e nlogn, \u043d\u043e \u0432\u0441\u0451-\u0442\u0430\u043a\u0438 \u044f \u0435\u0451 \u0440\u0430\u0441\u043f\u0438\u0448\u0443 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e, \u043d\u0430 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043a\u0430\u0440\u0442\u0438\u043d\u044b<\/p>\n<p><strong>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 1. <\/strong><em><u>\u041f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u043e\u0439 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 n<\/u><\/em> \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c <\/p>\n<p>\u041d\u0435\u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 &#8212; \u044d\u0442\u043e \u0432\u0437\u044f\u043b\u0438 0, 1, &#8230; , n-1 \u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u0430\u043b\u0438. \u0412 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u0445 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u0443\u0434\u043e\u0431\u043d\u043e \u0438\u0437\u0443\u0447\u0430\u0442\u044c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043e\u043a: \u043f\u043e \u0441\u0443\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u0443\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0434\u0430\u0451\u0442 \u043d\u0435\u0443\u0431\u044b\u0432\u0430\u044e\u0449\u0438\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a. \u0422\u0435\u043f\u0435\u0440\u044c \u043c\u044b \u0433\u043e\u0442\u043e\u0432\u044b \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0435\u043e\u0440\u0435\u043c\u0443<\/p>\n<p><em>\u041d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u0438\u043d\u044b n<\/em><\/p>\n<p><em>\u043d\u0430\u0445\u043e\u0434\u0438\u043b \u0431\u044b \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 p \u0442\u0430\u043a\u0443\u044e, \u0447\u0442\u043e<\/em><\/p>\n<p><em>\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c<\/em><\/p>\n<p><em>\u043f\u043e\u043f\u0430\u0440\u043d\u044b\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u0442.\u0435. \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0434\u0432\u0443\u0445 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/em><\/p>\n<p>\u0414\u043b\u044f \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430 \u044d\u0442\u043e\u0433\u043e \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044f \u044f \u043b\u044e\u0431\u043b\u044e \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u044e: \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0432\u044b \u0438\u0433\u0440\u0430\u0435\u0442\u0435 \u0432 \u0438\u0433\u0440\u0443 \u0441\u043e \u0441\u0432\u043e\u0438\u043c \u043a\u043e\u043b\u043b\u0435\u0433\u043e\u0439. \u041e\u043d \u0437\u0430\u0433\u0430\u0434\u044b\u0432\u0430\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0435\u0434\u043c\u0435\u0442, \u0430 \u0432\u044b \u0437\u0430\u0434\u0430\u0451\u0442\u0435 \u0432\u043e\u043f\u0440\u043e\u0441 \u043f\u0440\u043e \u044d\u0442\u043e\u0442 \u043f\u0440\u0435\u0434\u043c\u0435\u0442, \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0442\u0432\u0435\u0442 \u0434\u0430\/\u043d\u0435\u0442. \u0412\u0430\u0448\u0430 \u0446\u0435\u043b\u044c \u043e\u0442\u0433\u0430\u0434\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u043c\u0435\u0442. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u044d\u0442\u043e\u0439 \u0438\u0433\u0440\u044b \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a\u0430\u044f: \u0435\u0441\u0442\u044c \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>\u0425<\/em>, \u043f\u0435\u0440\u0432\u044b\u0439 \u0438\u0433\u0440\u043e\u043a \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>y<\/em>, \u0432\u0442\u043e\u0440\u043e\u0439 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u0434\u0430\u0432\u0430\u0442\u044c \u0432\u043e\u043f\u0440\u043e\u0441\u044b \u0432\u0438\u0434\u0430 &#171;\u041f\u0440\u0430\u0432\u0434\u0430, \u0447\u0442\u043e <em>y<\/em> \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0443 <em>A<\/em>?&#187;. \u0412\u043e\u043f\u0440\u043e\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u0442\u044c &#8212; \u043a\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f \u0432\u044b\u0431\u043e\u0440\u0430 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432\/\u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u0434\u043b\u044f \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0438\u0433\u0440\u043e\u043a\u0430 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u0442 \u043a \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432 \u0434\u043b\u044f \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 <em>y<\/em>?<\/p>\n<p>\u041e\u0442\u0432\u0435\u0442 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c: \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0443\u0436\u043d\u043e \u0437\u0430\u0434\u0430\u0442\u044c &#8212; \u044d\u0442\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 <em>X<\/em><\/p>\n<p>\u0418\u0434\u0435\u044f \u043f\u0440\u043e\u0441\u0442\u0430\u044f: \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u0437\u0430\u0434\u0430\u0451\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441 \u0432\u044b\u0431\u0440\u0430\u0432 \u043a\u0430\u043a\u043e\u0435-\u0442\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>A <\/em>\u043c\u044b \u0434\u0435\u043b\u0438\u043c <em>X<\/em> \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438: \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 <em>A<\/em> \u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0435 \u0438\u0437 <em>A.<\/em> \u041f\u043e\u043b\u0443\u0447\u0438\u0432 \u043e\u0442\u0432\u0435\u0442 \u043e\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0438\u0433\u0440\u043e\u043a\u0430 \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u043a \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u043d\u043e \u0443\u0436\u0435 \u043d\u0435 \u0441 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c <em>X<\/em>, \u0430 \u0441 <em>A<\/em> \u0438\u043b\u0438 <em>X\\A <\/em>(\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 <em>X<\/em> \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 <em>A<\/em>)<em>. <\/em>\u0412\u0440\u043e\u0434\u0435 \u0431\u044b \u0438\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u0447\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e, \u0442\u0435\u043c \u0441\u043b\u043e\u0436\u043d\u0435\u0435 \u0432 \u044d\u0442\u043e\u0439 \u0438\u0433\u0440\u0435 \u043d\u0430\u0439\u0442\u0438 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0432 \u043e\u0442\u0432\u0435\u0442 \u043c\u044b \u043e\u0441\u0442\u0430\u043d\u0435\u043c\u0441\u044f \u0441 \u0431\u041e\u043b\u044c\u0448\u0438\u043c \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c, \u0432\u0441\u0435 \u0447\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0439 \u0438\u0433\u0440\u043e\u043a &#8212; \u044d\u0442\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <em>A<\/em> \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u043e \u0434\u0435\u043b\u0438\u043b\u043e <em>X<\/em> \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u043e\u043f\u043e\u043b\u0430\u043c. \u0421 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0435\u0439 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0435\u0441\u0442\u044c <em>y <\/em>\u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430, \u0435\u0441\u043b\u0438 \u0431\u044b\u0442\u044c \u0442\u043e\u0447\u043d\u0435\u0435 \u0442\u043e \u0432\u0441\u0435 \u0442\u0430\u043a\u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a<\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 1, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f <em>y<\/em>, \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u0447\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u043e \u0447\u0442\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 &#8212; \u044d\u0442\u043e <em>y <\/em>\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0438 \u0438\u0441\u043a\u0430\u043b\u0438. \u0412 \u0438\u0442\u043e\u0433\u0435 \u0438\u043c\u0435\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435: \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u0435\u0440\u0430 <em>n<\/em> \u043d\u0443\u0436\u043d\u043e \u0443\u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0438\u0442\u044c (\u0438\u043b\u0438 \u0435\u0441\u043b\u0438 \u0431\u044b\u0442\u044c \u0442\u043e\u0447\u043d\u0435\u0435 \u0443\u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0438\u0442\u044c \u0441 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435\u043c \u0432\u0432\u0435\u0440\u0445), \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u043e \u0441\u0442\u0430\u043b\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 1? \u042d\u0442\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438 \u0435\u0441\u0442\u044c <\/p>\n<p>\u041a\u0430\u043a \u0432\u0441\u0451 \u044d\u0442\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u043c, \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430\u043c \u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c\u0443 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044e? \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u044f \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043c\u044b \u043a\u043e\u0441\u0432\u0435\u043d\u043d\u043e \u0434\u0435\u043b\u0438\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 &#171;\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435&#187; \u0438 &#171;\u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435&#187;, \u043d\u0430 \u0442\u0430\u043a\u0438\u0435, \u0433\u0434\u0435 \u044d\u0442\u0438 \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043d\u0443\u0436\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0438 \u0442\u0435, \u0433\u0434\u0435 \u044d\u0442\u0438 \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0430 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u0442\u043e\u0447\u043d\u043e \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0435, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u043b\u043e\u0438\u043a\u0443 \u0438\u0437 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0438 &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c, &#8212; \u044d\u0442\u043e <\/p>\n<p>\u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u044d\u0442\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 &#8212; \u044d\u0442\u043e <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%A1%D1%82%D0%B8%D1%80%D0%BB%D0%B8%D0%BD%D0%B3%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0421\u0442\u0438\u0440\u043b\u0438\u043d\u0433\u0430<\/a>, \u043d\u043e \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0432\u043e\u0442 \u0442\u0430\u043a<\/p>\n<h2>\u0422\u0435\u043e\u0440\u0435\u043c\u0430 \u21162<\/h2>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e, \u0447\u0442\u043e \u043c\u044b \u0443\u043c\u0435\u0435\u043c \u043c\u0435\u043d\u044f\u0442\u044c \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438? \u041b\u0438\u0447\u043d\u043e \u044f \u043e\u0431\u044b\u0447\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u043b, \u0447\u0442\u043e \u044d\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0430 \u043a\u0430\u043a\u043e\u043c-\u043d\u0438\u0431\u0443\u0434\u044c \u043a\u043e\u043d\u0432\u0435\u0439\u0435\u0440\u0435 \u0433\u0434\u0435 \u043b\u044e\u0434\u0438 \u0437\u0430\u0447\u0435\u043c-\u0442\u043e \u0440\u0443\u043a\u0430\u043c\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u0435 \u0438 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0447\u0442\u043e-\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043a\u0440\u043e\u043c\u0435 \u043a\u0430\u043a \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u043c\u0435\u0441\u0442\u0430\u043c\u0438 \u0441\u043e\u0441\u0435\u0434\u0435\u0439.<\/p>\n<p>\u0412 \u0442\u0430\u043a\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0432\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e <em>\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u0443\u0437\u044b\u0440\u044c\u043a\u043e\u043c \u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0434\u0435\u043b\u0430\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441\u0432\u043e\u043f\u043e\u0432. \u0415\u0441\u043b\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0441\u0434\u0435\u043b\u0430\u043b\u0430 m \u0441\u0432\u043e\u043f\u043e\u0432 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438\u0437 \u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 n+m-1.<\/em> <\/p>\n<p>\u0412\u043e\u0442 \u044d\u0442\u043e \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u0432 \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u0434\u0435\u043b\u0430\u0435\u0442 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043f\u0443\u0437\u044b\u0440\u044c\u043a\u043e\u043c \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0439, \u0432 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u0432\u0441\u0435\u043c\u0435\u0441\u0442\u043d\u043e \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043a\u0430\u0440\u0442\u0438\u043d\u044b \u043f\u0440\u0438\u0432\u043e\u0436\u0443 \u043a\u043e\u0434 \u043e\u0431\u0435\u0438\u0445 (\u043a\u043e\u0434 \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0439, \u0432 \u043f\u0440\u043e\u0434\u0435 \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c)<\/p>\n<pre><code class=\"python\">def bubble_sort(array):     comparisons = 0     swaps = 0     for i in range(len(array) - 1):         for j in range(len(array) - 1 - i):             comparisons += 1             if array[j] &gt; array[j + 1]:                 swaps += 1                 array[j], array[j + 1] = array[j + 1], array[j]     return comparisons, swaps<\/code><\/pre>\n<pre><code class=\"python\">def insertion_sort(array):     comparisons = 0     swaps = 0          for i in range(0, len(array)):         j = i         while j &gt; 0 and array[j - 1] &gt; array[j]:             comparisons += 1             swaps += 1             array[j - 1], array[j] = array[j], array[j - 1]             j -= 1         if j &gt; 0:             comparisons += 1     return comparisons, swaps<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u043f\u0440\u043e\u0433\u043d\u0430\u0442\u044c insertion_sort \u043d\u0430 \u0443\u0436\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438\u0437 <em>n<\/em> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043d\u043e \u044d\u0442\u043e\u0442 \u043a\u043e\u0434 \u0432\u044b\u0434\u0430\u0441\u0442 n-1 comparisons \u0438 0 swaps. \u041f\u0443\u0437\u044b\u0440\u0435\u043a \u0436\u0435 \u0432\u044b\u0434\u0430\u0441\u0442 n(n-1)\/2 comparisons, \u0447\u0442\u043e \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435. <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043f\u043e\u043d\u044f\u0442\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0436\u0435 \u0438\u043c\u0435\u043d\u043d\u043e \u0441\u0432\u043e\u043f\u043e\u0432 \u0434\u0435\u043b\u0430\u044e\u0442 \u044d\u0442\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0438 \u043f\u043e\u0447\u0435\u043c\u0443 \u044d\u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0432\u043e\u043f\u043e\u0432 (\u043e\u043f\u044f\u0442\u044c \u0436\u0435 \u0432 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0435\u0441\u043b\u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0432\u043e\u043f\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445). \u041d\u0430\u043c \u0431\u0443\u0434\u0443\u0442 \u043d\u0443\u0436\u043d\u044b \u043f\u0430\u0440\u0430 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u0439.<\/p>\n<p><strong>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 2. <\/strong><em><u>\u0418\u043d\u0432\u0435\u0440\u0441\u0438\u0435\u0439<\/u><\/em> \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435<em> p <\/em>\u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0430\u044f \u043f\u0430\u0440\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0439 <code>i<\/code> \u0438 <code>j<\/code>, \u0447\u0442\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f<\/p>\n<p>\u0412\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u043d\u043d\u044b\u0445 \u0441\u0432\u043e\u043f\u043e\u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u043e\u0439 \u0432\u0441\u0442\u0430\u0432\u043a\u0430\u043c\u0438 &#8212; \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a. \u041f\u0440\u0435\u0436\u0434\u0435, \u0447\u0435\u043c \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u044d\u0442\u043e \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u044d\u0442\u043e\u043c<\/p>\n<details class=\"spoiler\">\n<summary>\u041a\u043e\u0434 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">def calc_inversions_simple(array):     result = 0     for i, x in enumerate(array):         for j in range(i + 1, len(array)):             if array[j] &lt; x:                 result += 1     return result  def calc_inversions_fast(array):     tree_size = 1     while tree_size &lt; len(array):         tree_size *= 2     tree_size = tree_size     tree = [0 for i in range(2 * tree_size)]          def tree_insert(i):         i += tree_size         while i &gt; 0:             tree[i] += 1             i \/\/= 2          def get_less_count(i):         if i == tree_size - 1:             return tree[1]         i += tree_size         result = 0         while i &gt; 0:             if i % 2 == 0:                 result += tree[i]             i = (i - 1) \/\/ 2         return result          pos = dict()     for i, x in enumerate(sorted(array)):         pos[x] = i              result = 0     for i in reversed(range(len(array))):         result += get_less_count(pos[array[i]])         tree_insert(pos[array[i]])     return result  def test_insertion_sort_versus_inversiond(array):     comparisons, swaps = insertion_sort(array)     print(f\"Inversions: {calc_inversions_fast(array)}\")     print(f\"Comparisons: {comparisons}\")     print(f\"Swaps:       {swaps}\")<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<p>\u0418\u0442\u0430\u043a \u0442\u0435\u043e\u0440\u0435\u043c\u0430 #2<\/p>\n<p><em>\u0414\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0432\u043e\u043f\u043e\u0432 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0434\u043b\u044f \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0432 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 p \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0449\u0435\u0439 \u0430 \u0432 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u044e\u0449\u0438\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a<\/em><\/p>\n<p>\u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u043b\u0438\u0441\u044c \u0443\u043f\u0440\u043e\u0449\u0430\u044e\u0442 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 &#8212; \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430. \u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0442\u044c\u0441\u044f: \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0441\u0432\u043e\u043f\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0442\u0430\u043a: \u043c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 0, 1, 2, &#8230;, n-1, \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0442\u044c \u0432 \u043d\u0435\u0439 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u0432 \u043a\u043e\u043d\u0446\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0449\u0443\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 <em>p. <\/em>\u0423 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 0. \u0415\u0441\u043b\u0438 \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c\u0441\u044f, \u0442\u043e \u043e\u0434\u043d\u0430 \u0437\u0430\u043c\u0435\u043d\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043b\u0438\u0431\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u043d\u0430 1, \u043b\u0438\u0431\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u043d\u0430 1 &#8212; \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u0441\u0440\u0430\u0437\u0443 \u0441\u043b\u0435\u0434\u0443\u0435\u0442, \u0447\u0442\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0447\u0435\u043c \u0437\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f. \u0412\u043e\u043f\u0440\u043e\u0441, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u043b\u0438 \u0440\u043e\u0432\u043d\u043e \u0437\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 \u044d\u0442\u043e\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0442.\u0435. \u0435\u0441\u043b\u0438 \u043c\u044b \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0432\u043e\u043f\u043e\u0432 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438\u0437 <em>p <\/em>\u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443, \u0442\u043e \u0432\u044b\u0431\u0438\u0440\u0430\u044f \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0430\u043a\u0438\u0435 \u0441\u0432\u043e\u043f\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u044e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439, \u043c\u044b \u0432 \u0438\u0442\u043e\u0433\u0435 \u043f\u0440\u0438\u0434\u0435\u043c \u043a \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0441 0 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439 &#8212; \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439. \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0432\u0438\u043d\u0442\u0438\u043a \u0432 \u044d\u0442\u043e\u043c \u043f\u0430\u0437\u043b\u0435 &#8212; \u044d\u0442\u043e \u0442\u043e, \u0447\u0442\u043e \u0443 \u043b\u044e\u0431\u043e\u0439 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u043a\u0440\u043e\u043c\u0435 \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0436\u043d\u0430 \u043d\u0430\u0439\u0442\u0438\u0441\u044c \u043f\u0430\u0440\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u044e, \u0441\u0432\u043e\u043f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u0439.<\/p>\n<p>\u041d\u0430\u043a\u043e\u043d\u0435\u0446 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f\u0441\u044c \u043e\u0442 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u043a \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430\u043c \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0441\u0432\u043e\u043f\u044b<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-452848","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/452848","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=452848"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/452848\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=452848"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=452848"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=452848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}