Error in program for modified bubble sort

Question

Codeforces problem 339A-http://codeforces.com/problemset/problem/339/A

I have tried to sort the values stored at even places of the array(starting from 0).I get an error while running the program or program returns a junk value.What is wrong with my solution?

My solution:

#include<iostream>
#include<cstring>

using namespace std;

int main()
{
    char s[101],temp;
    int i,j;

    cin>>s;

    for(i=0;i<strlen(s);i+=2) //Bubble sorting values at even values of i.'+' is stored at odd values of i.
    {
        for(j=0;j<(strlen(s)-i-2);j+=2)
        {
            if(s[j]>s[j+2])
            {
                temp=s[j];
                s[j]=s[j+2];
                s[j+2]=temp;
            }
        }
    }

    cout<<s;
}

You are answering the question completely wrong, the + is a delimiter, it doesn't mean that numbers are only one digit, not to mention that the input is 1+1+3+1+3 (example), and your code won't do anything meaningful with it — Noam Rathaus
– Noam Rathaus, Commented Dec 31, 2013 at 15:49
@nrathaus The numbers are only 1, 2, 3, so they are one digit, no spaces. The approach seems sound. — Christopher Creutzig
– Christopher Creutzig, Commented Dec 31, 2013 at 15:51
@nrathaus - The numbers are all in the set {1,2,3} so this approach is valid and sensible. — JoeG
– JoeG, Commented Dec 31, 2013 at 15:51
For this question it might be sound, but I don't think it is teaching you to do stuff in the right way — Noam Rathaus
– Noam Rathaus, Commented Dec 31, 2013 at 15:52

Christopher Creutzig · Accepted Answer · 2013-12-31 16:00:23Z

1

Your compiler should have warned you about the problem (you did switch on all warnings, yes? always do that!): Once i==strlen(s)-1, the loop for j is essentially unbounded, by the magic of arithmetic rules for signed/unsigned values.

for(unsigned j=0; j+2+i < strlen(s); j+=2)

does not have this problem. (i should be unsigned as well.)

Or stop the loop for i earlier. The problem in your code is still there then, but you won’t run into it. But I believe that is the worse route to take – fix the bug, and then optimize by observing i doesn’t need to go as far up, because the last character already forms a sorted sequence.

answered Dec 31, 2013 at 16:00

Christopher Creutzig

8,77437 silver badges46 bronze badges

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

Comments

simonc · Accepted Answer · 2013-12-31 17:12:48Z

0

For odd lengths len of s, the outer loop runs until i==len-1. The inner loop then terminates at len - len - 1 - 2. Since strlen returns an unsigned type, this evaluates to a very large unsigned number, causing the inner loop to read way beyond the end of s. Eventually you'll reach memory you don't have access to read or write, causing the crash.

You can fix this by ending the outer loop sooner

int len = strlen(s);
for(i=0;i<len-2;i+=2) {
    for(j=0;j<(len-i-2);j+=2)

edited Dec 31, 2013 at 17:12

answered Dec 31, 2013 at 15:58

simonc

42.3k12 gold badges91 silver badges105 bronze badges

1 Comment

Christopher Creutzig Over a year ago

You are missing the point: len is unsigned, so len - (len - 1) - 2 will be a large positive value. If it were -3, there would not be a problem, the loop would immediately terminate. Try it: for(j=0; j<static_cast<int>(strlen(s))-i-1; j+=2) works just fine.

Noam Rathaus · Accepted Answer · 2013-12-31 15:55:48Z

0

Change this:

 for(i=0;i<strlen(s);i+=2)

Into this:

 for(i=0;i<strlen(s) - 2;i+=2)

Otherwise the s value be handled beyond its end-point

edited Dec 31, 2013 at 15:55

answered Dec 31, 2013 at 15:50

Noam Rathaus

5,6082 gold badges31 silver badges37 bronze badges

5 Comments

simonc Over a year ago

Why does that matter? Won't the next line - cin>>s; - initialise s up to a nul terminator?

Noam Rathaus Over a year ago

@simonc, sorry I thought the wrong cause of the exception, fixed

Noam Rathaus Over a year ago

See @simonc 's explanation, basically because the len reaches (before) strlen(s) - 1, the inner loop did strlen(s) - (strlen(s) - 1) - 2, which meant -1-2 => -3, which is out of bound

RichardPlunkett Over a year ago

shouldnt it be "-1" ?

Noam Rathaus Over a year ago

No because he is jumping by "2"

Deepesh Meena · Accepted Answer · 2017-08-15 20:26:23Z

0

here is my code

void bubble(int a[], int n){
    for(int i=0; i<n; i++){
        int swaps=0;
        for(int j=0; j<n-i-1; j++){
            if(a[j]>a[j+1]){
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                swaps++;
            }
        }
        if(swaps==0)
            break;
    }
}

answered Aug 15, 2017 at 20:26

Deepesh Meena

1352 silver badges13 bronze badges

1 Comment

Kai Over a year ago

Please provide more detail on what this does and how it answers the question

Collectives™ on Stack Overflow

Error in program for modified bubble sort

4 Answers 4

Comments

1 Comment

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related