Problem Solving: Sorting Variants

Learn to write a program for different variants of sorting.

We'll cover the following

Sorting variants

The purpose of this and the next lesson is to understand how to generalize the ideas of manipulating the data in ranges and portions.

For example, we could sort part of an array in an ascending or descending order. We can also sort only the even indexes or odd indexes in either ascending or descending order. We can also sort just the even or odd values in the data, etc.

Let’s begin!

Sort a specific range within an array

Task 1: Given an array and a range, sort the part of the array within the range in ascending order.

Sample input

A before sorting: { 1 2 3 4 5 6 1 2 3 4 5 6 10 -20 30 -40 50 60 -11 -2 -33 -34 -35 -6  }
Range[si ei]   :    0 12

Sample output

Array after SortAscending for [0 12]:
A = { 1 1 2 2 3 3 4 4 5 5 6 6 10 -20 30 -40 50 60 -11 -2 -33 -34 -35 -6  }

Sorted region A[0...12]: A = { 1 1 2 2 3 3 4 4 5 5 6 6 }

UnSorted region A[13...23]: A = { 10 -20 30 -40 50 60 -11 -2 -33 -34 -35 -6  }

To solve this problem, we need to make the following function:

void sortAscending(int D[], int si, int ei);
  • D[] is the given array.
  • si and ei are the start and end indexes, respectively.

We’ll generalize the bubble sort algorithm in this range setting that we have discussed in a previous lesson.

Idea:

  • First, calculate the size of the range on which our algorithm needs to work. The range size will determine how many times the bubbling iterations should run.

    int total_iterations = ei-si+1;

  • For bubbling, as we need to work in the range now, we need to start the loop (the inner bubbling loop) from si and must not exceed the limit of the range, which is ei and the rest of the bubbling will be exactly the same.

Press + to interact
void sortAscending(int D[ ], int si, int ei)
{
    int total_iterations = ei-si+1; // compute the size
    
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=si;            // instead of starting from 0 we start at si
                      i+1<=ei;   // the ending i+1 must not exceed ei
                            i++) // increment is exactly the same
        {
            if(D[i]>D[i+1])
                swap(D[i], D[i+1]);  // use library swap function.
        }
    }
}

Here’s the complete implementation with the testing main() program:

#include<iostream>
using namespace std;

void sortAscending(int D[], int si, int ei)
{
    int total_iterations = ei-si+1;
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=si; i+1<=ei; i++)
        {
            if(D[i]>D[i+1])
                swap(D[i], D[i+1]);
        }
    }
}
void sortDscending(int D[], int si, int ei)
{
    // 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[ ] = {1,2,3,4,5,6,1,2,3,4,5,6,10,-20,30,-40,50,60,-11,
                       -2,-33,-34,-35,-6};
        // another sample u may try...
        // {7, 9, 16, 5, 8, 0, -1, 8, 9, 4, 6, 7, 8, 9, 7, 6, 4, 3, 2, 1};
    int size = sizeof(A)/sizeof(int);
                // sizeof(A) tells the array size in bytes
                // as each entry is of 4 bytes due to integer
                // so size = (TheArraySize)/(ElementSize)
    cout << "Array before sorting:\n";
    printSpecial("A", A, size); cout << endl;
    sortAscending(A, 0,size/2);
    cout << "Array after sorting the first half:\n";
    printSpecial("1st half of A   (Sorted)", A, size/2); cout << endl;  // printing 
    printSpecial("2nd half of A (UnSorted)", A+size/2, size-size/2); cout << endl;
                    // sending the base address of middle value
                    // and the remaining size
    return 0;
}
First half array in ascending

Look at the animation below, where we have divided an array into four quarters. The question that follows is based on this animation.

Sorting the ranges

Question

Given the above implementation of sortAscending() function, how will we sort the first quarter and the third quarter of the array in ascending order?

Show Answer

Look at the animations below, where we call the sortAscending() for each quarter in the following two ways:

  1. Range sort by changing address.
  1. Range sort by changing indexes.

Exercise 1: Sorting in descending order

Now, we want to sort the first half of the array in descending order:

Sample input

Array Before Sorting:
A = { 1 2 3 4 5 6 1 2 3 4 5 6 10 -20 30 -40 50 60 -11 -2 -33 -34 -35 -6  }

Sample output

Array After Sorting:
A = { 10 6 6 5 5 4 4 3 3 2 2 1 1 -20 30 -40 50 60 -11 -2 -33 -34 -35 -6  }

Instruction: Write in the playground above the following function:

void sortDscendingInRange(int D[], int si, int ei)

Using this function sorts the first half values in descending order.

Exercise 2: Sorting within ranges of an array

Given the implementation of sortAscending() and sortDescending(), let’s do the following:

  • Sort the first and third quarters of the array in ascending order.
  • Sort the second and fourth quarters in descending order.

In the end, we print the array.

Press + to interact
#include<iostream>
#include <utility>
using namespace std;
void sortAscending(int D[], int si, int ei);
void sortDescending(int D[], int si, int ei);
void printSpecial(const char msg[], int D[], int size);
int main()
{
    int A[ ] = {1,7,3,4,5,6,1,2,3,4,5,6,10,-20,30,-40,50,60,-11,-2,-33,-34,-35,-6};// {7, 9, 16, 5, 8, 0, -1, 8, 9, 4, 6, 7, 8, 9, 7, 6, 4, 3, 2, 1};
    int size = sizeof(A)/sizeof(int);
    
    cout << "Before sorting:\n";
    printSpecial("A", A, size); cout << endl;
    // write your code here...
    
    return 0;
}
void sortAscending(int D[ ], int si, int ei)
{
    int total_iterations = ei-si+1;
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=si; i+1<=ei; i++)
        {
            if(D[i]>D[i+1])
                swap(D[i], D[i+1]);
        }
    }
}
void sortDescending(int D[ ], int si, int ei)
{
    int total_iterations = ei-si+1;
    for(int t=1; t<=total_iterations; t++)
    {
        for(int i=si; i+1<=ei; i++)
        {
            if(D[i]<D[i+1])
                swap(D[i], D[i+1]);
        }
    }
}
void printSpecial(const char msg[ ], int D[ ], int size)
{
    cout << msg << " = { ";
    for(int i=0; i<size; i++)
    {
        cout << D[i] << " ";
    }
    cout << " }"<<endl;
}

Click “Show Solution” to see the solution below: