Wave Sort Using C++ [Easy Tutorial]

Filed Under: C++
Wave Sort Using C

In this article, we will learn wave sort using C++. This is a very popular interview question related to sorting methods. We will start by discussing the problem statement and later work on the implementation part. Let’s get started.

What Is Wave Sort?

Given an array of finite elements, arrange the elements in such an order that the magnitude of the elements forms a wave. In simple words, the first element of the array is greater than the second element then the third element is greater than both the second and the fourth element, and so on.

Note: There can be many orderings possible for a given array, we just have to find any one of such orderings.

Approach

In this article, we will only discuss the optimized approach to this problem. Below are the steps that we will follow to develop the algorithm.

  • Suppose that the first element should be bigger than the second element.
  • We start by comparing the first element with the second.
    • If the first element is greater than the second element, do nothing
    • Otherwise, swap the first element with the second element.
  • Now jump to the third element and compare this element with the second element and the fourth element.
    • If the third element is smaller than the second element than swap these elements. This is because the second element is already smaller than the first element, and third is smaller than second. This ultimately implies that third is smaller than the first element.
    • Else if the third element is smaller than the fourth element, swap these elements.
  • Now move to the current element + 2th element.
  • Repeat the same procedure for all the remaining elements.

Pseudocode

for(i = 0 --> i = size() - 1)
    if(arr[i] < arr[i - 1] && i != 0)
        swap(arr[i], arr[i - 1])
    else if(arr[i] < arr[i + 1] && i != size() - 1)
        swap(arr[i], arr[i + 1])
    i <-- i + 2

Wave Sort Using C++

#include <iostream>
#include <vector>

using namespace std;

// initializing a counter variable
// to keep track of total number
// of swaps the algorithm makes
int swap_count = 0;

// passing the vector by reference
// to reflect the changes that we
// make inside this function
void wave_sort(vector <int> &arr)
{
	int len = arr.size();

	// if the length of the vector
	// is 1 then simply return
	// because it is already wave sorted
	if(len == 1)
		return;

	for(int i = 0; i < len; i+=2)
	{
		// if the element is smaller than its
		// previous element than swap these elements
		if(arr[i] < arr[i - 1] && i != 0)
		{
			cout << "*******" << endl;
			cout << "Current element is: " << arr[i] << endl;
			cout << "Its previous element is: " << arr[i - 1] << endl;
			cout << "Swapping these elements" << endl;
			cout << "Swaps so far: " << ++swap_count << endl;
			cout << "*******" << endl;

			swap(arr[i], arr[i - 1]);
		}

		// else if the element is smaller than the next
		// element, swap again
		if(arr[i] < arr[i + 1] && i != len - 1)
		{
			cout << "*******" << endl;
			cout << "Current element is: " << arr[i] << endl;
			cout << "Its next element is: " << arr[i + 1] << endl;
			cout << "Swapping these elements" << endl;
			cout << "Swaps so far: " << ++swap_count << endl;
			cout << "*******" << endl;

			swap(arr[i], arr[i + 1]);
		}
	}
}

// function to print the vector
void print_vector(vector <int> v)
{
	cout << "******************************************" << endl;
	cout << "The vector is: " << endl;

	for(int num : v)
	{
		cout << num << " ";
	}

	cout << endl << "******************************************" << endl;
}

int main()
{
	vector <int> v;
	cout << "Enter the elements of the vector, press -1 to stop" << endl;

	while(true)
	{
		int num;
		cin >> num;

		if(num == -1)
			break;

		v.push_back(num);
	}

	print_vector(v);
	wave_sort(v);
	cout << "After wave sort" << endl;
	print_vector(v);
}
Algorithm Code
Algorithm Code

Output

Wave Sort Output 1
Wave Sort Output 1
Wave Sort Output 2
Wave Sort Output 2

Conclusion

Today we learned to implement wave sort using C++. In the beginning, we discussed the problem statement. Then we moved to the pseudocode of the algorithm. In the end, we developed a C++ program to demonstrate the working of this algorithm on three different examples. The overall time complexity of this algorithm is O(N). Also, this algorithm is a constant space algorithm, i.e. we do not require any amount of extra space. This is because we iterate through the entire vector only once. That’s basically it for today, thanks for reading.

Further Reading

To read more about sorting methods, you can refer to the following websites.

https://www.journaldev.com/55721/time-complexity-of-sorting-algorithms

https://www.journaldev.com/56329/merge-sort-in-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content