Page 1 of 2
bubble sort algorithm doesn't sort negative values!
Posted: Tue Jul 28, 2009 7:47 am
by 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!
you see?
and when we sort the same array, with the same values using selection and insertion sort, it gives the right output.
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;
}
}
}
}
Re: bubble sort algorithm doesn't sort negative values!
Posted: Tue Jul 28, 2009 9:29 am
by Creature
I don't do Java, but I think the problem is obviously here:
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.
Re: bubble sort algorithm doesn't sort negative values!
Posted: Tue Jul 28, 2009 6:33 pm
by 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!
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 12:25 am
by Solar
Creature wrote: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? 
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 12:43 am
by 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?
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 12:56 am
by 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.
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 1:04 am
by 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.
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 1:57 am
by 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...
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 2:02 am
by 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
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 2:32 am
by 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.
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 2:37 am
by Solar
Um... he did, in the very next line.
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 2:48 am
by pcmattman
And he did too. I dunno how I missed that
. Sorry!
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 3:38 am
by Creature
Solar wrote:Creature wrote: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
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 4:23 am
by redoktober
you guys are geniuses.
thanks a billion!
Re: bubble sort algorithm doesn't sort negative values!
Posted: Wed Jul 29, 2009 5:17 am
by Solar
redoktober wrote:you guys are geniuses.
Thanks...
...I guess.
Erm...
...for what?