3
$\begingroup$

Consider following task:

we have an input of N+1 lines, where first line contains N ≤ 150000 - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id ≤ 10^7, m ≤ 100.
We have to perform a stable sort on this sequence and print the result.

Sample input:

8
1 2
16 3
11 2
20 3
3 5
26 4
7 1
22 4

Sample output:

3 5
26 4
22 4
16 3
20 3
1 2
11 2
7 1

My current naive implementation was just allocate vector of size N, fill it, and then run any stable sort algorithm on it. In following example (all examples are written in Rust) I'm just adding row number as part of the sorting key and then perform quick sort:

use std::io::{self, BufRead};
use std::cmp::Ordering;

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();
        tuples.push((id, m, i));
    }

    tuples.sort_unstable_by(|a, b| {
        let cmp = b.1.cmp(&a.1);
        match cmp {
            Ordering::Equal => a.2.cmp(&b.2),
            other => other
        }
    });

    for (id, m, ..) in tuples {
       println!("{} {}", id, m);
    }
}

My second implementation used BTreeSet, but it wasn't a success, and it have taken much more time than first naive one.

My third idea was using idea from insertion sort to keep array sorted from the scratch. When we get yet another element from the stream we just seek the position where it should be placed and then insert in there. When all elements are processed we already have a final array. Here is a sample implementation:

use std::io::{self, BufRead};
use std::cmp::Ordering;

struct TeamResult {
    id: u32,
    m: u8,
}

impl TeamResult {
    pub fn new(id: u32, m: u8) -> Self {
        Self {
            id,
            m
        }
    }
}

impl Ord for TeamResult {
    fn cmp(&self, other: &Self) -> Ordering {
        other.m.cmp(&self.m)
    }
}

impl PartialOrd for TeamResult {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

impl PartialEq for TeamResult {
    fn eq(&self, other: &Self) -> bool {
        self.m.eq(&other.m)
    }
}

impl Eq for TeamResult { }

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();

        let item_to_insert = TeamResult::new(id, m);
        let index_to_insert = search_pos(&tuples[0..i], &item_to_insert);
        tuples.insert(index_to_insert, item_to_insert);
    }

    for x in tuples {
        println!("{} {}", x.id, x.m);
    }
}

fn search_pos<T: Ord>(a: &[T], value: &T) -> usize {
    let len = a.len();

    if len == 0 {
        return 0;
    }

    if value < &a[0] {
        return 0;
    }

    if value > &a[len - 1] {
        return len;
    }

    let mut lo = 0;
    let mut hi = len - 1;

    while lo < hi {
        let mid = (hi + lo) / 2;

        match value.cmp(&a[mid]) {
            Ordering::Less => hi = mid - 1,
            Ordering::Greater => lo = mid + 1,
            Ordering::Equal => {
                lo = mid;
                break;
            }
        };
    }

    while lo <= hi && value >= &a[lo] {
        lo += 1
    }

    lo
}

However, it was even slower than a BTree one and it timed out.

I wonder what are theoretical and practical optimal implementations?
I mean I think that in theory BTree should be faster on this task, but in practice simple array sort beats it.

$\endgroup$
2
  • $\begingroup$ This sounds like a competition problem. Please give a link to the problem description so that those of us who prefer not to help people participating in active contests can see if the contest is currently active or not. $\endgroup$ May 15, 2018 at 12:45
  • 3
    $\begingroup$ @j_random_hacker I have taken it from Tetrahedron Team Contest May 2001, task A. This competition ended long time ago. I'm just interested in optimal solution. It's an algorithmic problem, I don't pretend to get any points for it or something. I'l accept any change in the task definition or absence of concrete solution if it hurts anyone. I was thinking about it several years ago, but several days ago I just found that competition with that task and tried to solve it, not to participate anywhere, but just for interest. $\endgroup$ May 15, 2018 at 13:15

2 Answers 2

1
$\begingroup$

First, it should not be surprising that if you want to sort some numbers, a dedicated sorting algorithm is faster than using a data structure that is capable of sorting and also doing other things (finding given elements efficiently, inserting new elements efficiently, removing elements efficiently). (That said, you should find that the difference is "only" a constant factor, at least for sufficiently large inputs.)

Since the maximum m value is very small, you can just use a slight variant of counting sort, which takes $O(n+m)$ time and memory. Declare an array freq[] of size 101, then in a first pass through all the numbers, increment the corresponding element of freq for each number: this is to decide the bucket sizes. Then allocate a fresh length-$n$ buffer output[], and make a pass through the 101 elements of freq, changing each element to the total so far: after doing this, freq[i] conceptually points to one past the end position of a block within output[] that is large enough to hold all input numbers having key equal to i. Now make a final pass in reverse order through the n input elements, writing each to the next free space available within its block and decrementing the position accordingly. (Literally for (int i = n - 1; i >= 0; --i) output[--freq[input[i].m] = input[i].id; in C++.)

There are no truly "streaming" sorting algorithms, since the very last number read could be smaller than all the others, meaning you have to either buffer them, or save partial results to disk.

$\endgroup$
5
  • $\begingroup$ Great explanation. Thank you. Going to try it ASAP, when come back home :) $\endgroup$ May 15, 2018 at 13:59
  • $\begingroup$ I'm trying to implement your algorithm. However, I currently face several troubles. One of them is that order must be descending, while count expects to be ascending. It's completely solveable, but it requires more efforts. Here is what I've done for now. Feel free to play with code. $\endgroup$ May 15, 2018 at 22:45
  • $\begingroup$ Hmm, it didn't take much time: play.rust-lang.org/… I'm inspired with your answer. Going to finish it and check results. BRB with them. $\endgroup$ May 15, 2018 at 23:01
  • $\begingroup$ It seems that for some reason it doesn't perform stable sort.. I can't pass Test #3 (I don't have input data to debug it). Any ideas what could be wrong? It works fine on all my sample data. $\endgroup$ May 15, 2018 at 23:38
  • 1
    $\begingroup$ I don't know Rust, I'm afraid, but your code looks alright to me. The best way to debug something is to try to find a small input that produces the problem. I would suggest writing a function that generates a large number of random size-$k$ arrays, testing each one and reporting any failures, for say $k = 2, 3, 4$. Use fairly restricted numbers to get a good chance that some pairs will test the sort stability. $\endgroup$ May 16, 2018 at 5:59
1
$\begingroup$

Here is an algorithm to consider https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8982863/

$\endgroup$
6
  • $\begingroup$ This is a highly interesting result. The paper proposes an algorithm that takes $O(n)$ time complexity and $O(m)$ space complexity (RAM) where $m < 0.35n$. It is peer-reviewed by PLoS One (Wikipedia), and the proof can be found in the "Time Complexity Analysis" section of the 34th reference of the paper, which is authored by the same person. However, the proof is beyond my understanding, and I don't see this explained elsewhere, could you provide an explanation? Note to moderators: Please don't delete this answer, it could be useful for search results. $\endgroup$ Feb 1 at 22:44
  • $\begingroup$ I would appreciate an explanation from anyone as to the following: Is this a comparison sorting algorithm, or is this a non-comparison sorting algorithm? As far as I know, both comparison and non-comparison are not known to be $O(n)$, so roughly how did this paper achieve this, or is there any flaw? This answer authored by myself along with the comment might be useful, it is mostly based on the Wikipedia page on the topic. $\endgroup$ Feb 1 at 22:52
  • 1
    $\begingroup$ Where I'm not mistaken, there are Constraints like At any time, the sizes of previously sorted data in a compact form and the size of next incoming data chunk must not exceed [available memory] or each value may appear at most twice. $\endgroup$
    – greybeard
    Feb 2 at 11:22
  • $\begingroup$ @greybeard Interesting catch, but I believe the interpretation is that it needs many subsequences (sorted) with each adjacent element (must be an integer) differ by at most two, what do you have in mind? In the "Definitions and Notations" section of the 34th reference, it describes 4 main compactifications which are central to the algorithm, namely type-1 where each adjacent element differ by 1, type-2 where each adjacent element differ alternatingly by 1, 2, 1, 2, .., type-3 where each adjacent element differ alternatingly by 2, 1, 2, 1, .., and type-4 where each adjacent element differ by 2. $\endgroup$ Feb 2 at 14:32
  • 1
    $\begingroup$ To me, it looks an ad-hoc streaming/online compression procedure for integer keys much more than sorting. (And I don't really have any idea what exactly they suggest to sort, and how - just the integers? Semi-useless. Including "associated data"/medium size data records? Good luck keeping a decent compression ratio. Process two-pass à la counting sort? How will random access to the output be handled?) $\endgroup$
    – greybeard
    Feb 2 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.