• Per =?UTF-8?B?Tm9yZGzDtnc=?= (32/32) Nov 16 2018 How do I sort a subrange of a range `x` where the subrange is
• Stanislav Blinov (22/39) Nov 16 2018 Back-of-the-envelope translation (probably some error checking
• Per =?UTF-8?B?Tm9yZGzDtnc=?= (3/15) Nov 16 2018 Wonderful!

Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:

How do I sort a subrange of a range `x` where the subrange is 
defined by a lower and upper (in this case exlusive) element 
contained within `x`?

     auto x = [1,2,7,4,2,6,8,3,9,3];
     auto y = sortSubRange(x, 3,5];

should yield `y` being

     [3,3,4]

and `x` being

     [a ,3,3,4, b]

where

- a contains the elements 1,2,2 in some undefined order and
- b contains the elements 6,7,8,9 in some undefined order

.


Algorithm was highlighted in C++ at 
https://www.youtube.com/watch?v=0WlJEz2wb8Y&t=1719s

as

/** Sort sub-range [sub_begin, sub_end] of [begin, end].
  *
  * Describe at https://www.youtube.com/watch?v=0WlJEz2wb8Y&t=2686s
  */
template <typename I>           // I models RandomAccessIterator
void sort_subrange(I begin, I end,
                    I sub_begin, I sub_end)
{
     if (sub_begin == sub_end) { return; }
     if (sub_begin != begin)
     {
         std::nth_element(begin, sub_begin, end);
         ++sub_begin;
     }
     std::partial_sort(sub_begin, sub_begin, end);
}

Stanislav Blinov <stanislav.blinov gmail.com> writes:

On Friday, 16 November 2018 at 11:24:20 UTC, Per Nordlöw wrote:

 /** Sort sub-range [sub_begin, sub_end] of [begin, end].
  *
  * Describe at 
 https://www.youtube.com/watch?v=0WlJEz2wb8Y&t=2686s
  */
 template <typename I>           // I models RandomAccessIterator
 void sort_subrange(I begin, I end,
                    I sub_begin, I sub_end)
 {
     if (sub_begin == sub_end) { return; }
     if (sub_begin != begin)
     {
         std::nth_element(begin, sub_begin, end);
         ++sub_begin;
     }
     std::partial_sort(sub_begin, sub_begin, end);
 }

Back-of-the-envelope translation (probably some error checking 
would be in order):

import std.range.primitives : isRandomAccessRange;

auto sortSubRange(R)(R range, size_t i, size_t j) if 
(isRandomAccessRange!R) {
     import std.algorithm.sorting : topN, partialSort;
     size_t start = i;
     if (i != 0) {
         topN(range, i);
         start++;
     }
     partialSort(range[start .. $], j-start);
     return range[i .. j];
}

void main() {
     auto x = [1,2,7,4,2,6,8,3,9,3];
     auto y = sortSubRange(x, 3, 6);
     import std.stdio;
     writeln(y); // 3, 3, 4
     writeln(x); // ex. 2, 2, 1, 3, 3, 4, 6, 7, 9, 8
}

Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:

On Friday, 16 November 2018 at 12:08:33 UTC, Stanislav Blinov 
wrote:
 import std.range.primitives : isRandomAccessRange;

 auto sortSubRange(R)(R range, size_t i, size_t j) if 
 (isRandomAccessRange!R) {
     import std.algorithm.sorting : topN, partialSort;
     size_t start = i;
     if (i != 0) {
         topN(range, i);
         start++;
     }
     partialSort(range[start .. $], j-start);
     return range[i .. j];
 }

Wonderful!