Code Snippets

Java Source Code

Welcome to Dream.In.Code
	Become a Java Expert! Join 137,226 Java Programmers for FREE! Get instant access to thousands of Java experts, tutorials, code snippets, and more! There are 2,033 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a Java Expert

Bubble Sort

Bubble sort with a few improvements made so that the best-case run time for this algorithm will be n.

Submitted By: Dark_Nexus

Actions:

Rating:

Views: 334

Language: Java

Last Modified: August 29, 2008

Instructions: This class has a Sort method which takes an array of Integer's. The class will then sort that array and return it.

Snippet

class BubbleSort
{
private Integer[] list;
private void bubbleSort()
{
/*Sorts the list "sorted" by use of the bubble sort
algorithm with a few "improvements" made. The first improvement
uses a boolean value to detect whether swaps were during a pass.
If no swaps were made, then the list is sorted and no furuther passes
are required. The second optimization is the limit placed on the
range of the inner for loop. After each pass, the the element at
index n - i has been placed properly, where n is the length of the list.
Thus, there is no need to look at the value again when making future
passes*/
Integer tmp = null; //Temporary variable for swapping
boolean hasSwapped = false; //Boolean value to flag whether swaps were made
int len = list.length - 1; //The pre-calculated index of the last element in the array
for (int i = 0;i < len;i++)
{
hasSwapped = false; //Initialize hasSwapped to false for each pass
for (int s = 0;s < len - i;s++)
{
//If this element is greater than the next element
if (list[s] > list[s + 1])
{
//Swap the elements
tmp = list[s];
list[s] = list[s + 1];
list[s + 1] = tmp;
hasSwapped = true; //Flag that a swap has been made
}
}
//If no swaps were made (sorting is complete)
if (hasSwapped == false)
return; //End the sort
}
}
public Integer[] sort(Integer[] unsorted)
{
/*Initializes the list to be sorted as the copy list passed
and then invokes a bubble sort algorithm on that list. The
resulting sorted list will then be returned*/
list = unsorted;
bubbleSort();
return list;
}
BubbleSort()
{
/*Default constructor*/
list = null;
}
}

Copy & Paste

class BubbleSort
{
     private Integer[] list;

private void bubbleSort()
     {
          /*Sorts the list "sorted" by use of the bubble sort
            algorithm with a few "improvements" made.  The first improvement
            uses a boolean value to detect whether swaps were during a pass.
            If no swaps were made, then the list is sorted and no furuther passes
            are required.  The second optimization is the limit placed on the 
            range of the inner for loop.  After each pass, the the element at 
            index n - i has been placed properly, where n is the length of the list.
            Thus, there is no need to look at the value again when making future
            passes*/

Integer tmp = null;          //Temporary variable for swapping
          boolean hasSwapped = false;     //Boolean value to flag whether swaps were made
          int len = list.length - 1;     //The pre-calculated index of the last element in the array

for (int i = 0;i < len;i++)
          {
               hasSwapped = false; //Initialize hasSwapped to false for each pass

for (int s = 0;s < len - i;s++)
               {
                    //If this element is greater than the next element
                    if (list[s] > list[s + 1])
                    {
                         //Swap the elements
                         tmp = list[s];
                         list[s] = list[s + 1];
                         list[s + 1] = tmp;
               
                         hasSwapped = true;     //Flag that a swap has been made
                    }
               }

//If no swaps were made (sorting is complete)
               if (hasSwapped == false)
                    return;     //End the sort
          }
     }

public Integer[] sort(Integer[] unsorted)
     {
          /*Initializes the list to be sorted as the copy list passed
             and then invokes a bubble sort algorithm on that list.  The
            resulting sorted list will then be returned*/

list = unsorted;

bubbleSort();
     
          return list;
     }
     
     BubbleSort()
     {
          /*Default constructor*/
          list = null;
     }
}