Sorting Loop Not Sorting First Variable-CodePudding

This is my first stack overflow post so sorry if its not in the right format. In any case, the following is in C# and I'm using Visual Studio 2019 .NET Core 3.1

Goal: Sorting an Array of integers in ascending order ex. [3, 2, 5, 1] -> [1, 2, 3, 5]

Problem: Method sorts everything but the first element ex. [3, 2, 5, 1] -> [3, 1, 2, 5]

Code:

for (int i = 0; i < array.Length; i  )
{
    if(i != array.Length - 1 && array[i] > array[i   1])
    {
        int lowerValue = array[i   1];
        int higherValue = array[i];

        array[i] = lowerValue;
        array[i   1] = higherValue;

        i = 0;
    }
}

I've put in Console.WriteLine() statements(one outside of the for loop above to see the starting array and one in the if statement to see how it updates the array when a change happens and yes I know I could use the debugger, but I don't currently have any method calls to the method this for loop is in) to see how its adjusting the array as it goes along and it will regularly show that its running through an iteration without changing anything.

Also if anyone could tell me what the time complexity of this is, that would be great. My initial guess is that its linear but I feel like with the "i = 0" statement and the way it swaps values makes it exponential. Thanks!

CodePudding user response：

When I run your code, I get 2135

As @Flydog57 says, it would be useful to go through every single step to notice when it doesn't run as desired. The code looks a bit like a BubbleSort without inner loop... The iteration also goes through only once. If I see it correctly, you are missing a multiple iteration. Have a look at the BubleSort.

My suggestion for the sorting looks like this:

int[] array = { 3, 2, 5, 1 };
var sortedArray = array.OrderBy(p => p).ToArray();

Regarding O notation, I am unfortunately a bit rusty and can't help. But for me it looks like O(n).

CodePudding user response：

Your algorithm is not a variant of bubble sort and it reset the loop counter when facing to descending order. in Bubble sort in every traverse, we are sure that the global max/min is in the right place but your algorithm is not sure about that till the execution for the last i. In your algorithm, the left part of the array is always partially ordered.

Firstly, the problem with your code is that after resetting the counter, the loop would add it up to 1(i ), therefore in your code, it can't be less than 1. if you set it to -1 it would sort the array, because after setting it to -1 the loop changes it to 0 and that's the desired behavior. The if block should be like this:

    if(i != array.Length - 1 && array[i] > array[i   1])
    {
        int lowerValue = array[i   1];
        int higherValue = array[i];

        array[i] = lowerValue;
        array[i   1] = higherValue;

        i = -1;
    }

The order of the algorithm: The worst-case happens when the array is in descending order, and in this case, for every i, The if condition would be true then the i would be reset to zero, therefore the total time complexity would be:

1 2 3 4 .. n(array length)= n(n 1)/2= O(n^2)