{"id":25268,"date":"2017-10-15T16:57:55","date_gmt":"2017-10-15T11:27:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25268"},"modified":"2018-11-01T13:15:04","modified_gmt":"2018-11-01T07:45:04","slug":"sort-array-wave-form","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/sort-array-wave-form\/","title":{"rendered":"Sort an array in wave form"},"content":{"rendered":"<p><span style=\"color: #008080;\"><strong>Sort an array in wave form<\/strong><\/span><\/p>\n<p>Given an unsorted array of integers, sort the array into a wave like array. An <a href=\"https:\/\/www.wikitechy.com\/tutorials\/javascript\/sort-array-of-objects-by-string-property-value-in-javascript\" target=\"_blank\" rel=\"noopener\">array<\/a> \u2018arr[0..n-1]\u2019 is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= \u2026..<span id=\"more-133397\"><\/span><\/p>\n<h3 id=\"examples\"><span style=\"color: #003366;\"><strong>Examples:<\/strong><\/span><\/h3>\n<pre> Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}\r\n Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR\r\n                 {20, 5, 10, 2, 80, 6, 100, 3} OR\r\n                 any other array that is in wave form\r\n\r\n Input:  arr[] = {20, 10, 8, 6, 4, 2}\r\n Output: arr[] = {20, 8, 10, 4, 6, 2} OR\r\n                 {10, 8, 20, 2, 6, 4} OR\r\n                 any other array that is in wave form\r\n\r\n Input:  arr[] = {2, 4, 6, 8, 10, 20}\r\n Output: arr[] = {4, 2, 8, 6, 20, 10} OR\r\n                 any other array that is in wave form\r\n\r\n Input:  arr[] = {3, 6, 5, 10, 7, 20}\r\n Output: arr[] = {6, 3, 10, 5, 20, 7} OR\r\n                 any other array that is in wave form<\/pre>\n<p>A <strong>Simple Solution<\/strong> is to use sorting. First sort the input array, then swap all adjacent elements.<\/p>\n<p>For example, let the input array be {3, 6, 5, 10, 7, 20}. After <a href=\"https:\/\/www.wikitechy.com\/technology\/find-minimum-length-unsorted-subarray-sorting-makes-complete-array-sorted\/\" target=\"_blank\" rel=\"noopener\">sorting<\/a>, we get {3, 5, 6, 7, 10, 20}. After <a href=\"https:\/\/www.wikitechy.com\/tutorials\/c-programming\/swapping-of-two-numbers-in-c\" target=\"_blank\" rel=\"noopener\">swapping<\/a> adjacent elements, we get {5, 3, 7, 6, 20, 10}.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Below are implementations of this simple approach.<\/p>\n<h2 id=\"c-implementation-of-sort-an-array-in-wave-form\"><span style=\"color: #ff0000;\"><strong>C++ Implementation of\u00a0Sort an array in wave form:<\/strong><\/span><\/h2>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20C%2B%2B%20program%20to%20sort%20an%20array%20in%20wave%20form%20using%0A%2F%2F%20a%20sorting%20function%0A%23include%3Ciostream%3E%0A%23include%3Calgorithm%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20utility%20method%20to%20swap%20two%20numbers.%0Avoid%20swap(int%20*x%2C%20int%20*y)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*x%3B%0A%20%20%20%20*x%20%3D%20*y%3B%0A%20%20%20%20*y%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20sorts%20arr%5B0..n-1%5D%20in%20wave%20form%2C%20i.e.%2C%20%0A%2F%2F%20arr%5B0%5D%20%3E%3D%20arr%5B1%5D%20%3C%3D%20arr%5B2%5D%20%3E%3D%20arr%5B3%5D%20%3C%3D%20arr%5B4%5D%20%3E%3D%20arr%5B5%5D..%0Avoid%20sortInWave(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Sort%20the%20input%20array%0A%20%20%20%20sort(arr%2C%20arr%2Bn)%3B%0A%20%0A%20%20%20%20%2F%2F%20Swap%20adjacent%20elements%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-1%3B%20i%20%2B%3D%202)%0A%20%20%20%20%20%20%20%20swap(%26arr%5Bi%5D%2C%20%26arr%5Bi%2B1%5D)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B10%2C%2090%2C%2049%2C%202%2C%201%2C%205%2C%2023%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20sortInWave(arr%2C%20n)%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>2 1 10 5 49 23 90<\/pre>\n<h2 id=\"java-implementation-of-sort-an-array-in-wave-form\"><span style=\"color: #ff0000;\"><strong>JAVA\u00a0<\/strong><\/span><span style=\"color: #ff0000;\"><strong>Implementation of\u00a0Sort an array in wave form:<\/strong><\/span><\/h2>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20implementation%20of%20naive%20method%20for%20sorting%0A%2F%2F%20an%20array%20in%20wave%20form.%0Aimport%20java.util.*%3B%0A%20%0Aclass%20SortWave%0A%7B%0A%20%20%20%20%2F%2F%20A%20utility%20method%20to%20swap%20two%20numbers.%0A%20%20%20%20void%20swap(int%20arr%5B%5D%2C%20int%20a%2C%20int%20b)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Ba%5D%3B%0A%20%20%20%20%20%20%20%20arr%5Ba%5D%20%3D%20arr%5Bb%5D%3B%0A%20%20%20%20%20%20%20%20arr%5Bb%5D%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20This%20function%20sorts%20arr%5B0..n-1%5D%20in%20wave%20form%2C%20i.e.%2C%0A%20%20%20%20%2F%2F%20arr%5B0%5D%20%3E%3D%20arr%5B1%5D%20%3C%3D%20arr%5B2%5D%20%3E%3D%20arr%5B3%5D%20%3C%3D%20arr%5B4%5D..%0A%20%20%20%20void%20sortInWave(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Sort%20the%20input%20array%0A%20%20%20%20%20%20%20%20Arrays.sort(arr)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Swap%20adjacent%20elements%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn-1%3B%20i%20%2B%3D%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20swap(arr%2C%20i%2C%20i%2B1)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Test%20ob%20%3D%20new%20Test()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B10%2C%2090%2C%2049%2C%202%2C%201%2C%205%2C%2023%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20ob.sortInWave(arr%2C%20n)%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3A%20arr)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(i%20%2B%20%22%20%22)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201djava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output-2\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>2 1 10 5 49 23 90<\/pre>\n<h2 id=\"python\"><span style=\"color: #ff0000;\"><strong>PYTHON<\/strong><\/span><\/h2>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20function%20to%20sort%20the%20array%20arr%5B0..n-1%5D%20in%20wave%20form%2C%0A%23%20i.e.%2C%20arr%5B0%5D%20%3E%3D%20arr%5B1%5D%20%3C%3D%20arr%5B2%5D%20%3E%3D%20arr%5B3%5D%20%3C%3D%20arr%5B4%5D%20%3E%3D%20arr%5B5%5D%0Adef%20sortInWave(arr%2C%20n)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23sort%20the%20array%0A%20%20%20%20arr.sort()%0A%20%20%20%20%0A%20%20%20%20%23%20Swap%20adjacent%20elements%0A%20%20%20%20for%20i%20in%20range(0%2Cn-1%2C2)%3A%0A%20%20%20%20%20%20%20%20arr%5Bi%5D%2C%20arr%5Bi%2B1%5D%20%3D%20arr%5Bi%2B1%5D%2C%20arr%5Bi%5D%0A%20%0A%23%20Driver%20progrM%0Aarr%20%3D%20%5B10%2C%2090%2C%2049%2C%202%2C%201%2C%205%2C%2023%5D%0AsortInWave(arr%2C%20len(arr))%0Afor%20i%20in%20range(0%2Clen(arr))%3A%0A%20%20%20%20print%20arr%5Bi%5D%2C\u201d message=\u201dpython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output-3\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>2 1 10 5 49 23 90<\/pre>\n<p>The time complexity of the above solution is O(nLogn) if a O(nLogn) sorting algorithm like <a href=\"https:\/\/www.wikitechy.com\/technology\/merge-sort-linked-lists-2\/\" target=\"_blank\" rel=\"noopener\">Merge Sort<\/a>, <a href=\"https:\/\/www.wikitechy.com\/technology\/time-complexity-building-heap-2\/\" target=\"_blank\" rel=\"noopener\">Heap Sort<\/a>, .. etc is used.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Sort an array in wave form &#8211; Searching and sorting &#8211; A Simple Solution is to use sorting. First sort the input array, then swap all adjacent elements.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71670,83516],"tags":[72773,72746,72738,72759,72754,72768,72757,72767,72737,72762,72761,72764,72731,72775,72743,72748,72771,72733,72736,72766,72753,72774,72732,72745,72749,72772,72758,72770,72734,72750,72765,72763,72777,72730,72404,72756,72752,72760,72739,72735,72742,72751,72755,72740,72747,72769,72741,72776,72744],"class_list":["post-25268","post","type-post","status-publish","format-standard","hentry","category-searching-and-sorting","category-sort-array","tag-antenna-relay","tag-array-antenna","tag-car-ma","tag-carma","tag-carnegie-wave-energy","tag-cylindrical","tag-focal-plane","tag-focal-plane-array","tag-gigabit-wireless","tag-gravitational-waves","tag-gravitational-waves-detected","tag-gravity-waves-detected","tag-integrated-microwave","tag-interstellar-wiki","tag-ka-band-antenna","tag-karma-credit","tag-millimeter","tag-millimeter-wave","tag-millimeter-wave-antenna","tag-millimeter-wave-antenna-array","tag-plane-wave","tag-ppta","tag-pulsar","tag-pulsar-timing","tag-pulsar-timing-array","tag-pulsar-waves","tag-python-print-array","tag-radio-wiki","tag-sector-antenna","tag-short-wave-infrared","tag-silicon-technologies","tag-slot-band","tag-sonic-shock","tag-sort-an-array-in-wave-form","tag-sort-array-java","tag-vertical-wave","tag-visualization","tag-wave-array","tag-wave-energy","tag-wave-plate","tag-wave-power","tag-wave-power-energy","tag-wave-power-generator","tag-wave-software","tag-waveguide-antenna","tag-what-is-a-pulsar","tag-what-is-wave-energy","tag-what-is-wave-power","tag-wireless-gigabit"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25268","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25268"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25268\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25268"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25268"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25268"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}