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 ?