{"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":"

Sort an array in wave form<\/strong><\/span><\/p>\n

Given an unsorted array of integers, sort the array into a wave like array. An 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><\/p>\n

Examples:<\/strong><\/span><\/h3>\n
 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
A Simple Solution<\/strong> is to use sorting. First sort the input array, then swap all adjacent elements.<\/p>\n
For example, let the input array be {3, 6, 5, 10, 7, 20}. After sorting<\/a>, we get {3, 5, 6, 7, 10, 20}. After swapping<\/a> adjacent elements, we get {5, 3, 7, 6, 20, 10}.<\/p>\n[ad type=”banner”]\n
Below are implementations of this simple approach.<\/p>\n
C++ Implementation of\u00a0Sort an array in wave form:<\/strong><\/span><\/h2>\n
 
 c++<\/span> <\/div> 
\/\/ A C++ program to sort an array in wave form using\/\/ a sorting function#include<iostream>#include<algorithm>using namespace std; \/\/ A utility method to swap two numbers.void swap(int *x, int *y){    int temp = *x;    *x = *y;    *y = temp;} \/\/ This function sorts arr[0..n-1] in wave form, i.e., \/\/ arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5]..void sortInWave(int arr[], int n){    \/\/ Sort the input array    sort(arr, arr+n);     \/\/ Swap adjacent elements    for (int i=0; i<n-1; i += 2)        swap(&arr[i], &arr[i+1]);} \/\/ Driver program to test above functionint main(){    int arr[] = {10, 90, 49, 2, 1, 5, 23};    int n = sizeof(arr)\/sizeof(arr[0]);    sortInWave(arr, n);    for (int i=0; i<n; i++)       cout << arr[i] << " ";    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
2 1 10 5 49 23 90<\/pre>\n
JAVA\u00a0<\/strong><\/span>Implementation of\u00a0Sort an array in wave form:<\/strong><\/span><\/h2>\n
 
 java<\/span> <\/div> 
\/\/ Java implementation of naive method for sorting\/\/ an array in wave form.import java.util.*; class SortWave{    \/\/ A utility method to swap two numbers.    void swap(int arr[], int a, int b)    {        int temp = arr[a];        arr[a] = arr[b];        arr[b] = temp;    }     \/\/ This function sorts arr[0..n-1] in wave form, i.e.,    \/\/ arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]..    void sortInWave(int arr[], int n)    {        \/\/ Sort the input array        Arrays.sort(arr);         \/\/ Swap adjacent elements        for (int i=0; i<n-1; i += 2)            swap(arr, i, i+1);    }     \/\/ Driver method    public static void main(String args[])    {        Test ob = new Test();        int arr[] = {10, 90, 49, 2, 1, 5, 23};        int n = arr.length;        ob.sortInWave(arr, n);        for (int i : arr)            System.out.print(i + " ");    }}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
2 1 10 5 49 23 90<\/pre>\n
PYTHON<\/strong><\/span><\/h2>\n
 
 python<\/span> <\/div> 
# Python function to sort the array arr[0..n-1] in wave form,# i.e., arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5]def sortInWave(arr, n):         #sort the array    arr.sort()        # Swap adjacent elements    for i in range(0,n-1,2):        arr[i], arr[i+1] = arr[i+1], arr[i] # Driver progrMarr = [10, 90, 49, 2, 1, 5, 23]sortInWave(arr, len(arr))for i in range(0,len(arr)):    print arr[i],<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
2 1 10 5 49 23 90<\/pre>\n
The time complexity of the above solution is O(nLogn) if a O(nLogn) sorting algorithm like Merge Sort<\/a>, Heap Sort<\/a>, .. etc is used.<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Sort an array in wave form – Searching and sorting – 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}]}}