Flipping mechanism bug

**CaliforniaCoder1984** · October 27th, 2011, 08:55 PM

I've made a system that when given an array of unsorted numbers and the length of the array returns the sequence at which points the array can be flipped to create a sorted list.

I have the main setup figured there just seems to be some deviations that mess up the system, and I have been looking for the bug for 5 hours now.

Edit - Some further explanation:
The output is an "index" which is actually index + 1, so for example if I were to rotate from the second number in the array it would out 2.

Eg. for the array of [1, 7, 6, 4, 2] the output would be: "2 1 0" because..

Rotating at 2 gives [1, 2, 4, 6, 7]
Rotating at 1 gives [7, 6, 4, 2, 1] (A sorted list)

0 is used to confirm the end of the sequence.

This works by putting the highest number that isn't already in order to the end of the array and flipping from the point after the already sorted numbers.

It works for small arrays, but for larger arrays errors begin to occur when the placing one number in the correct position results in the next number to be sorted already at the end of the array, even though I have made a condition for that situation.

    public static void flipSort(int stack[], int arraySize)
    {
        int size = arraySize;     
 
 
        String output = "";
        int sortedStack = 0; 
 
        for(int i = 0; i < (size - 1); i++)
        {
 
            int hiNum = 0;
            int hiIndex = 0;
 
            for(int t = size - 1; t > sortedStack - 1; t-- )
            {
                if(stack[t] > hiNum)
                {
                    hiNum = stack[t];
                    hiIndex = t;
                }
            }
 
            if((hiIndex > sortedStack)) 
            {
                if((hiIndex + 1) == stack.length)
                {
                    output = output + (sortedStack + 1) + " ";
                }
                else
                {
                    output = output + (hiIndex + 1) + " ";
                    if(hiIndex != size-1)
                    {
                        output = output + (sortedStack + 1) + " ";
                    }
                }
                int[] tempStack = new int[size];
 
                int stackCount = 0;
 
                for(int a = 0; a < sortedStack-1; a++)
                {
                    tempStack[stackCount] = stack[a];
                    stackCount++;
                }
 
                tempStack[stackCount] = stack[hiIndex];
                stackCount++;
 
                for(int b = (hiIndex + 1); b < size; b++)
                {
                    tempStack[stackCount] = stack[b];
                    stackCount++;
                }
 
                for(int c = (hiIndex - 1); c >= sortedStack; c--)
                {
                    tempStack[stackCount] = stack[c];
                    stackCount++;
                }
 
                stackCount = 0;
 
                for(int g = 0; g < size; g++)
                {
                    stack[g] = tempStack[g];
                }
 
            }
            sortedStack++;
        }
        output = output + "0";
        System.out.println(output);
    }

Any advice would be much appreciated.

**Mr.777** · October 28th, 2011, 06:18 AM

1. How will we know, what are the deviations in your program?
2. Kindly ask the exact problem, you need us to look at and help you. No one will read this lengthy code.

**CaliforniaCoder1984** · October 28th, 2011, 07:26 AM

Sorry. I've edited the OP to make it a bit clearer. It was very late when I made the post initially. Hope this helps.

**Mr.777** · October 28th, 2011, 08:00 AM

for(int a = 0; a < sortedStack; a++)
                {
                    tempStack[stackCount] = stack[a];
                    stackCount++;
                }

Why it's not a<sortedStack-1 ?? Just a question or a hint as i don't know much about what you trying to do.

What is prevIndex???

for(int i = 0; i < (size - 1); i++)

Why your loop always start from 0 and iterate for "size" iterations?

I have tried stack[5,3,9,11,7,6] and after one complete iteration of your outer loop,
conditions were;
stack[11,7,9,3,5,6]
tempstack[11,7,9,3,5, ] Last index remained empty.
arraySize (6)
size (6)
output(4)
sortedStack (1)
stackCOunt (0)
PrevIndex (3)
hiNum(11)
hiIndex (3)

I just posted the status of all variables, may be this could help you out. And what are the logics, where i have asked you about in my post.

**CaliforniaCoder1984** · October 28th, 2011, 09:40 AM

Originally Posted by Mr.777

for(int a = 0; a < sortedStack; a++)
                {
                    tempStack[stackCount] = stack[a];
                    stackCount++;
                }

Why it's not a<sortedStack-1 ?? Just a question or a hint as i don't know much about what you trying to do.

Ah that is an error, thanks!
I'm still having the same problem though unfortunately.

Originally Posted by Mr.777

What is prevIndex???

Junk code from when I counted the next position as the previous index + 1. I'll remove that.

Originally Posted by Mr.777

for(int i = 0; i < (size - 1); i++)

Why your loop always start from 0 and iterate for "size" iterations?

The maximum amount of flips required is never higher than the array size, I think.

Originally Posted by Mr.777

I just posted the status of all variables, may be this could help you out. And what are the logics, where i have asked you about in my post.

That's very useful, much appreciated!

The basic logic behind the system:

*Find the largest integer that has an index higher than "sortedStack", which are already in the correct position

*If this integer is already in the correct position, no rotations required, just increase sortedStack by one

*Else if this integer is in the last position in the array, rotate from the position after sortedStack to from a situation like above

*Otherwise rotate the highest integer so it is in the last position in the array and then rotate at the position after sortedStack so it becomes sorted

*Fill a second temporary array with the new array positioning using the shown for loop logics

*Make the primary array equal to this temporary array

*Increase sortedStack by one as we now have another sorted number

Hope this helps. Thank you very much for your help so far

Thread: Flipping mechanism bug

LinkBack

Thread Tools

Display

Flipping mechanism bug

Related threads:

Re: Flipping mechanism bug

Re: Flipping mechanism bug

Re: Flipping mechanism bug

Re: Flipping mechanism bug

Similar Threads

Flipping a coin