How to sort an array in wave form
Akin to waves, an array sorted in wave form has elements arranged in a series of highs and lows. Mathematically, this would mean that the array,
This is illustrated in the following figure:
As an example, we'll take the
Algorithm
While sorting the array and swapping its adjacent elements would result in an array sorted in wave form, a more efficient solution exists.
The premise of the more efficient solution is that every even-positioned element has to be greater than its respective preceding and proceeding element (as
This results in the following rules for every even-positioned element:
If the element is smaller than the element before it, then swap both of the elements.
If the element is smaller than the element after it, swap both elements.
An example of these rules in play is demonstrated in the following illustration.
C++ code
The code snippet below provides a C++ implementation for the algorithm above.
Note: To run the following code, provide input for the array in the form of just integers separated with a space (without commas or brackets).
For example, enter [3, 5, 1, 6, 4] as
The size of the array is stored in the variable,
n, we may change it to any positive integer.
int n = 6;int arr[n];for (int i = 0; i < n; i++){cin >> arr[i];}for (int i = 0; i < n; i+=2){if (i>0 && arr[i] < arr[i-1]){int temp = arr[i];arr[i] = arr[i-1];arr[i-1] = temp;}if (i<n-1 && arr[i] < arr[i+1]){int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}for (int i = 0; i < n; i++){cout << arr[i] << " ";}
Enter the input below
Complexity
The algorithm above has the following properties:
Explanation
Line 1: We store the size of the array in the
nvariable.Line 3: We store the array in the
arrvariable.Lines 5–7: These lines deal with taking the user's input for the array.
Lines 9–22: A single traversal of the even elements of
arris performed, in which:Lines 11–15: The
ifcondition checks for the first rule and then swaps the current element with the previous element if required.Lines 17–21: The
ifcondition checks for the second rule and then swaps the current element with the proceeding element if needed.
Lines 24–26: We print the array sorted in wave form.
