CODEWITHSUNDEEP
c++stringsorting
vishal_khanna
vishal_khanna

Reputation: 57

Error in program for modified bubble sort

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;
}

Upvotes: 0

Views: 144

Answers (4)

Deepesh Meena
Deepesh Meena

Reputation: 135

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;
    }
}

Upvotes: 0

simonc
simonc

Reputation: 42175

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)

Upvotes: 0

Christopher Creutzig
Christopher Creutzig

Reputation: 8774

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.

Upvotes: 1

Noam Rathaus
Noam Rathaus

Reputation: 5598

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

Upvotes: 0

Related Questions