Smallest number possible by swapping adjacent even-odd pairs in C++

The objective is to rearrange the digits of a given number to generate the smallest possible number while ensuring that adjacent digits represent even-odd pairs. It is known as the "swapping adjacent even-odd pairs" problem in C++.

1. Bubble Sort Approach
2. Greedy Approach

1. Bubble Sort Approach

A popular and easy-to-understand sorting algorithm for effectively resolving a variety of sorting problems is bubble sort. The Bubble Sort method provides a simple solution when used to identify the smallest number that can be obtained by swapping adjacent even-odd pairs.

Using this method, we start by looking at the number's digits from left to right. Iteratively going over the digits, we compare adjacent pairs. If an adjacent pair (an even digit followed by an odd digit) is in the wrong order, we swap them to correct the order. This process is repeated until no more swaps are required to ensure that adjacent digits form even-odd pairs.

Algorithm steps:

Step-1: Enter an array of numbers that have not been sorted.

Step-2: Create a loop that iterates over the array repeatedly until every element is sorted.

Step-3: Iterate over every pair of adjacent elements in the array within the loop.

Step-4: Verify that for every pair, the first element is odd and the second element is even. If true, swap the elements.

Step-5: Compare the element that was just swapped with the element in the array that appeared preceding it. Replace the previously swapped element with the smaller one if necessary.

Step-6: Iteratively repeat the procedure until each pair has been validated and sorted.

Step-7: If no swaps are performed during any iterations, the array is sorted, and the loop can be terminated.

Step-8: Print the sorted array after the sorting process is complete.

Example:

Let us take an example to illustrate swapping adjacent even-odd pairs problem in C++ using the Bubble sort approach.

Output:

 
Please enter the number of elements: 8
Enter the elements separated by space: 7 2 5 9 10 12 8 1
1 5 7 9 2 8 10 12   

Explanation:

This C++ code sorts an array of integers using the Bubble Sort method, which makes sure that integers with the same parity are put in the same relative order and that even-odd pairs are sorted in ascending order. The BubbleSort function swaps adjacent elements in the array iteratively according to specified conditions. The method executes swaps based on whether adjacent elements form even-odd pairs or have the same parity but are out of order in each iteration. If no swaps are done during an iteration, the swapped flag indicates that the array has already been sorted, which optimises the sorting process by breaking out of the loop.

After that, the main function asks the user to enter the array's elements and the number of elements, sorts the array using BubbleSort, and prints the sorted array.

2. Greedy Approach

• Start from the leftmost digit of the number.
• Iterate the process from left to right through the digits of the number.
• Swap the digits if the one before it is even and the one after it is odd.
• Repeat this process until the end of the number is reached or there are no more swaps available.
• By swapping adjacent even-odd pairs, the resulting number will be the smallest possible number.

Example:

Let us take an example to illustrate swapping adjacent even-odd pairs problem in C++ using the Greedy approach.

Output:

 
Please enter the number: 2145367
The smallest number after swapping the adjacent even-odd pairs is: 2145637   

Explanation:

This C++ code swaps adjacent even-odd pairs in a given number expressed as a string in an attempt to discover the smallest possible number. Iterating through the string, the smallestNumberSwappingPairs function finds even digits at even indices and odd digits at odd indices. In order to keep the even-odd pairing maintained, it swaps the numbers if such a pair is found. After that, the main function prompts the user to enter a number; it runs the function smallestNumberSwappingPairs to swap adjacent even-odd pairs in order to get the smallest possible number. After that, the result is printed. Overall, the code effectively uses a swapping method to minimize the number while maintaining the order of even-odd pairs.