bubble sort algorithm doesn't sort negative values!

[redoktober]

hello!
on sunday, i was writing the bubble sort algorithm in java, to sort the contents of an array in ascending order.
it was part of a college assignment.
the next day, my practical instructor tests my program. first, he uses positive integers, and the bubble sort sorts them beautifully.
next, he enters negative values into the array.
and when he runs the bubble sort, it gives one helluva output!

Code: Select all

-3454 -4332 -7690 0 1232 4545

you see?
and when we sort the same array, with the same values using selection and insertion sort, it gives the right output.

Code: Select all

-7690 -4332 -3454 0 1232 4545

super weird.
now, i need to find out why this is happening, and i've completely lost it.


i'm attaching the java code listing for the bubble sort method. if you guys don't mind, can you please, please take a peek and give me a clue as to what's wrong??

thanks!

Code: Select all

 public void bubblesort()
 {
  int out, in;
  for(out=nElems-1;out>1;out--)
  {
   for(in=0;in<out;in++)
   {
    if(a[in]>a[in+1])
    {
     double temp=a[in];
     a[in]=a[in+1];
     a[in+1]=temp;
    }
   }
  }
 }

[Creature]

I don't do Java, but I think the problem is obviously here:

Code: Select all

 if(a[in]>a[in+1])

Of course it will work here because for example 5000 > 2000, but -5000 < -2000 so it will sort the negative values from largest to smallest instead of the other way around, I'm guessing.

[redoktober]

thanks, man!
lifesaver.

i guess i'll first have the method check if the number's negative or positive, and then act accordingly.

thanks yet again!

[Solar]

Of course it will work here because for example 5000 > 2000, but -5000 < -2000 so it will sort the negative values from largest to smallest instead of the other way around...

Erm... what?

[redoktober]

it's super strange. aren't all these algorithms supposed to be tried and tested, before being taught to innocent college-going students like us?

[Solar]

Your bubblesort() function works fine. (I tried it. In C, I admit, but I seriously doubt Java defines the operator > any different.) Your problem is outside that function, or the function your instructor tested is not the one you posted here.

Post the complete code, including the starting values of the array and the output code.

[redoktober]

okay.
here goes.
i'm sorry, i don't have access to a JDK right now, so i'm just posting the code.

Code: Select all

//DSDemo source code.

//Rudraksh MK, The HackerLabs Foundation, 26 July 2009 AD 

import java.io.*; 
 

class DSArray

{

private double[] a;

private int nElems; 

public DSArray(int max)

{

  a=new double[max];

  nElems=0;

} 

public void linear_search(double searchKey)

{

  int j;

  for(j=0; j<nElems; j++)

  {

   if(a[j]==searchKey)

   {

    System.out.println("Element found at index " + j+ ".");

   }

   else

   {

    System.out.println("Element not found.");

   }

  }

} 

public void binary_search(double searchKey)

{

  int high=a.length;

  int low=0;

  int mid; 

  while(low<=high)

  {

   mid=(high+low)/2;

   if(searchKey==a[mid])

   {

    System.out.println("Element found at index " + mid + ".");

   }

   else if(searchKey<a[mid])

   {

    high=mid-1;

   }

   else

   {

    low=mid+1;

   }

  }

} 

public void insert(double value)

{

  a[nElems]=value;

  nElems++;

} 

public boolean delete(double value)

{

  int j;

  for(j=0;j<nElems;j++)

  {

   if(value==a[j])

   {

    break;

   }

   if(j==nElems)

   {

    return false;

   }

   else

   {

    for(int k=j;k<nElems;k++)

    {

     a[k]=a[k+1];

     nElems--;

     return true;

    }

   } 

  }

  return false;

} 

public void display()

{

  for(int g=0;g<nElems;g++)

  {

   System.out.print(a[g] + " ");

  }

  System.out.println();

} 
 

public void bubblesort()

{

  int out, in;

  for(out=nElems-1;out>1;out--)

  {

   for(in=0;in<out;in++)

   {

    if(a[in]>a[in+1])

    {

     double temp=a[in];

     a[in]=a[in+1];

     a[in+1]=temp;

    }

   }

  }

}

 

public void selectionsort()

{

  int out, in, min;

  for(out=0;out<nElems-1;out++)

  {

   min=out;

   for(in=out+1;in<nElems;in++)

   {

    if(a[in]<a[min])

    {

     min=in;

     double temp=a[out];

     a[out]=a[min];

     a[min]=temp;

    }

   }

  }

} 

public void insertionsort()

{

  int in, out;

  for(out=1;out<nElems;out++)

  {

   double temp=a[out];

   in=out;

   while(in>0 && a[in-1]>=temp)

   {

    a[in]=a[in-1];

    --in;

  }

   a[in]=temp;

  }

} 

} 
 

class DSStack

{

private int maxSize;

private double[] s;

private int top; 

public DSStack(int size)

{

  maxSize=size;

  s=new double[maxSize];

  top= -1;

} 

public void push(double j)

{

  s[++top]=j;

} 

public double pop()

{

  return s[top--];

} 

public double peek()

{

  return s[top];

} 

} 
 

class DSQueue

{

private int maxSize;

private int [] q;

private int front;

private int rear;

private int nItems; 

public DSQueue(int size)

{

  maxSize=size;

  q=new int[maxSize];

  front=0;

  rear= -1;

  nItems=0;

} 

public void insert(int j)

{

  if(rear==maxSize-1)

  {

   rear= -1;

  }

  q[++rear]=j;

  nItems++;

} 

public int remove()

{

  int temp=q[front++];

  if(front==maxSize)

  {

   front=0;

  }

  nItems--;

  return temp;

} 

public int peek()

{

  return q[front];

} 

public int size()

{

  return nItems;

}

} 

class DSDemo

{

static public void DSA(int size2) throws IOException

{

  DSArray dsa = new DSArray(size2);

  DataInputStream dsr1 = new DataInputStream(System.in);

  System.out.println("Please enter elements...");

  for(int f=0;f<size2;f++)

  {

   dsa.insert(Double.parseDouble(dsr1.readLine()));

  }

  System.out.println("Displaying elements...");

  dsa.display();

  System.out.println("Would you like to delete an element?(y/n)");

  String input;

  char reply;

  input=dsr1.readLine();

  reply=input.charAt(0);

  if(reply=='y')

  {

   System.out.println("Please enter the element you wish to delete.");

   double value2=Double.parseDouble(dsr1.readLine());

   dsa.delete(value2);

  }

  System.out.println("Remaining elements=>");

  dsa.display();

  System.out.println("Applying Bubble, Selection and Insertion sorts...");

  System.out.println();

  dsa.bubblesort();

  dsa.display();

  System.out.println();

  dsa.selectionsort();

  dsa.display();

  System.out.println();

  dsa.insertionsort();

  dsa.display();

  System.out.println();

  System.out.println("Would you like to search for an element?(y/n)");

  input=dsr1.readLine();

  reply=input.charAt(0);

  if(reply=='y')

  {

   double sk;

   System.out.println("Please enter searchKey: ");

   sk=Double.parseDouble(dsr1.readLine());

   dsa.linear_search(sk);

   System.out.println();

  // dsa.binary_search(sk);

  // System.out.println();

  }

} 

public static void DSS(int s3) throws IOException

{

  DSStack dss = new DSStack(s3);

  DataInputStream dsr2 = new DataInputStream(System.in);

  String input;

  char reply;

  System.out.println("Please enter items to push onto the stack: ");

  for(int t=0;t<s3;t++)

  {

   dss.push(Double.parseDouble(dsr2.readLine()));

  }

  System.out.println("Would you like to pop an item off the stack?(y/n)");

  input=dsr2.readLine();

  reply=input.charAt(0);

  if(reply=='y')

  {

   double value=dss.pop();

   System.out.println("You just popped " + value);

  }

  double peekvalue=dss.peek();

  System.out.println("The topmost value on the stack is " + peekvalue);

} 
 

public static void DSQ(int s4) throws IOException

{

  DSQueue dsq = new DSQueue(s4);

  DataInputStream dsr3 = new DataInputStream(System.in);

  String input;

  char reply;

  System.out.println("Please enter elements to arrange in the queue: ");

  for(int u=0;u<s4;u++)

  {

   dsq.insert(Integer.parseInt(dsr3.readLine()));

  }

  System.out.println("The value at the front of the queue is ");

  int peekvalue=dsq.peek();

  System.out.print(peekvalue);

  System.out.println("Would you like to delete the front item from the queue?(y/n)");

  input=dsr3.readLine();

  reply=input.charAt(0);

  if(reply=='y')

  {

    int deletedvalue=dsq.remove();

    System.out.println("the deleted value is " + deletedvalue);

    System.out.println("the front value is now ");

    peekvalue=dsq.peek();

    System.out.print(peekvalue);

  }

} 
 
 

public static void main(String args[]) throws IOException

{

  DataInputStream dsr = new DataInputStream(System.in);

  System.out.println("Welcome to DSDemo! Please enter your choice according to the list below: ");

  System.out.println("Enter 1 for Arrays.");

  System.out.println("Enter 2 for Stacks.");

  System.out.println("Enter 3 for Queues.");

  int choice;

  choice=Integer.parseInt(dsr.readLine());

  switch(choice)

  {

   case 1:

           System.out.println("Enter array size: ");

           int size3=Integer.parseInt(dsr.readLine());

           System.out.println("Going to DSA()...");

           DSA(size3);

           break;

   case 2:

           System.out.println("Enter stack size: ");

           int size4=Integer.parseInt(dsr.readLine());

           DSS(size4);

           break;

   case 3:

           System.out.println("Enter queue size: ");

           int size5=Integer.parseInt(dsr.readLine());

           DSQ(size5);

           break;

  } 

} 
 

} 
 

   

you asked.

[Solar]

*sigh*

• What's with the double linefeeds?
• A file attachment would have been handy.
• Rule #1 of Debugging: Reduce the problem. Cut away any code that's not strictly necessary to reproduce the problem. Most often, this already gives you the answer.

I'll see if I find the time to do #3 for you...

[Solar]

Cannot reproduce. All three algorithms sort just fine.

Code: Select all

Welcome to DSDemo! Please enter your choice according to the list below:
Enter 1 for Arrays.
Enter 2 for Stacks.
Enter 3 for Queues.
1
Enter array size:
6
Going to DSA()...
Please enter elements...
-3456
0
74
-6453
64
3298
Displaying elements...
-3456.0 0.0 74.0 -6453.0 64.0 3298.0
Would you like to delete an element?(y/n)
n
Remaining elements=>
-3456.0 0.0 74.0 -6453.0 64.0 3298.0
Applying Bubble, Selection and Insertion sorts...

-6453.0 -3456.0 0.0 64.0 74.0 3298.0

-6453.0 -3456.0 0.0 64.0 74.0 3298.0

-6453.0 -3456.0 0.0 64.0 74.0 3298.0

Would you like to search for an element?(y/n)
n

[pcmattman]

In addition to Solar's remarks,

and when he runs the bubble sort, it gives one helluva output!

That's not helpful - the least you can do is post the expected as well as the actual output.

[Solar]

Um... he did, in the very next line.

[pcmattman]

And he did too. I dunno how I missed that . Sorry!

[Creature]

Of course it will work here because for example 5000 > 2000, but -5000 < -2000 so it will sort the negative values from largest to smallest instead of the other way around...

Erm... what?

I guess I wasn't paying enough attention while replying, my mistake, nevermind what I said

[redoktober]

you guys are geniuses.


thanks a billion!

[Solar]

you guys are geniuses.

Thanks...

...I guess.

Erm...

...for what?