# Problem Solving: Sorting Variants II (extended)

Learn to write a program for different variants of sorting.

## 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 `i`

th 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:

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:

- 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`

. - Increment in the loop with
`i+=gap`

. - Compare each
`i`

th value with the next value at`i+gap`

.

Let’s write down the functions below:

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.

#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:

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:

void sortDescendingWithGap(int D[ ], int si, int ei, int gap){ // assuming both si and ei are inclusiveint total_iterations = (ei-si+1)/gap + 1; // +1 is due to being on the safe sidefor(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 inclusiveint total_iterations = (ei-si+1)/gap + 1; // +1 is due to being on the safe sidefor(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:

- Sort even indexes in descending order.
- 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:

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 availableint 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 herecout <<"\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:

- Sort odd indexes in descending order.
- Sort odd indexes in ascending order.
- 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

- 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.