Problem Solving: Sorting Variants

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.