Sorting the values with an arbitrary gap

Now here is another non-trivial version of the problems of sorting.

What if we’d like to sort only the even values placed inside the array so that all the odd values remain untouched and only the even values are compared with each other and sorted according to the requirements (ascending or descending)? Similarly, the odd values could be sorted within. We can make several variants of such programs, like sorting only the prime or composite numbers inside the array, considering the other numbers as anchor points).

Sorting even values

Let’s start with even values. Consider the following scenario.

Given an array of integers, sort all the even values in ascending order

Remember: The sorting should not interfere with the values where odd values are placed.

Sample input

Array Before Sorting: A = { 7 9 6 5 8 0 -1 8 9 4 6 7 8 9 7 6 4 3 2 1  }
                                .   . .    .   . .   .     . .   .     
Array After Sorting:  A = { 7 9 0 5 2 4 -1 4 9 6 6 7 6 9 7 8 8 3 8 1  }

Dots '.' are just placed to help the reader understand which elements are manipulated

Let’s discuss the algorithm! How can we sort the even values in an array?

To sort the even values within an array, we need to find where the next even value is.

Let’s create a function nextEven() in which we will pass the array, start index, and end index. This function will return the next index with an even value or -1 in case no further even value is found.

Press + to interact
int nextEven(int D[ ], int si, int ei)
{
    for(int i=si; i<=ei; i++) // keep searching from si towards ei
    {
        if(D[i]%2==0)       // if an even value is found
            return i;       // return that index
    }
    return -1;
}

To sort in ascending order, we will make the following changes in the bubble sort algorithm:

Press + to interact
void sortAscendingOnlyEvenValues(int D[ ], int size)
{
    bool changeHappen;
    int ei = size-1;
    do
    {
        changeHappen = false;
        for(int i=nextEven(D, 0, ei); i!=-1; i=nextEven(D, i+1, ei))
        {
            int ni=nextEven(D, i+1, ei);
            if(ni!=-1 && D[i]>D[ni])
            {
                ChangeHappen = true;
                swap(D[i], D[ni]);
            }
        }
    }
    while(changeHappen);
}

Line 4: We have initialize end index ei with array size.

Line 8:

  • First, we initialize the for loop with i=nextEven(D, 0, ei) that returns the first even value.

  • Second, the for loop will continue to run as long as the returned index is not -1 (because the nextEven() function returns -1 when no even value is found in the given range), and for each iteration, it will set the variable i to the returned index.

  • Third, we update the value of i with the next index where the even value found by executing i=nextEven(D, i+1, ei). When we pass i+1, then nextEven() will return us the next index with an even value.

Lines 10–11: We check if the value at the next index is not even and the value at the current index is greater than the value at the next index. Then, we do swapping and remember that swapping has happened (and another bubbling-step is a must now).

Let’s test our program in the main()function:

#include<iostream>
using namespace std;
void swap(int & a, int & b)
{
    int t = a;
    a = b;
    b = t;
}
int nextEven(int D[ ], int si, int ei)
{
    for(int i=si; i<=ei; i++)
    {
        if(D[i]%2==0)
            return i;
    }
    return -1;
}

void sortAscendingOnlyEvenValues(int D[ ], int size)
{
    bool changeHappen;
    int ei = size-1;
    do
    {
        changeHappen = false;
        for(int i=nextEven(D, 0, ei); i!=-1; i=nextEven(D, i+1, ei))
        {
            int ni=nextEven(D, i+1, ei);
            if(ni!=-1 && D[i]>D[ni])
            {
                changeHappen = true;
                swap(D[i], D[ni]);
            }
        }
    }
    while(changeHappen);
}
void sortDscendingOnlyEvenValues(int D[ ], int size)
{
    //Exercise 2: Write your code here
}
void sortAscendingOnlyOddsValues(int D[ ], int size)
{

}
void sortDscendingOnlyOddsValues(int D[ ], int size)
{
    //Exercise 3: Write your code here
}



void printSpecial(const char msg[ ], int D[ ], int size)
{
    cout << msg << " = { ";
    for(int i=0; i<size; i++)
    {
        cout << D[i] << " ";
    }
    cout << " }"<<endl;
}

int main()
{
    int A[ ] = {7, 9, 6, 5, 8, 0, -1, 8, 9, 4, 6, 7, 8, 9, 7, 6, 4, 3, 2, 1};
    int size = sizeof(A)/sizeof(int);
    
    cout << "Array Before Sorting...\n";
    printSpecial("A", A, size); cout << endl;
    sortAscendingOnlyEvenValues(A,size);  
    cout << "Array After Sorting...\n";
    printSpecial("A", A, size); cout << endl;
    return 0;
}
Sorting even values

Exercise 1: Sorting even values in descending order

Exercise 2: Sort odd values

Sort all the odd values in descending order (this sorting should not interfere with the values where even values are placed).

Exercise 3: Sorting odd values in descending order

Write the code for sorting odd numbers in descending order. The prototype is already written in the playground above.

Challenge: Sorting even and odd values in ranges

Problem statement

We are given data of integers and we need to do the following:

  • In the first half, sort even values in ascending and odd values in descending order.
  • In the second half, sort even values in descending and odd values in ascending order.

Direction: You do not need to make any new function (everything is already made). You just need to call the following function with the appropriate arguments.

void printSpecial(const char msg[ ], int D[ ], int size);
void sortAscendingOnlyEvenValues(int D[ ], int size);
void sortDscendingOnlyEvenValues(int D[ ], int size);
void sortAscendingOnlyOddValues(int D[ ], int size);
void sortDscendingOnlyOddValues(int D[ ], int size);
// Assume your have the above functions available.

int main()
{
    int A[ ] = {7, 9, 6, 5, 8, 0, -1, 8, 9, 4, 6, 7, 8, 9, 7, 6, 4, 3, 2, 1};
    int size = sizeof(A)/sizeof(int);
    
    printSpecial({"Before range sorting: "}, A, size);
    // Write your code here, you need to write 4 lines
    

    printSpecial({"After range sorting: "}, A, size);
    return 0;
}
Challenge: Sorting even and odd values in range