How to custom sort an array in C++, but leave a portion of it unsorted?

Question

I want to sort an array, but leave a part of it out. The part that is left out shall be specified by a start index (n) and an end index (m). All fields between those two indices, including the two specified ones, shall not be sorted. All others, including the ones before the interval and the ones after it, shall be sorted together.

For example:

• Input serial {10 , 4 , 11 , 7 , 6 , 20}
• Non-sort interval start index n = 1
• Non-sort interval end index m = 3 ,
• Output: { 6 , 4 , 11 , 7 , 10 , 20 }

The fields from index 1 to 3 with the values 4, 11, 7 are not sorted.

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
    int arr[5] = {10, 4, 11, 7, 6, 20};
    sort (arr,arr+5);
    for (int i = 0; i < 5; i++){
        cout << arr[i] << " ";
    }
    return 0;
}

How can I do that?

Answer 1

I provide two solutions:

• sort a temporary copy and put the sorted items back into the original list
• create several views of the data, and sort one of the views of the data

Solution One - Make a temporary array with entries 1 - 3 missing. Sort the temporary and put the temporary back into the original array. To make this "elegate", I use an index array which is a lookup into my original array for where to pull the values from and push the values back to:

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char* argv[]) {
  int arr[6] = { 10, 4, 11, 7, 6, 20 };
  int index[3] = { 0, 4, 5 };
  int tmp[3];

  for (int i = 0; i < 3; i++)
    tmp[i] = arr[index[i]];

  sort(tmp, tmp + 3);

  for (int i = 0; i < 3; i++)
    arr[index[i]] = tmp[i];

  for (int i = 0; i < 6; i++)
    cout << arr[i] << " ";

  cout << "\n";

  return 0;
}

Solution Two - Use a custom comparator to sort a the subset of the array:

#include <iostream>
#include <algorithm>

using namespace std;

bool compare(int *a, int *b) {
  return *a < *b;
}

int main(int argc, char* argv[]) {
  int arr[6] = { 10, 4, 11, 7 , 6, 20 };
  int* sorted[3] = { &arr[0], &arr[4], &arr[5] };
  int* skip[3] = { &arr[1], &arr[2], &arr[3] };
  int** arr2[6] = { &sorted[0], &skip[0], &skip[1], &skip[2], &sorted[1], &sorted[2] };

  sort(sorted, sorted + 3, compare);

  for (int i = 0; i < 6; i++)
    cout << **arr2[i] << " ";

  return 0;
}

Answer 2

Here is a way to do it using std::rotate and std::sort.
It rotates the elements that should not be sorted to the end, then sorts the beginning part and then rotates back the ones we moved.

#include <iostream>
#include <iterator>
#include <array>
#include <algorithm>

int main() {
    std::array<int, 6> arr = {10, 4, 11, 7, 6, 20};

    unsigned from = 1;
    unsigned to = 3;

    unsigned distance = to - from + 1;

    if (to + 1 != arr.size())
        std::rotate(arr.begin(), arr.begin() + to + 1, arr.end());

    std::sort(arr.begin(), arr.end() - distance);

    std::rotate(arr.begin() + from, arr.end() - distance, arr.end());

    for (auto v : arr)
        std::cout << v << ' ';
}

I used a std::array instead of a c-style array. Works on a std::vector as well.

Answer 3

This is a nice show case for a range library, e.g. Boost.Range.

We first create a slice range for the parts to be sorted left and right to the fixed part.

auto left = arr | sliced(0, n);
auto right = arr | sliced(m, 6);

Then we create a new range which joins these two slices

auto s = join(left, right);

and sort it

auto r = sort(s);

Together with output this gives us the following code using Boost.Range:

#include<iostream>
#include<algorithm>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/range/join.hpp>

using namespace boost;
using namespace boost::adaptors;

int main(){
  //define original and temp arrays
  int arr[6] = {10, 4, 11, 7, 6, 20};
  auto n = 2;
  auto m = 4;

  auto left = arr | sliced(0, n);
  auto right = arr | sliced(m, 6);
  auto s = join(left, right);

  auto r = sort(s);

  std::cout << "sorted range: ";
  boost::copy(r, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;

  std::cout << "array: ";
  boost::copy(arr, std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;

  return 0;
}

Running the code prints

sorted range: 6,7,10,20, 
array: 6,4,11,7,10,20,

It should also be very efficient since there is no extra moving or copying of data involved. I also find it very expressive.

Answer 4

You can take out the elements that you want to sort and store them in a temp array, then restructure the array in the form you need. I've provided a crude code solution; however, you should look into using std::vector or another std container (also array lengths are hardcoded, if you want to change the length of the orignal array you would need to use something like sizeof(a)/sizeof(a[0])).

#include<iostream>
#include<algorithm>

int main(){
  //define original and temp arrays
  int arr[6] = {10, 4, 11, 7, 6, 20};
  int temp[3] = {0};


  //cycle through arr, remove the static elements, and store in temp array
  int k = 0;
  for(int i = 0; i < 6; i++)
  {
    if(i > 0 && i < 4)
    {
      continue;
    }
    temp[k] = arr[i];
    k++;
  }

  //sort the temp array
  std::sort(temp, temp + 3);

  //restructure the array by placing the static elements back into the original array
  k = 0;
  for (int i = 0; i < 6; i++)
  {
    if (i > 0 && i < 4)
    {
      continue;
    }
    arr[i] = temp[k];
    k++;
  }

  //print out the sorted array with static elements
  for(int i = 0; i < 6; i++)
  {
    std::cout << arr[i] << " ";
  }

  return 0;
}