{"id":869,"date":"2017-04-13T15:52:37","date_gmt":"2017-04-13T23:52:37","guid":{"rendered":"http:\/\/www.tech.dimprash.com\/?p=869"},"modified":"2017-04-13T15:53:54","modified_gmt":"2017-04-13T23:53:54","slug":"sort-an-array-of-0s-1s-and-2s","status":"publish","type":"post","link":"http:\/\/www.tech.dimprash.com\/?p=869","title":{"rendered":"Sort an array of 0s, 1s and 2s"},"content":{"rendered":"<p>Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.<\/p>\n<p>Example<br \/>\nInput = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};<br \/>\nOutput = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}<\/p>\n<p>This is a variation of famous Dutch national flag problem<br \/>\nThe problem was posed with three colours, here `0?, `1? and `2?. The array is divided into four sections:<\/p>\n<p>a[1..Lo-1] zeroes (red)<br \/>\na[Lo..Mid-] ones (white)<br \/>\na[Mid..Hi] unknown<br \/>\na[Hi+1..N] twos (blue)<br \/>\nThe unknown region is shrunk while maintaining these conditions<\/p>\n<pre>\r\nLo := 1; Mid := 1; Hi := N;\r\nwhile Mid <= Hi do\r\nInvariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and \r\na[Hi+1..N]=2; a[Mid..Hi] are unknown.\r\n\r\ncase a[Mid] in\r\n0: swap a[Lo] and a[Mid]; Lo++; Mid++\r\n1: Mid++\r\n2: swap a[Mid] and a[Hi]; Hi\u2013\r\n<\/pre>\n<p>http:\/\/www.geeksforgeeks.org\/sort-an-array-of-0s-1s-and-2s\/<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last. Example Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}; Output = {0, 0, 0, 0, 0, 1, 1, 1, &hellip; <a href=\"http:\/\/www.tech.dimprash.com\/?p=869\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Sort an array of 0s, 1s and 2s<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-869","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/869","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=869"}],"version-history":[{"count":3,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/869\/revisions"}],"predecessor-version":[{"id":872,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/869\/revisions\/872"}],"wp:attachment":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=869"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=869"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=869"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}