Sorting array with gaps in between

We will explain the process of sorting an array by specifying a gap value, where elements are compared by skipping a certain number of indexes. For example, the ith element will be compared to the i+gap element. This method can be a foundation for various sorting techniques, such as sorting even indexes in ascending order, odd indexes in descending order, and sorting even and odd indexes within a specific range. We will examine each of these techniques separately. A sample program is given below:

Press + to interact
Complete Array Before Sorting:
A =  { 7 9 6 5 8 0 -1 8 9 4 6 7 8 9 7 6 4 3 2 1 }
----------------------------------------------------
Complete Array After Ascending Sort with Gap=3: 
A = { -1 9 6 2 8 0 4 8 9 5 6 7 6 9 7 7 4 3 8 1 }
Array values that are changed after Ascending Sort:
A = { -1     2     4     5     6     7     8     }
----------------------------------------------------
Complete Array After Descending Sort with Gap=3: 
A = { 8 9 6 7 8 0 6 8 9 5 6 7 4 9 7 2 4 3 -1 1 }
Array values that are changed after Descending Sort...
A = { 8     7     6     5     4     2     -1     }
----------------------------------------------------

Implementation of sort ascending with a gap

We want to sort an array with an integral multiple of gap indexes (that is, 0+i*gap) in both ascending and descending order.

How can we do that?

Let’s make two functions, sortAscendingWithGap() and sortDescendingWithGap(), in which we will use the same bubble sort algorithm with the following changes:

  1. Divide the size with gap because we want to sort the values with a gap, and add 1 to be on the safe side of the range, which is not completely divisible by the gap.
  2. Increment in the loop with i+=gap.
  3. Compare each ith value with the next value at i+gap.

Let’s write down the functions below:

Press + to interact
void sortAscendingWithGap(int D[ ], int size, int gap)
{
    int total_iterations=size/gap+1;
    
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=0; i+gap<size; i+=gap)
        {
            if(D[i]>D[i+gap])
                swap(D[i], D[i+gap]);
        }
    }
}

Here’s the complete implementation with printing. Also, look at the printWithGap() function. The nested loop inside the printWithGap function makes sure to skip all the values and only place values aligned with the original output so that one can focus on which values our sorting function has manipulated.

Press + to interact
#include<iostream>
using namespace std;
void swap(int & a, int & b)
{
    int t = a;
    a = b;
    b = t;
}
void sortAscendingWithGap(int D[ ], int size, int gap)
{
    int total_iterations=size/gap+1;
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=0; i+gap<size; i+=gap)
        {
            if(D[i]>D[i+gap])
                swap(D[i], D[i+gap]);
        }
    }
}
void sortDescendingWithGap(int D[ ], int size, int gap)
{
    // Write your code here.       
}
void printWithGap(const char msg[ ], int D[ ], int size,int gap=1)
{
    cout << msg ;
    cout <<" = { ";
    for(int i=0; i<size; i+=gap)
    {
        cout << D[i] << " ";
        for(int s=1; s<gap; s++)
             cout <<"  "; // one space for value and one actual space
    }
    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};// {1,2,3,4,5,6,1,2,3,4,5,6,10,-20,30,-40,50,60,-11,-2,-33,-34,-35,-6};
    int size = sizeof(A)/sizeof(int);
    
    cout << "Complete Array Before Sorting...\n";
    printWithGap("A", A, size,1); 
    //cout << endl;
    cout << "\n----------------------------------------------------\n";
    sortAscendingWithGap(A, size, 3);
    printWithGap("Complete Array After Ascending Sort with Gap=3: \nA", 
                            A, size,1); 
    cout << "\nArray values which are changed after Ascending Sort...\n";
    printWithGap("A", A, size,3); 
    cout << "----------------------------------------------------\n";
    sortDescendingWithGap(A, size, 3);
    printWithGap("Complete Array After Descending Sort with Gap=3: \nA", 
                            A, size,1); 
    cout << "\nArray values which are changed after Descending Sort...\n";
    printWithGap("A", A, size,3); 
    cout << "----------------------------------------------------\n";
    
    return 0;
}

Exercise: Implementation of sort-descending (with a gap)

Write void sortDescendingWithGap(int D[], int size, int gap) in the playground above and test it (the main is already there).

Sort Ascending/Descending in range (with gap)

Let’s write two functions:

Press + to interact
void sortDescendingWithGap(int D[ ], int si, int ei, int gap);
void sortAscendingWithGap(int D[ ], int si, int ei, int gap);

Both of these functions work in ranges with a gap value. The two parameters, si and ei, (both inclusive) dictate that this is the region in which the functions need to sort on with the gap value gap.

Here are their implementations:

Press + to interact
void sortDescendingWithGap(int D[ ], int si, int ei, int gap)
{                                   // assuming both si and ei are inclusive
    int total_iterations = (ei-si+1)/gap + 1;  // +1 is due to being on the safe side
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=si; i+gap<=ei; i+=gap)
        {
            if(D[i]<D[i+gap])
                swap(D[i], D[i+gap]);
        }
    }
}
void sortAscendingWithGap(int D[ ], int si, int ei, int gap)
{                                   // assuming both si and ei are inclusive
    int total_iterations = (ei-si+1)/gap + 1;  // +1 is due to being on the safe side
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=si; i+gap<=ei; i+=gap)
        {
            if(D[i]>D[i+gap])
                swap(D[i], D[i+gap]);
        }
    }
}

Notice the total number of values to process are (ei-si+1)/gap + 1. Here +1 is just to be on the safe side.

We will use these two functions to do a lot of variants of sorting now. Let’s look at some of them here.

Application: Sorting in terms of even and odd indexes

Look at the sample input and output.

Sample input

Data before sorting = { 7 9 6 5 8 0 1 8 9 4 6 7 8 9 7 6 4 3 2 1 }

Sample output

After sorting of even indexes = { 9 9 8 5 8 0 7 8 7 4 6 7 6 9 4 6 2 3 1 1 }

Even indices = { 9 8 8 7 7 6 6 4 2 1 }

Let’s also sort the odd indexes in ascending order:

After sorting of odd indexes = { 9 0 8 1 8 3 7 4 7 5 6 6 6 7 4 8 2 9 1 9 }

Odd indices = { 0 1 3 4 5 6 7 8 9 9 }

We want to do the following tasks first:

  1. Sort even indexes in descending order.
  2. Sort even indexes in ascending order.

1. Sorting even indexes in descending order

With sortDescendingWithGap() and sortAscendingWithGap(), this complicated looking task is nothing but a function call:

 sortDescendingWithGap(A, 0, size-1, 2);

2. Sorting even indexes in ascending order

Similarly to sort the even indexes in ascending order, we only have to make a function call:

sortAscendingWithGap(A, 0, size-1, 2);

Here’s the complete implementation to test your program:

Press + to interact
void swap(int & a, int & b);;
void sortDescendingWithGap(int D[ ], int si, int ei, int gap);
void sortAscendingWithGap(int D[ ], int si, int ei, int gap);
void printWithGap(const char msg[ ], int D[ ], int size,int gap, int si);
// Assuming we have the above functions implementations 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};
// Another sample: {1,2,3,4,5,6,1,2,3,4,5,6,10,-20,30,-40,50,60,-11,-2,-33,-34,-35,-6};
    int size = sizeof(A)/sizeof(int);
    
    printWithGap({"Original array:              "}, A, size);
    cout <<"\n";
    sortDescendingWithGap(A, 0, size-1, 2);
    printWithGap({"After sorting evens in descending:      "}, A, size);
    printWithGap({"Only evens after desc-sort:  "}, A, size,2,0);
    
    //Call your function here 
    cout <<"\n----------------------------------------------------------------------\n";
    sortAscendingWithGap(A, 0, size-1, 2);
    printWithGap({"After sorting evens in ascending:       "}, A, size);
    printWithGap({"Only evens after asc-sort:   "}, A, size,2,0);    
    return 0;
}

Instruction: Run the above program to see the effect of the two function call on line 16 and 22.

Exercise: Range sorting

Add the following scenarios in the above playground and test them:

  1. Sort odd indexes in descending order.
  2. Sort odd indexes in ascending order.
  3. Sort in this fashion
    • In the first half, evens in ascending and odds in descending
    • In the second half, evens in descending and odds in ascending
  4. Sort in this fashion
    • In the first half, evens in descending and odds in ascending
    • In the second half, evens in ascending and odds in descending

We can make several such variants.