By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,541 Members | 1,106 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,541 IT Pros & Developers. It's quick & easy.

Bubble sort, I just need information on it please.

JavaStudent07
P: 64
If you know anything about "Bubble Sorts" please leave it here, the teacher said, "Use bubble sort to sort numbers into decreasing numerical value." Then she started eating lunch and said we were on our own...LAME
Jan 25 '07 #1
Share this Question
Share on Google+
20 Replies


JavaStudent07
P: 64
I will be on tommorow to check it out,

thanks,
Steve
Jan 25 '07 #2

10K+
P: 13,264
If you know anything about "Bubble Sorts" please leave it here, the teacher said, "Use bubble sort to sort numbers into decreasing numerical value." Then she started eating lunch and said we were on our own...LAME
Maybe she was very hungry.

Read about it here then try to sort an array of integers using it.
Jan 25 '07 #3

JavaStudent07
P: 64
lol, that beast is always hungry, thanks i will try it
Jan 26 '07 #4

10K+
P: 13,264
lol, that beast is always hungry, thanks i will try it
Did you get it to work?
Jan 29 '07 #5

JavaStudent07
P: 64
err, its a start lol, still working things out, I have to import numbers from a data file somehow...
Jan 29 '07 #6

10K+
P: 13,264
err, its a start lol, still working things out, I have to import numbers from a data file somehow...
I suppose you are using Scanner or BufferedReader for reading the file? Anyway just post if you get stuck with the code.
Jan 29 '07 #7

JavaStudent07
P: 64
thanks for that option too :-P
Jan 29 '07 #8

JavaStudent07
P: 64
Expand|Select|Wrap|Line Numbers
  1. import java.io.*;
  2.  
  3. public class BubbleSort
  4. {
  5. public static void main (String args[]) throws IOException
  6. {
  7.  
  8. int List[];
  9. seekSort(List);
  10.  
  11.  
  12. try
  13.     {
  14.     File file=new File("H:/Triangles.java");
  15.     BufferedReader lineIn=new BufferedReader(new FileReader(file));
  16.     int intNumber=1;
  17.     String linetext;
  18.     while((linetext=lineIn.readLine())!=null)
  19.        System.out.println((intNumber++)+" "+linetext);
  20.     }
  21.   catch(FileNotFoundException e)
  22.    {
  23.     System.out.println("The file you entered was not found.");
  24.     System.exit(0);
  25.    }
  26.  catch(IOException d)
  27.   {
  28.    System.out.println("ERROR! please try again.");
  29.   }
  30. }
  31.  
  32. //V^V^V^V^V^V^V^V^V^V^V^V^^V^V^V^V^V^V^V^V^V^V^V^V^V^V^V^
  33. public static void seekSort()
  34. {
  35. int swapped=0;
  36. int swap=0;
  37.  
  38.  
  39.     while(swapped=0)
  40.     {
  41.         while(List(N)  List(N-1))
  42.            {
  43.        if List[N] > List[N + 1] 
  44.            {     
  45.        swap=List[N];
  46.        List[N]=List[N+1];
  47.        List[N+1]=swap;
  48.            }
  49.        swapped=0; 
  50.        }//end while
  51.         if(swapped==0)
  52.         {
  53.     swapped=1;
  54.         }
  55.     }//end while
  56. }
Jan 31 '07 #9

10K+
P: 13,264
Expand|Select|Wrap|Line Numbers
  1. import java.io.*;
  2.  
  3. public class BubbleSort
  4. {
  5. public static void main (String args[]) throws IOException
  6. {
  7.  
  8. int List[];
  9. seekSort(List);
  10.  
  11.  
  12. try
  13. {
  14. File file=new File("H:/Triangles.java");
  15. BufferedReader lineIn=new BufferedReader(new FileReader(file));
  16. int intNumber=1;
  17. String linetext;
  18. while((linetext=lineIn.readLine())!=null)
  19. System.out.println((intNumber++)+" "+linetext);
  20. }
  21. catch(FileNotFoundException e)
  22. {
  23. System.out.println("The file you entered was not found.");
  24. System.exit(0);
  25. }
  26. catch(IOException d)
  27. {
  28. System.out.println("ERROR! please try again.");
  29. }
  30. }
  31.  
  32. //V^V^V^V^V^V^V^V^V^V^V^V^^V^V^V^V^V^V^V^V^V^V^V^V^V^V^V^
  33. public static void seekSort()
  34. {
  35. int swapped=0;
  36. int swap=0;
  37.  
  38.  
  39.     while(swapped=0)
  40.     {
  41. while(List(N) List(N-1))
  42. {
  43.      if List[N] > List[N + 1] 
  44.      swap=List[N];
  45.      List[N]=List[N+1];
  46.      List[N+1]=swap;
  47. }
  48.      swapped=0; 
  49.      }//end while
  50. if(swapped==0)
  51. {
  52.     swapped=1;
  53. }
  54.     }//end while
  55. }
Is it working?
Feb 1 '07 #10

sangeetha jagannathan
P: 23
If you know anything about "Bubble Sorts" please leave it here, the teacher said, "Use bubble sort to sort numbers into decreasing numerical value." Then she started eating lunch and said we were on our own...LAME
hi
let me tell u what i know about bubble sort

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list via the swaps.

at the end of each pass the largest element in the list will reach its final position.

the pseudocode for this is

function bubble_sort(list L, number listsize)
loop
has_swapped := 0 //reset flag
for number i from 1 to (listsize - 1)
if L[i] > L[i + 1] //if they are in the wrong order
swap(L[i], L[i + 1]) //exchange them
has_swapped := 1 //we have swapped at least once, list may not be sorted yet
endif
endfor
//if no swaps were made during this pass, the list has been sorted
if has_swapped = 0
exit
endif
endloop
endfunction


Analysis

Worst-case performance
Bubble sort has worst-case complexity O(n2) on lists of size n. To see why, note that each element is moved no more than one step each time. No element can be more than a distance of n - 1 away from its final sorted position, so we use at most n - 1 = O(n) operations to move an element to its final sorted position, and use no more than (n - 1)2 = O(n2) operations in the worst case.

However, on a list where the smallest element is at the bottom, each pass through the list will only move it up by one step, so we will take n - 1 passes to move it to its final sorted position. As each pass traverses the whole list a pass will take n - 1 = O(n) operations. Thus the number of operations in the worst case is also o(n2). We have a tight worst-case complexity bound of O(n2).


Best-case performance
When a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. This means the list is already sorted. Thus bubblesort will take O(n) time when the list is completely sorted. It will also use considerably less time if the elements in the list are not too far from their sorted places.


however this algorithm is not considered to be the most efficient algorithm.

hope this is helpful to you
Feb 1 '07 #11

10K+
P: 13,264
hi
let me tell u what i know about bubble sort

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list via the swaps.

at the end of each pass the largest element in the list will reach its final position.

the pseudocode for this is

function bubble_sort(list L, number listsize)
loop
has_swapped := 0 //reset flag
for number i from 1 to (listsize - 1)
if L[i] > L[i + 1] //if they are in the wrong order
swap(L[i], L[i + 1]) //exchange them
has_swapped := 1 //we have swapped at least once, list may not be sorted yet
endif
endfor
//if no swaps were made during this pass, the list has been sorted
if has_swapped = 0
exit
endif
endloop
endfunction


Analysis

Worst-case performance
Bubble sort has worst-case complexity O(n2) on lists of size n. To see why, note that each element is moved no more than one step each time. No element can be more than a distance of n - 1 away from its final sorted position, so we use at most n - 1 = O(n) operations to move an element to its final sorted position, and use no more than (n - 1)2 = O(n2) operations in the worst case.

However, on a list where the smallest element is at the bottom, each pass through the list will only move it up by one step, so we will take n - 1 passes to move it to its final sorted position. As each pass traverses the whole list a pass will take n - 1 = O(n) operations. Thus the number of operations in the worst case is also o(n2). We have a tight worst-case complexity bound of O(n2).


Best-case performance
When a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. This means the list is already sorted. Thus bubblesort will take O(n) time when the list is completely sorted. It will also use considerably less time if the elements in the list are not too far from their sorted places.


however this algorithm is not considered to be the most efficient algorithm.

hope this is helpful to you
That's a lot of information.
Feb 1 '07 #12

JavaStudent07
P: 64
Yeah, lots of info, thanks I got that off of Wikipedia :) good stuff though, and no its not working yet...
Feb 2 '07 #13

10K+
P: 13,264
Yeah, lots of info, thanks I got that off of Wikipedia :) good stuff though, and no its not working yet...
Are you getting an error messages on compiling? What is happening with the code?
Feb 3 '07 #14

JavaStudent07
P: 64
Are you getting an error messages on compiling? What is happening with the code?
H:\>c:\j2sdk1.4.1\bin\javac.exe BubbleSort.java
BubbleSort.java:52: ')' expected
while(List[N] List[N-1])
^
BubbleSort.java:66: illegal start of expression
}//end while
^
BubbleSort.java:65: ';' expected
}
^
BubbleSort.java:67: '}' expected
}
^
BubbleSort.java:17: incompatible types
found : java.io.BufferedReader
required: java.io.FileReader
FileReader reader=new BufferedReader(reader);
^
BubbleSort.java:20: seekSort() in BubbleSort cannot be applied to (int[])
seekSort(List);
^
BubbleSort.java:50: incompatible types
found : int
required: boolean
while(swapped=0)
^
BubbleSort.java:52: cannot resolve symbol
symbol : variable List
location: class BubbleSort
while(List[N] List[N-1])
^
BubbleSort.java:52: cannot resolve symbol
symbol : variable N
location: class BubbleSort
while(List[N] List[N-1])
^
9 errors
Feb 5 '07 #15

10K+
P: 13,264
H:\>c:\j2sdk1.4.1\bin\javac.exe BubbleSort.java
BubbleSort.java:52: ')' expected
while(List[N] List[N-1])
^
BubbleSort.java:66: illegal start of expression
}//end while
^
BubbleSort.java:65: ';' expected
}
^
BubbleSort.java:67: '}' expected
}
^
BubbleSort.java:17: incompatible types
found : java.io.BufferedReader
required: java.io.FileReader
FileReader reader=new BufferedReader(reader);
^
BubbleSort.java:20: seekSort() in BubbleSort cannot be applied to (int[])
seekSort(List);
^
BubbleSort.java:50: incompatible types
found : int
required: boolean
while(swapped=0)
^
BubbleSort.java:52: cannot resolve symbol
symbol : variable List
location: class BubbleSort
while(List[N] List[N-1])
^
BubbleSort.java:52: cannot resolve symbol
symbol : variable N
location: class BubbleSort
while(List[N] List[N-1])
^
9 errors
Your code is really jumbled up. Why are you reading the file? D you want to sort numbers in a file? Where is the list that you want to sort?
Feb 6 '07 #16

P: 8
to know about c#
Feb 6 '07 #17

10K+
P: 13,264
to know about c#
You are so lost. Try the .Net forum.
Feb 6 '07 #18

JavaStudent07
P: 64
67 34 5 6 23 12
56 100 97 97 85
78 67 90
452 78 345 67 888 78

^^^^^The List of numbers I have to input one line at a time to sort from high to low and print^^^^^
Feb 6 '07 #19

10K+
P: 13,264
67 34 5 6 23 12
56 100 97 97 85
78 67 90
452 78 345 67 888 78

^^^^^The List of numbers I have to input one line at a time to sort from high to low and print^^^^^
Does each line contain a list of numbers or it one list of very large numbers with each number on its line?
Feb 6 '07 #20

JavaStudent07
P: 64
Does each line contain a list of numbers or it one list of very large numbers with each number on its line?
Four lists that I have to sort separately...this program is garbage, she should have broken it up into two programs, would have been MUCHO FACIL!
Feb 7 '07 #21

Post your reply

Sign in to post your reply or Sign up for a free account.