Solved

Bubble Sort

Posted on 2000-03-04
13
362 Views
Last Modified: 2008-02-20
I have a small problem that I am working on and I cannot see what I am doing wrong.  I have an array of several strings and I need to sort each element alaphabetically. (Not the entire array, but each element must be sorted)  For example, "Howdy!" would turn into "!dHowy".  Here is the code I currently have:

#include <iostream.h>
#include <conio.h>
#include <iomanip.h>

void display(int *[], int);
void display(char *[], int);
void sort(char *);
void sort(int [], int);
void swap(char *, char *);

int main()
{
   int i;
   char *greet[] = {
                    "Howdy!\n",
                    "Greetings!\n",
                    "Buenos Dias!\n",
                    "Guten Tag!\n",
                    "G'Day!\n",
                    "Bonjour!\n",
                    "Hello!\n",
                    };
   //
   // Display the unsorted greetings for the user to see.
   //
        cout << "Displaying the greetings:" << endl;
        display(greet, (sizeof greet / sizeof (char*)));
   //
   // Sort the greetings one by one.
   //
      for (i = 0; i < (sizeof greet / sizeof (char*)); i++)
         sort(greet[i]);
   //
   // Display the sorted greetings for the user to see.
   //
      cout << "Displaying the greetings:" << endl;
      display(greet, (sizeof greet / sizeof (char*)));
   //
   // Stop to let the user see the data.
   //
      getch();
   //
   // Let the computer know everything is ok.
   //
      return 0;
}

void display(char *a[], int s)
{
   for(int i = 0; i < s; i++)
      cout << setw(15 + i) << a[i];
   cout << endl;
}

void sort(char *a)
{
   int counter = 0;
   char temp[2];
   char temp2[2];

   while (a[counter] != '\0')
   {
      counter++;
   }
   counter--;

   for(int i = 1; i < counter; i++)
   {
      for(int j = counter; j >=i; j--)
      {
         if(a[j-1] > a[j])
         {
            temp[0]= a[j];
            temp2[0] = a[j-1];
            //swap(temp, temp2);
            a[j] = temp2[0];
            a[j-1] = temp[0];
         }
      }
   }
}

void swap(char *a, char *b)
{
   char temp[2];
   temp[0] = a[0];
   //char temp2 = b[0];
   a[0] = b[0];
   b[0] = temp[0];
}


As soon as it gets to these lines it causes a access violation:
     a[j] = temp2[0];
     a[j-1] = temp[0];
Can anyone tell me what I am doing wrong.  If possible, also show me how I can utilize the swap() function instead of doing the swap inside the sort() function.
0
Comment
Question by:header
  • 5
  • 4
  • 2
  • +1
13 Comments
 

Expert Comment

by:aamit
Comment Utility
I think this might be for an assignment so I won't give you any code -

This program seems to work fine for me.
However I can see the following problems:

1. you don't really need char temp[2] (char temp) should do fine.
char temp;
if (blah )
{
temp = a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
2. This is an inefficient implementation - if there are no swaps performed in a given pass of the inner loop - your array is sorted and you can exit the sort
3. you should be encapsulating your string stuff into a class :)
4. swapping is very easy to implement - a good c++ book should have an example (check passing by reference examples)


0
 
LVL 3

Expert Comment

by:Try
Comment Utility
"header", where did you get this example from?  IOW, what prompted you to write this code?
0
 
LVL 2

Author Comment

by:header
Comment Utility
aamit, you are right.  This is a homework assignment and my teacher is not letting us use classes or string manipulation functions. (with the exception of 'sizeof')  He just wants us to do things the old fashion way to see what it takes.

aamit, did the strings sort correctly on your machine.  I am beginning to wonder if it is just my computer.  I went ahead and changed the code to your suggestion:
{
temp = a[j];
a[j]= a[j - 1];
a[j - 1] = temp;
}
however, I still get an access violation when it gets to "a[j]=a[j - 1];".
0
 

Expert Comment

by:aamit
Comment Utility
I checked it on solaris 2.6 (ultra10).


Try stepping through your code in a debugger (eg. dbx / gdb on unix ) .
set a breakpoint at the place where you get the access violation. Check the value of j to see if j or j-1 are out of bounds also check the value of a and *a to see if everything is correct.  
 


0
 
LVL 9

Expert Comment

by:Pacman
Comment Utility
header,

I compiled your code in Windows 98 development environment using visual c++ 5.0 with BoundsChecker instrumental build. This is a tool for detecting access vioalations and invalid memory operations.
Your code seems to be ok. There is no violation at all.
On which OS do you compile ?
which compiler ?
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
I did run his code and received the "Access violation" at the same place "header" has reported.

I am running Win 2000, using VC++ 6.0.  Interestingly, the VC++ debugger revealed that everything was in order; all the values were what they should have been, and the subscripts were what they also should have been.
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
LVL 3

Expert Comment

by:Try
Comment Utility
"Pacman," compiling a program and running it are two different things.  I compiled the program too, and received no error from doing so.  However, when I ran it, that was when I encountered the same error that "header" received.  I would be interested in finding out if when you executed the program, that it ran well for you without any error.  Did you even try executing it?

"aamit," since you have the question locked, did you run the program too, or are we talking only about having compiled it?  You said the program seemed to have worked fine for you.  What does that mean?

After my experience with the error, I did a lot of research into why the error occurred, and I found the reason.  After correcting the error, the program did run well afterwards.

Because of what the reason was, my feeling is doubtful that any of you ran the program and obtained an 'error free' result.
0
 
LVL 2

Author Comment

by:header
Comment Utility
Try, if you figured out the problem and fixed it, the points are yours.

(I am using Win 98/VC++ 6.0)
0
 
LVL 3

Accepted Solution

by:
Try earned 100 total points
Comment Utility
The reason why both you and I were getting the "Access violation" error message has to do with C/C++, the language.

After determining what the problem was, I fixed it, plus did a few extra things mainly cosmetic to make the output display look better.  Afterwards, I ran the program and it ran like a charm.  There is a little bit of cosmetic stuff left to be done, which I figured you could look into and finished up with.

The clue to the problem had to do with the way C/C++ treats an array.  Recall that the name of an array is a "constant pointer", meaning it cannot change what it is pointing to.  The second piece of realization is that an array of pointers to character, is an array of pointers to string, and this is where the pieces began fitting together, because each of those strings are arrays unto themselves with their names as constant pointers also.  (Constant pointers cannot be added to nor changed in any manner.  You can, however, modify what they're pointing to, if what they're pointing to have not been defined as a constant object.)

Anyway, here's what I did, and it works!

-------------------------------------

#include "stdafx.h"
#include <iostream.h>
#include <iomanip.h>


void display(char *[], int);
void sort(char *);


int main()
{
   int i;

   char greet1[] = {"Howdy!\n"};
   char greet2[] = {"Greetings!\n"};
   char greet3[] = {"Buenos Dias!\n"};

   char *greet[] = {greet1, greet2, greet3};

   cout << "Displaying the greetings: BEFORE ***\n" << endl;
   display(greet, (sizeof greet/sizeof(char*)));
   cout << '\n' << endl;

   // Sort the greetings one by one.
   //
   for(i=0; i<(sizeof greet/sizeof(char*)); i++)
       sort(greet[i]);

   cout << "Displaying the greetings: AFTER ***\n" << endl;
   display(greet, (sizeof greet/sizeof(char*)));
   cout << '\n' << endl;

   return 0;
}

void display(char *ar[], int sz)
{
   for(int i = 0; i < sz; i++)
      cout << setw(15 + i) << ar[i];

   cout << endl;
}

void sort(char a[])
{
   int cnt = 0, i, j;
   char temp;

   while (*(a+cnt) != '\0')
   {
      cnt++;
   }

   cnt -= 2;

   for(i=0; i<cnt; i++)
   {
      for(j=cnt; j>=i; j--)
      {
         if(*(a+j-1) > *(a+j))
         {
            temp = *(a+j);
            *(a+j) = *(a+j-1);
            *(a+j-1) = temp;
         }
      }
    }
}

------------------------------------

You will have to finish up on the cosmetic part as I stated earlier, but it works, meaning, it does the rearranging of the letters.

The reason for "cnt -= 2;" is because I wanted the count to end at "!" and not at "\n" which is an escape sequence character for newline.  Because "cnt" got incremented just before null was reached, that meant both null and "\n" had to be decremented from "cnt" in order for "!" to be positioned at the end.

As you can see, I only tested three members of the 'greet' array.  IOW, I just wanted to prove what I needed to do in order for the program to work.  You can fill in the rest of the greetings.

Lastly, I used pointer arithmetic to do the rearranging, but I also ran the program using regular array indexing.  Feel free to leave it the way it is, or change it to array indexing.  Either way, they both worked.

If you have any further question, don't hesitate.
0
 
LVL 2

Author Comment

by:header
Comment Utility
Try, well done! You deserve the points!
0
 
LVL 2

Author Comment

by:header
Comment Utility
Once again, thankyou!
0
 
LVL 9

Expert Comment

by:Pacman
Comment Utility
Try,

I've compiled the program and sure I started it !
0
 
LVL 3

Expert Comment

by:Try
Comment Utility
Yeah!  Right!
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now