CODEWITHSUNDEEP
arraysalgorithmsortinginteger
Walter Stabosz
Walter Stabosz

Reputation: 7735

Is it possible to sort integers with this very limited set of operators?

Background

I'm working in a strange programming language with a very limited tool set.

I want to sort a list of integers, but I can't figure out an algorithm that works given the tools. I don't know if it's even possible.

The operators

This is some JavaScript code that documents the available operators.

// 1. you can create new variables
// javascript quirk: in order to pass-by-reference, you must store an integer in an object
const v = (value) => {
    return { value: value };
}

// 2. you can set A to B, if B is larger than A
const max = (a,b) => {
    if(b.value > a.value)
        a.value = b.value;
};

// 3. you can set A to B, if B is less than A
const min = (a,b) => {
    if(b.value < a.value)
        a.value = b.value;        
};

// 4. you can swap the values of A and B
const swap = (a,b) => {
    let t = a.value;
    a.value = b.value;
    b.value = t;
};

// 5. you can set A to B
const set = (a,b) => {
    a.value = b.value;
};

// 6. you can add B to A
const add = (a,b) => {
    a.value = a.value + b.value;
};

// 7. you can subtract B from A
const subtract = (a,b) => {
    a.value = a.value - b.value;
};

// 8. you can multiply A by B
const multiply = (a,b) => {
    a.value = a.value * b.value;
};

// 9. you can divide A by B, losing the remainder
// if B == 0, then A is not modified
const divide = (a,b) => {
    if (b.value == 0) return;
    a.value = Math.floor(a.value/b.value);
};

// 10. you can set A to the remainder of A divided by B
// if B == 0, then A is not modified
const mod = (a,b) => {
    if (b.value == 0) return;
    a.value = a.value % b.value;
};

// 11. you can test if A falls within a range of integers, and if true, call a function 
// (see next section for function rules). You cannot do anything with a false
//
// min and max must be hard coded integers (i.e. you cannot pass in variables)
const in_range = (a,min,max) => {
    return (a >= min && a <= max);
};

// 12. you can add an integer to A
// x must be a hard-coded integer, you cannot pass in variables
const add2 = (a,x) => {
    a.value = a.value + x;
};

// 13. you can set A to an integer
// x must be a hard-coded integer, you cannot pass in variables
const set2 = (a,x) => {
    a.value = x;
};

Input

    var a = v(2);
    var b = v(1);
    var c = v(3);

    // you may create as many extra variables as you want
    var temp = v(0);

Desired result

    a.value == 1
    b.value == 2
    c.value == 3

Question

Using only the operations listed above, it possible to sort the integers ?

The language is very limited:

There are no loops, or other comparison/logic flow available.

There are no arrays.

You can write functions, but they have to follow the above rules. You cannot pass variables to functions, they must be accessed from the global scope.

Upvotes: 0

Views: 66

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59253

Now that the definitions of max and min have been fixed, you can do it like this:

var sum = v(0);
add(sum ,a);
add(sum ,b);
add(sum ,c);

//remember a and set a to min
var olda = v(0);
set(olda,a);
min(a,b);
min(a,c);

//set c to max
max(c,olda);
max(c,b);

//calculate b
set(b,sum);
subtract(b,a);
subtract(b,c);

You have way more operations available than you need. Obviously, it is easier than this to sort just 2 variables, and if you can sort 2, then you can sort as many as you like using a sorting network.

Upvotes: 1

Related Questions