Solved

Bubble Sort

Posted on 2000-03-04
13
375 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

691 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