Solved

Bubble Sort

Posted on 2000-03-04
13
367 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
ID: 2584235
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
ID: 2584635
"header", where did you get this example from?  IOW, what prompted you to write this code?
0
 
LVL 2

Author Comment

by:header
ID: 2584924
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
ID: 2586322
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
ID: 2586765
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
ID: 2586941
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 3

Expert Comment

by:Try
ID: 2588958
"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
ID: 2589531
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
ID: 2589868
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
ID: 2589956
Try, well done! You deserve the points!
0
 
LVL 2

Author Comment

by:header
ID: 2589960
Once again, thankyou!
0
 
LVL 9

Expert Comment

by:Pacman
ID: 2590527
Try,

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

Expert Comment

by:Try
ID: 2590715
Yeah!  Right!
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
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.

912 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

15 Experts available now in Live!

Get 1:1 Help Now