Sorting Loop Not Sorting First Variable

Question

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!

Have you debugged this at all? You should be able to tell what it's doing by stepping through, line-by-line. Once you get it working, put a counter in your code and see how it behaves for 5, 10, 50, 100 length collections. That will give you an idea of the big-O complexity — Flydog57
– Flydog57, Commented Sep 18, 2021 at 23:43
No because I wanted to see what other suggestions people had as well as the time complexity. — Warmonger
– Warmonger, Commented Sep 19, 2021 at 15:22

bad_coder · Accepted Answer · 2021-09-19 01:18:59Z

1

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).

edited Sep 19, 2021 at 1:18

bad_coder

13.2k20 gold badges59 silver badges95 bronze badges

answered Sep 19, 2021 at 0:08

rutim

516 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Warmonger Over a year ago

I was trying to sort the array in linear time which, if @Mehrdad Dowlatabadi was right about the time complexity, I didn't do. BubbleSort is exponential. As far as achieving the intended result, what I was missing was resetting i to -1 instead of 0. So the example I provided was a poor one as I had a poor understanding of why the first value wouldn't switch. The reason it was 2135 instead of 3125 like i said it would be is because it will sort the first element as long as its greater than the second -- which I didn't catch; otherwise, the first element will never be sorted.

Mehrdad Dowlatabadi · Accepted Answer · 2021-09-19 01:02:33Z

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)

Collectives™ on Stack Overflow

Sorting Loop Not Sorting First Variable

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related