Sorting an array

There's an array of values from 1 to n. It isn't sorted. We have to sort it, but there are only to ways to move: third element to beginning or last element to beginning. How to do that ?

The only winning move is to take a pre-sorted array

What if n=2?

>>3
If it's {1, 2} its done.
If it's {2, 1} move last element to front and it's done.


check array n > 2

while ( !sorted )
{
    if ( rand() & 1 )
        third_to_start();
    if ( rand() & 1 )
        last_to_start();
}

If the first three elements are sorted, move the last one.
Otherwise, move the third one.

What a retarded homework

>>6
Sure. It's the best way to do an infinity loop

>>1
Moving to beginning, as in swapping first and last, or pop back and push front?

>>9
No, no swapping. It's moving to beginning. The previous first element is now second etc

>>8
In which circumstance would that happen?

>>11
for example,
2 1 3
Next steps:
3 2 1
1 3 2
2 1 3
And we're in home.

>>12
That's the special case where the third element is the last element. So you'd be moving the same--IHBT

>>13
Yeah ? So add one more:
2 1 3 4
First three elements aren't sorted, so we try to do that:
3 2 1 4
1 3 2 4
2 1 3 4
And we're in home one more time.

>>14
Alright then, switch the conditions around. It took me 5 whole seconds to think of this. I'm quite surprised it didn't stand up to such intense scrutiny.

>>14
2 1 3 4:
4 2 1 3 (last-->1)
3 4 2 1 (3-->1)
2 4 3 1 (3-->1)
1 2 4 3 (last-->1)
4 1 2 3 (3-->1)
3 4 1 2 (last-->1)
2 3 4 1 (last-->1)
1 2 3 4 (last-->1)[/m]
The real question is if you can build an intuitive algorithm out of these two rules.  I doubt the problem can be made to compute in polynomial time.

To me it almost seems like a version of the Tower of Hanoi problem, but that could just be me.

>>16
Reading over my own post, I mislabeled a step, accidentally a swap, and messed myself up.  Redo; alternate:
2 1 3 4:
4 2 1 3 (last-->1)
3 4 2 1 (last-->1)
2 3 4 1 (3-->1)
1 2 3 4 (last-->1) (done)

>>18
So what's the algorithm? Or are you just solving that one case?
What about
if (third < first) {
 swap (third)
} else if (last < first) {
 swap (last)
} else swap (min(third, last))

>>19
What do you mean by 'min' function ?

>>19
The minimum of the two. I ran through it, and it doesn't work.

This task may revert to an impossible task (to find non-randomly), as it's kind of similar to Collatz conjecture

>>19
2 1 3 4:
3 2 1 4 (case 3)
1 3 2 4 (case 1)
2 1 3 4 (case 3) (failure)
(I did my solution intuitively - not working with an algorithm.)

>>23
Yeah. I'd like to kid myself that there is a similarly simple solution, but there probably isn't.

>>24
The simplest solution is to perform an inplace anusSort

>>22
What? There's no connection.
It's pretty easy for the solvable cases.

Here's a brute force solution. Generate every possible sequence of moves and filter out the move sequences that don't sort the list. Lists of even length are sortable, but some odd lists aren't sortable.


{-#LANGUAGE ViewPatterns #-}

import Prelude hiding (length, splitAt)
import Data.List (permutations)
import Data.Sequence hiding (filter)

herpsort :: (Ord a) => Seq a -> Seq a
herpsort s = head . filter sorted . map (runMoves s) $ allMoves

runMoves :: Seq a -> [Seq a -> Seq a] -> Seq a
runMoves s moves = foldr ($) s moves

allMoves :: [[Seq a -> Seq a]]
allMoves =
    allMoves' [[moveThird], [moveLast]]
  where
    allMoves' s = s ++ allMoves' (map (moveThird :) s ++ map (moveLast :) s)

moveThird s = moveToFront 2 s
moveLast  s = moveToFront (length s - 1) s

moveToFront :: Int -> Seq a -> Seq a
moveToFront n s =
    (item >< first) >< rest
  where
    (first, xs)  = splitAt n s
    (item, rest) = splitAt 1 xs

sorted :: (Ord a) => Seq a -> Bool
sorted (viewl -> EmptyL)  = True
sorted (viewl -> x :< xs) =
    sorted' x xs
  where
    sorted' :: (Ord a) => a -> Seq a -> Bool
    sorted' prev (viewl -> EmptyL)  = True
    sorted' prev (viewl -> x :< xs) = prev <= x && sorted' x xs



test1 = map herpsort . map fromList . permutations $ [1..4]
test2 = map herpsort . map fromList . permutations $ [1..6]

-- not sortable
hurr = herpsort $ fromList [2, 1, 3, 4, 5]

-- sortable
durr = herpsort $ fromList [2, 1, 3, 5, 4]

-- not sortable
hurf = herpsort $ fromList [2, 1, 3, 4, 5, 6, 7]

-- sortable
durf = herpsort $ fromList [2, 1, 3, 4, 5, 7, 6]

>>27
A brute force solution would have to run to infinity - any combination of moves could be the right one.

Unless you used memoization that is, and checked to see if every possible move got you to the list of previous values. Otherwise, yeah, to brute force it would take infinity.

>>28
IHBT

Bumping for hint towards general proof that the unsolvable cases are indeed such.
I tried looking for invariants, but no luck.

python:

range(N)

>but there are only to ways to move: third element to beginning or last element to beginning

Fuck off, ``faggot'

>>30
To find an unsolveable case, all you'd have to do is make all possible choices, and if it leads you to a previous sorting, then it's unsolveable.

Obviously the # of possible cases takes exponential memory and time for the elements you have to sort.

>>32
I think you are too clueless on the subject to even troll efficiently.

>>33
*your

>>34
What [i]about[i] my clueless?

Trolling is a art.

>>36
Indeed. It is risible that certain people seem to think they can compensate for their deficiency of skill and talent with sheer persistence.

_______           _______  _       _________ _        _______
(  ____ \|\     /|(  ____ \| \    /\\__   __/( (    /|(  ____ \
| (    \/| )   ( || (    \/|  \  / /   ) (   |  \  ( || (    \/
| (__    | |   | || |      |  (_/ /    | |   |   \ | || |     
|  __)   | |   | || |      |   _ (     | |   | (\ \) || | ____
| (      | |   | || |      |  ( \ \    | |   | | \   || | \_  )
| )      | (___) || (____/\|  /  \ \___) (___| )  \  || (___) |
|/       (_______)(_______/|_/    \/\_______/|/    )_)(_______)
                                                              
 _       _________ _______  _______  _             _______         
( \      \__   __/(  ____ \(  ____ )( )  |\     /|(  ___  )|\     /|
| (         ) (   | (    \/| (    )|| |  | )   ( || (   ) || )   ( |
| |         | |   | (_____ | (____)|| |  | (___) || |   | || | _ | |
| |         | |   (_____  )|  _____)| |  |  ___  || |   | || |( )| |
| |         | |         ) || (      (_)  | (   ) || |   | || || || |
| (____/\___) (___/\____) || )       _   | )   ( || (___) || () () |
(_______/\_______/\_______)|/       (_)  |/     \|(_______)(_______)
                                                                   
 ______   _______  _______  _______   __________________
(  __  \ (  ___  )(  ____ \(  ____ \  \__   __/\__   __/
| (  \  )| (   ) || (    \/| (    \/     ) (      ) (  
| |   ) || |   | || (__    | (_____      | |      | |  
| |   | || |   | ||  __)   (_____  )     | |      | |  
| |   ) || |   | || (            ) |     | |      | |  
| (__/  )| (___) || (____/\/\____) |  ___) (___   | |  
(______/ (_______)(_______/\_______)  \_______/   )_(  
                                                       
          _______  _______  _         _____ 
|\     /|(  ___  )(  ____ )| \    /\ / ___ \
| )   ( || (   ) || (    )||  \  / /( (   ) )
| | _ | || |   | || (____)||  (_/ /  \/  / /
| |( )| || |   | ||     __)|   _ (      ( ( 
| || || || |   | || (\ (   |  ( \ \     | | 
| () () || (___) || ) \ \__|  /  \ \    (_) 
(_______)(_______)|/   \__/|_/    \/     _  
                                        (_)

#include <stdio.h>

#define TREE_MAX     16
#define TREE_POWER_2 65536

#define ARRAY_SIZE 4

int tree[TREE_POWER_2][TREE_MAX];

void show(int *a)
{
    int i;
    for(i = 0; i < ARRAY_SIZE; i++)
        printf("%d", a[i]);
}

void swap_third(int *a)
{
    int tmp = a[0];
    a[0] = a[2];
    a[2] = tmp;
}

void swap_last(int *a)
{
    int tmp = a[0];
    a[0] = a[ARRAY_SIZE-1];
    a[ARRAY_SIZE-1] = tmp;
}

int sorted(int *a)
{
    int i;
    for(i = 1; i < ARRAY_SIZE; i++)
        if(a[i - 1] > a[i])
            return 0;
    return 1;
}

int main(void)
{
    int i, nsorted = 0;

    /*
     * tree:
     *    0000 0000
     *    0000 0001
     *    0000 0010
     *    0000 0011
     *    ...
     *    1111 1111
     *
     * 0 means swap_last
     * 1 means swap_third
     */


    for(i = 0; i < TREE_POWER_2; i++){
        int *a = tree[i];
        int  n = i, j = 0;

        for(j = 0; j < TREE_MAX; j++){
            a[j] = n % 2;
            n /= 2;
        }
    }

    for(i = 0; i < TREE_POWER_2; i++){
        int a[ARRAY_SIZE] = { 4, 2, 1, 3 };
        int j;

        for(j = 0; j < TREE_MAX; j++){
            printf("iteration %02d: ", j + 1);
            show(a);
            if(tree[i][j]){
                printf(" (third) ");
                swap_third(a);
            }else{
                printf(" (last ) ");
                swap_last(a);
            }
            printf(" -> ");
            show(a);
            putchar('\n');

            if(sorted(a)){
                puts("  sorted!");
                nsorted++;
                break;
            }
        }

        if(j == TREE_MAX)
            puts("  not sorted :(");
    }

    printf("---\nstats (with %d iterations)\nsorted: %d, not sorted: %d\n",
            TREE_MAX, nsorted, TREE_POWER_2 - nsorted);

    return 0;
}

No need to thank me.

>>39
It just doesn't work, am i rite ?

>>39
5/10, a commendable effort.  I wondered what it was doing until I noticed the swap.

Anyway, you can do an insertion sort in Θ(n²).

Samefag from >>40 here
I'm just curious how to do that

>>42
samefag
back to /b/, please

>>43
implying your post is going to change anything

>>42
What? It works ^fine

Simplify the operations a bit; last → first is just rotation; use that to seek, and you have just one operation: move any element two positions forward.
For even sized arrays this lets you move any element anywhere, for odd-sized arrays you have to first rotate the element to the correct modulo-2 position, and you'll end up with a sorted or almost sorted array.

A more interesting question is how to prove the unsolvable cases can't be solved. I found an invariant using the Lehmer code — probably, but it's kind of a pain to make a formal proof.

>>46
What do you mean by 'correct modulo-2 position' ?

>>46
—
fuck you

>>46
The most essential question is to make this max in O(n^2).
I dunno what correct modulo position is

>>49
That's okay, we love you anyway.

I thing the best way to sort arrays is
arrGayConquests.sort();

http://sio.mimuw.edu.pl/user.php/prz.pdf?op=get&id=96921

What a faggot, you thought the /prog/ won't find out?

>>52
Hah, wow, they get a month for five tasks? Please tell me this was the easy one.

>>53
This is the fourth of five. The three before it are laughable and doable by either tree search or even simple Haskell list comprehension and mapping/Prolog hacks, if the provided memory is sufficient. The third one is a joke; I'm assuming I'm too tired and missing something.

http://sio.mimuw.edu.pl/user.php?op=zadania&c=10180

I'd also like to direct you to a helpful blög post that will be of great help while doing most, if not all, of these exercises.

http://cairnarvon.rotahall.org/2010/02/28/search-trees-are-easy/

>>55
*blag

>>55
Nice shameless self-promotion, ``faggot''.

>>55
When are you going to write something new?

>>5

I like this solution.

>>55,57
Remember folks, if you dislike his post or his blog, it's because you're "insecure" or "uneducated." Heaven forbid he could actually be a douche.

>>60
I posted his blog in an honest attempt to help with these exercises, not because of your stupid Xarn wars or whatever. I demand an apology.

Fuck IHBT.

>>60
Fuck off of /prog/.

finally a czarn mention

BAMPV XARNÆ

>>61
Please forgive me, >>61, no offence indented.

FORCED INDENTION OF FORGIVENESS

>>60
I'll take a knowledgeable, interesting ``douche'' over someone whose only contribution to /prog/ consists of whining in every fucking thread because Xarn once called him a name.

>>64
And you can fuck right off too.

>>66
You're mad...

>>67
your gay

>>68
What about my gay?

>>54
Bear in mind that these are for kids from 16 to 19 years old, and this is only first of three rounds. Yeah, they are easy, but I would really like to see, how do you solve them using search trees in reasonable time complexity.

Don't change these.

Name:		Email:
Entire Thread Thread List