4

I have an integer array int[] number = { 3,4,2,5,1};

The minimum number of steps to sort it should be 2. But I am getting 4.

static void Main(string[] args)
        {
            int[] number = { 3,4,2,5,1};

           int result =  get_order(number);

            Console.ReadKey();
        }

        public static int get_order(int[] input1)
        {
            input1 = input1.OrderByDescending(o => o).ToArray();
            bool flag = true;
            int temp;
            int numLength = input1.Length;
            int passes = 0;

            for (int i = 1; (i <= (numLength - 1)) && flag; i++)
            {
                flag = false;
                for (int j = 0; j < (numLength - 1); j++)
                {
                    if (input1[j + 1] > input1[j])
                    {
                        temp = input1[j];
                        input1[j] = input1[j + 1];
                        input1[j + 1] = temp;
                        flag = true;
                    }
                }
                passes++;
            }
            return passes+1;
        }

What is the problem and what changes i need to do in my code?

Edit

implement @Patashu, algorithm, 

public static int get_order(int[] input1)
        {
            var sorterArray = input1.OrderByDescending(o => o).ToArray();
            var unsortedArray = input1;
            int temp1;
            int swap = 0;

            int arrayLength = sorterArray.Length;
            for (int i = 0; i < arrayLength; i++)
            {
                if (sorterArray[i] != unsortedArray[i])
                {
                    temp1 = unsortedArray[i];
                    unsortedArray[i] = sorterArray[i];
                    for (int j = i + 1; j < arrayLength; j++)
                    {
                        if (unsortedArray[j] == sorterArray[i])
                        {
                            unsortedArray[j] = temp1;
                            swap++;
                            break;
                        }
                    } 
                }
            }

            return swap;
        }
Improve this question
2
  • 2
    What do you define as a "step"? Also it's descending in this case? Commented Jun 13, 2013 at 4:00
  • but i need to find out how many minimum steps it takes to sort...how will i do it using linq? Commented Jun 13, 2013 at 4:01

6 Answers 6

Reset to default
3

The problem with your algorithm is that it only attempts swapping adjacent elements.

3,4,2,5,1 is best sorted by swapping 3 with 5, which is an unadjacent swap, and then 2 with 3.

So, I suggest that you will find a better algorithm by doing the following:

1) First, sort the array into descending order using the built in sorting function of C#.

2) Now, you can use this sorted array as a comparison - iterate through the array from left to right. Every time you see an element in the unsorted array that is != to the element in the same space in the sorted array, look deeper into the unsorted array for the value the sorted array has there, and do one swap.

e.g.

3,4,2,5,1

Sort using Sort -> 5,4,3,2,1 is our sorted array

3 is != 5 - look in unsorted array for 5 - found it, swap them.

Unsorted is now 5,4,2,3,1

4 == 4

2 is != 3 - look in unsorted array for 3 - found it, swap them.

Unsorted is now 5,4,3,2,1

2 == 2

1 == 1

We're at the end of the unsorted array and we did two swaps.

EDIT: In your algorithm implementation, it looks almost right except

instead of

unsortedArray[j] = sorterArray[i];
unsortedArray[i] = temp1;

you had it backwards, you want

unsortedArray[j] = temp1;
unsortedArray[i] = sorterArray[i];
Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

This is what I was thinking as well. Somewhat similar to Levenshtein distance for strings?
I'm not convinced by this method at all. Unless you brute force all possible swaps you are not going to arrive at the optimal solutions. It is extremely convenient that it even works out for this case.
@ZongZhengLi You are saying it is not possible to write this algorithm faster than O(n^2)?
@Patashu No, I'm saying this method as it currently stands does not find the correct value. And brute forcing all swaps would be something like O(n!) I think anyways. I'm not sure what is possible since the OP has not rigorously defined the operations we are allowed to use.
@ZongZhengLi Can you think of an example that foils the algorithm?
|
2

Since you're asking why you're getting 4 steps, and not how to calculate the passes, the correct way to do this is to simply step through your code. In your case the code is simple enough to step through on a piece of paper, in the debugger, or with added debug statements.

Original: 3, 4, 2, 5, 1

Pass: 1: 4, 3, 5, 2, 1
Pass: 2: 4, 5, 3, 2, 1
Pass: 3: 5, 4, 3, 2, 1
Pass: 4: 5, 4, 3, 2, 1

Basically what you see is that each iteration you sort one number into the correct position. At the end of pass one 2 is in the correct position. Then 3, 4, 5.

Ah! But this is only 3 passes you say. But you're actually incrementing passes regardless of flag, which shows you that you actually did one extra step where the array is sorted (in reverse order) but you didn't know this so you had to go through and double check (this was pass 4).

Improve this answer

Comments

1

To improve performance, you do not need to start checking the array from the beginning. Better than the last equal element.

static int MinimumSwaps(int[] arr)
{
    int result = 0;
    int temp;
    int counter = 0;
    for (int i = 0; i < arr.Length; ++i)
    {
        if (arr[i] - 1 == i)
        {
            //once all sorted then
            if(counter==arr.Length)break;
            counter++;
            continue;
        }
        temp = arr[arr[i]-1];
        arr[arr[i] - 1] = arr[i];
        arr[i] = temp;
        result++;//swapped
        i = counter ;//needs to start from the last equal element
    }
    return result;
}
Improve this answer

1 Comment

I have copied/pasted your code, it fails due to the "Index was outside the bounds of the array"...
0

At the start:

{ 3,4,2,5,1}; // passes = 0

Round 1 reuslt:

{ 4,3,2,5,1};
{ 4,3,5,2,1}; // passes = 1

Round 2 reuslt:

{ 4,5,3,2,1}; // passes = 2

Round 3 reuslt:

{ 5,4,3,2,1}; // passes = 3 and flag is set to true

Round 4 reuslt:

{ 5,4,3,2,1}; // same result and passes is incremented to be 4
Improve this answer

Comments

0

You fail to mention that the array is supposed to be sorted in descending order, which is usually not the default expected behavior (at least in "C" / C++). To turn:

3, 4, 2, 5, 1

into:

1, 2, 3, 4, 5

one indeed needs 4 (non-adjacent) swaps. However, to turn it into:

5, 4, 3, 2, 1

only two swaps suffice. The following algorithm finds the number of swaps in O(m) of swap operations where m is number of swaps, which is always strictly less than the number of items in the array, n (alternately the complexity is O(m + n) of loop iterations):

int n = 5;
size_t P[] = {3, 4, 2, 5, 1};

for(int i = 0; i < n; ++ i)
    -- P[i];
// need zero-based indices (yours are 1-based)

for(int i = 0; i < n; ++ i)
    P[i] = 4 - P[i];
// reverse order?

size_t count = 0;
for(int i = 0; i < n; ++ i) {
    for(; P[i] != i; ++ count) // could be permuted multiple times
        std::swap(P[P[i]], P[i]); // look where the number at hand should be
}
// count number of permutations

This indeed finds two swaps. Note that the permutation is destroyed in the process. The test case for this algorithm can be found here (tested with Visual Studio 2008).

Improve this answer

Comments

0

Here is the solution for your question :)

static int MinimumSwaps(int[] arr)
    {
        int result = 0;
        int temp;
        int counter = 0;
        for (int i = 0; i < arr.Length; ++i)
        {
            if (arr[i] - 1 == i)
            {
                //once all sorted then
                if(counter==arr.Length)break;
                counter++;
                continue;
            }
            temp = arr[arr[i]-1];
            arr[arr[i] - 1] = arr[i];
            arr[i] = temp;
            result++;//swapped
            i = 0;//needs to start from the beginning after every swap
            counter = 0;//clearing the sorted array counter
        }
        return result;
    }
Improve this answer

1 Comment

I have copied/pasted your code, it fails due to the "Index was outside the bounds of the array"... –

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.