CODEWITHSUNDEEP
c++bubble-sort
Moshe
Moshe

Reputation: 58097

How do I implement this bubble sort differently?

I'm looking to implement a bubble sort. I have the following code that I wrote, which uses a for loop inside of a do loop. How can I make this into a bubble sort that uses two for loops?

Here's my code:

do {
    switched = false;
    for (int i = 1; i < size; i++) {
        if (a[i] < a[i-1]) {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
} while (switched);

(This is tagged homework, but this is studying for the final exam, not actual homework.)

Upvotes: 2

Views: 446

Answers (8)

Blastfurnace
Blastfurnace

Reputation: 18652

A simple improvement to bubble sort is to remember the last location where a swap occurred. After each pass the elements beyond that point are sorted. Next time through the loop only iterate up to the previous high water mark.

void bubble_sort(int *arr, int size)
{
    for (int hwm; size > 1; size = hwm)
    {
        hwm = 0;
        for (int i = 1; i < size; ++i)
        {
            if (arr[i] < arr[i-1])
            {
                std::swap(arr[i], arr[i-1]);
                hwm = i;
            }
        }
    }
}

Upvotes: 1

corsiKa
corsiKa

Reputation: 82599

Because you know the last element in the list will always be sorted (since it bubbled up to the top) you can stop there.

for(int x = size; x >= 0; x--) {
    bool switched = false;
    for(int i = 1; i < x; i++) {
        if(blah) {
            // swap code here
            switched = true;
        }

    }
    if(!switched) break; // not the biggest fan of this but it gets the job done
}

Upvotes: 6

Daniel N
Daniel N

Reputation: 417

Since the maximum number of times your inner loop will run is size times, you know that the outer loop only can be bound by size.

for (int x = 0; x < size; x++ )
{
    switched = false;
    for (int i = 1; i < size; i++)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
            switched = true;
        }
    }

    if(switched)
    {
        break;
    }
}

Upvotes: 3

James Matta
James Matta

Reputation: 1570

A really silly method to use two for loops would be as follows:

for(bool switched=true;switched;)
{
    switched=false;
    for(int i=1; i<size; ++i)
    {
        if (a[i] < a[i-1]) 
        {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
}

A more serious answer might be as below... but now that I think about it this probably is not bubble sort:

for(int i=0; i<(size-1); ++i)
{
    for(int j=(i+1); j<(size-1); ++j)
    {
        if(a[i]>a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
}

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308530

Think about the maximum number of times the do loop can execute.

Upvotes: 0

sehe
sehe

Reputation: 393924

A bit obligate, but hey, you asked for it:

for(bool switched=true; switched;)
{
    switched = false;
    for (int i = 1; i < size; i++) {
        if (a[i] < a[i-1]) {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
}

Two for loops...

Upvotes: 5

ruakh
ruakh

Reputation: 183602

The first full pass through the loop (that is, the first iteration of your outer do loop) is guaranteed to put the largest element in position a[size - 1]. (Do you see why?) The next full pass is guaranteed not to change that, and, in addition, to put the second-largest element in position a[size - 2]. (Again, do you see why?) And so on. So the first pass needs i to go from 1 to size - 1, but the second only needs i to go from 1 to size - 2, the third only needs i to go from 1 to size - 3, and so on. Overall, you need at most size - 1 passes (with the last pass just covering position 1 and comparing a[1] to a[0] to make sure the smallest element is in place).

So, your outer for-loop needs to vary max_i, initially set to size - 1 and ending up at 1, and your inner for-loop needs to vary i from 1 to max_i.

Upvotes: 0

user97370
user97370

Reputation:

You can run the inside loop size times instead of checking switched, by having an outer loop for(int j=0; j<size; ++j). To make it slightly less badly inefficient you can make the inner loop 1 step shorter each time.

Upvotes: 0

Related Questions