C#•2y ago

Bubble Sort

I have two implementations of bubble sort here; one is the model answer and one is mine. I am just wondering if my implementation would cover every possibility and sort correctly, or if I had somehow misapplied.

void BubbleSortModel(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = 0; j < arr.Length - 1; j++)
        {
            if (arr[j+1] < arr[j])
            {
                Swap(ref arr[j+1],ref arr[j]);
            }
        }
    }
}

void BubbleSortMine (int[] arr)
{
    for(int i = 0; i < arr.Length-1; i++)
    {
        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[j] < arr[i])
            {
                Swap(ref arr[i], ref arr[j]);
            }

        }
    }
}

void Swap(ref int x, ref int y)
{
    int temp = x;
    x = y;
    y = temp;
}

void BubbleSortModel(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = 0; j < arr.Length - 1; j++)
        {
            if (arr[j+1] < arr[j])
            {
                Swap(ref arr[j+1],ref arr[j]);
            }
        }
    }
}

void BubbleSortMine (int[] arr)
{
    for(int i = 0; i < arr.Length-1; i++)
    {
        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[j] < arr[i])
            {
                Swap(ref arr[i], ref arr[j]);
            }

        }
    }
}

void Swap(ref int x, ref int y)
{
    int temp = x;
    x = y;
    y = temp;
}

18 Replies

Tvde1•2y ago

Why don't you test it? 🙂 Have you heard of unit tests?

ero•2y ago

the code is identical nothing to test

Tvde1•2y ago

it's far from identical, right?

ero•2y ago

wdym "far from". one does the + 1 in the loop declaration, the other does it in the body it's identical

Tvde1•2y ago

the only difference is that j starts at i + 1 in the second method then (instead of at 0)

ero•2y ago

and what's i + 1 when i = 0? i would recon that's the same as j + 1 when j = 0 just a hunch the only thing that's different in the second version is the swap

surwren•2y ago

I've heard of them but I don't know how to conduct them they both yield the same result I've ran them through arrays I can see through debugging that the second one (mine) won't loop through as many times as the model answer does but I consistently get the right answer anyway and I'm confused as to why

canton7•2y ago

The important bit is that the model answer compares j with j+1, and yours compares i with j Yours isn't bubble sort. I'm sure there's some input which will trip yours up, trying to find it...

surwren•2y ago

yeah, the way the sort moves isn't the same I'm not even sure what mine is lol is it possible to get mine to a reliable output at all? if not it's fine, I'll just use the default bubble sort I know mine doesn't implement stuff well

canton7•2y ago

I think yours is solid actually, although I'm not sure what it's called

Kouhai•2y ago

Isn't their implementation selection sort? Well, with many more swaps 😅

canton7•2y ago

Yes, I think you're right Selection sort with many many swaps

surwren•2y ago

But simple selection swap has

smallestvalue

smallestvalue

, no?

canton7•2y ago

I'm not sure what you mean I'm afraid

surwren•2y ago

Ok assuming an ascending ordered simple selection swap, it holds the index of the smallest array value (for that loop) in some variable (I just labelled it SmallestValue). It then checks across the entire array for values smaller than the value located at arr[SmallestValue], switching indices as it goes along and finds/selects smaller values. It only performs the swap once it has reached the end of the line and therefore cannot find any smaller values to select. My question is thus: wouldn't my sort need some sort of selection holder to be considered a selection sort?

canton7•2y ago

But your version doesn't have a separate variable. It uses arr[i] as the variable inside the inner loop which holds the smallest item And it does swaps to change what's in arr[i]. So it's constantly shuffling the area of the array which is unsorted (but not in a way which affects the outcome), which is why we said it was like selection sort but with lots of swaps

surwren•2y ago

But your version doesn't have a separate variable.

That's my point I still dont know why it works 😔 Fluke moment

canton7•2y ago

It works as I just described It uses arr[i] as the smallestvalue variable

Gaming

Programming

Bubble Sort