Wave Sort Algorithm: 2 Approaches with Code Examples
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
In this blog, we'll explore the "Wave Sort" algorithm, covering two different approaches to solve the problem, along with detailed code examples to illustrate each method.
Problem Statement
Given an unsorted array of integers, the task is to sort it in wave form. An array is in wave form if array elements are arranged in a sequence such that:
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ...
In other words:
- All even-positioned elements are greater than or equal to their adjacent odd-positioned elements.
- OR: arr[0] >= arr[1] <= arr[2] >= arr[3] <= ...
For example, if the input array is [10, 5, 6, 3, 2, 20, 100], then the output should be [10, 5, 20, 2, 100, 3, 6] or any other array that follows the wave pattern.
Brute Force Approach
Explanation
The simplest way to solve this problem is to:
- Sort the array in ascending order
- Swap adjacent elements, starting from the first pair
This approach works because after sorting, if we swap pairs of elements (indices 0&1, 2&3, 4&5, etc.), the even-positioned elements will be greater than their neighbors, creating the wave pattern.
Time Complexity: O(n log n) - dominated by the sorting operation
Space Complexity: O(1) - no extra space needed except for a temporary variable for swapping
Code (Python)
def wave_sort_brute(arr):
# Step 1: Sort the array
arr.sort()
# Step 2: Swap adjacent elements
for i in range(0, len(arr)-1, 2):
# Swap arr[i] and arr[i+1]
arr[i], arr[i+1] = arr[i+1], arr[i]
return arr
Code (C++)
std::vector<int> wave_sort_brute(std::vector<int> arr) {
// Step 1: Sort the array
std::sort(arr.begin(), arr.end());
// Step 2: Swap adjacent elements
for (int i = 0; i < arr.size()-1; i += 2) {
// Swap arr[i] and arr[i+1]
std::swap(arr[i], arr[i+1]);
}
return arr;
}
Code (Java)
public static int[] waveSortBrute(int[] arr) {
// Step 1: Sort the array
Arrays.sort(arr);
// Step 2: Swap adjacent elements
for (int i = 0; i < arr.length-1; i += 2) {
// Swap arr[i] and arr[i+1]
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
return arr;
}
Optimized Approach
Explanation
We can actually solve this problem without sorting the entire array, which gives us a significant performance boost. The key insight is that we only need to ensure each even-positioned element is greater than its neighbors.
The optimized approach:
- Iterate through the array, considering only even-positioned elements (indices 0, 2, 4, etc.)
- For each even position, make sure it's greater than both its previous and next elements (if they exist)
This approach works because we only care about the relative ordering between adjacent elements, not the overall sorting of the array.
Time Complexity: O(n) - we only need to go through the array once
Space Complexity: O(1) - no extra space needed except for a temporary variable for swapping
Consider the array [10, 5, 6, 3, 2, 20, 100]
i = 0:
- i > 0 → False (skip)
- i < n - 1 → 0 < 6 → True
- arr[0] = 10, arr[1] = 5 → 10 < 5 → False (no swap)
arr = [10, 5, 6, 3, 2, 20, 100]
i = 2:
- arr[2] = 6, arr[1] = 5 → 6 < 5 → False
- arr[2] = 6, arr[3] = 3 → 6 < 3 → False (no swap)
arr = [10, 5, 6, 3, 2, 20, 100]
i = 4:
- arr[4] = 2, arr[3] = 3 → 2 < 3 → Swap!
→ arr = [10, 5, 6, 2, 3, 20, 100]
- arr[4] = 3, arr[5] = 20 → 3 < 20 → Swap!
→ arr = [10, 5, 6, 2, 20, 3, 100]
i = 6:
- i < n - 1 → 6 < 6 → False (skip)
- arr[6] = 100, arr[5] = 3 → 100 < 3 → False (no swap)
arr = [10, 5, 6, 2, 20, 3, 100]
Wave Sort Algorithm Visualization
<visualization-box>
Code (Python)
def wave_sort_optimized(arr):
n = len(arr)
# Traverse all even positioned elements
for i in range(0, n, 2):
# If current element is smaller than previous
if i > 0 and arr[i] < arr[i-1]:
arr[i], arr[i-1] = arr[i-1], arr[i]
# If current element is smaller than next
if i < n-1 and arr[i] < arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
return arr
Code (C++)
std::vector<int> wave_sort_optimized(std::vector<int> arr) {
int n = arr.size();
// Traverse all even positioned elements
for (int i = 0; i < n; i += 2) {
// If current element is smaller than previous
if (i > 0 && arr[i] < arr[i-1]) {
std::swap(arr[i], arr[i-1]);
}
// If current element is smaller than next
if (i < n-1 && arr[i] < arr[i+1]) {
std::swap(arr[i], arr[i+1]);
}
}
return arr;
}
Code (Java)
public static int[] waveSortOptimized(int[] arr) {
int n = arr.length;
// Traverse all even positioned elements
for (int i = 0; i < n; i += 2) {
// If current element is smaller than previous
if (i > 0 && arr[i] < arr[i-1]) {
// Swap
int temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
}
// If current element is smaller than next
if (i < n-1 && arr[i] < arr[i+1]) {
// Swap
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
return arr;
}
Conclusion
In this article, we explored two approaches to sort an array in wave form:
1. The brute force approach sorts the array first, then swaps adjacent elements to create the wave pattern. This approach is simple but takes O(n log n) time due to the sorting operation.
2. The optimized approach directly manipulates the array to ensure even-positioned elements are greater than their neighbors, without sorting the entire array. This gives us a much better O(n) time complexity.
This problem shows how focusing on what actually matters (in this case, the relationship between adjacent elements rather than the overall sorting) can lead to significant performance improvements.
