1
$\begingroup$

Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id < 10^9, 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 alhorithm 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 timeouted.

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

$\endgroup$
  • $\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$ – j_random_hacker May 15 '18 at 12:45
  • 1
    $\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$ – Alex Zhukovskiy May 15 '18 at 13:15
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$
  • $\begingroup$ Great explanation. Thank you. Going to try it ASAP, when come back home :) $\endgroup$ – Alex Zhukovskiy May 15 '18 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$ – Alex Zhukovskiy May 15 '18 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$ – Alex Zhukovskiy May 15 '18 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$ – Alex Zhukovskiy May 15 '18 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$ – j_random_hacker May 16 '18 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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