HOME CONTENTS

This website is underconstruction. Author: Martin Sykes Challenge: I have challenged myself to 1 article per day, and framework improvements! Enjoy Challenge end: unknown

Bubble Sort

Combined learning sample

Bubble sort is a method of sorting numbers, in to numerical order, accending or decending, it is one of the easier methods because it does not need the creation of a temporary array. However it is still difficult and will show everything you have learn't up until now.
Covers:

• Variables
• Arrays
• Input / Output
• IF / ELSE
• LOOPS
• FUNCTIONS

This sample will create an array of 50 integers, begin a loop asking the user for random un-ordered numbers, exit the loop if the user enters a number less than 0, we will then create the bubble sort function and call it to sort the new array, finaly we will print the sorted array back to the user.

STEP 1/4

Create a project, name it bubblesort and create the main class as in all the other examples.

STEP 2/4

This is the main function, you will be able to copy and run this example, since I remarked the bubbleSort bit, it will ask the user for up to 50 numbers and print the unsorted array back to the user.

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

// create our memory up to 50 whole numbers
int i; // incrementer
int[] numbers = new int[50];
String strInput; // last time I checked keyboards had letters on them aswell as 0-9 so handle as string
int intInput;
// set the initial values of our memory all to 0
for(i=0 /* no int since it was declared above */; i<numbers.length; i++)
/* note no {

} on for, since I know only 1 line of code */
numbers[i] = -1;
// create a keyboard reader (input)
InputStreamReader isr = new InputStreamReader( System.in );
BufferedReader stdin = new BufferedReader( isr );
// ask user for input
i=0;
while(true){

// note I keep using numbers.length instead of 50 (the array length), this is so if I want to change the programs memory I only need to change 1 thing
System.out.println("Enter a number, up to "+numbers.length+" numbers, enter -1 to continue");
strInput = stdin.readLine();
intInput = Integer.parseInt(strInput); // convert to integer, note the throws IOException on the function
if(intInput < 0) break; // we assume negative numbers are user giving up
numbers[i] = intInput;
i++;
if(i>=numbers.length){

System.out.println("Memory full, sorting...");
break;

}

}
// sort our numbers
// numbers = bubbleSort(numbers); // call to sort array un-remark once you have done step 3
// display them in order (i hope)
System.out.println("Numbers in order, I hope....");
for(i=0; i<numbers.length;i++){

if(numbers[i]==-1) break; // reached end!
System.out.println(""+numbers[i]);

}

}

There are alot of steps to this, but atleast it demonstrates how to input an array of numbers!
You should be familiar to most of it by now... hopefully

• [varname].length - is used to get the size/length of an array how many items can be held in thsi case 50
• Interger.parseInt() - used to change a string into a number, The function needs "throws IOException incase input isn't numeric
• After int[] numbers = new int[50] - the array is filled with random values, so you must loop through and set initial values
• if(i>=numbers.length) - checks if their is still room for more values

STEP 3/4

The bubble sort function!

Code:
/* Slow standard numeric sorting
* Swops items until nothing else left to swop
* Advantages:
* -easier to program understand
* -doesn't need a seperate temporary loop
* Disadvantages:
* -slow!
*/
public static int[] bubbleSort(int[] numbers){

boolean made_change = true;
int tmp;
while(made_change){

// loop while something happened
made_change=false;
for(int check1=0; check1<numbers.length-1;check1++){

if(numbers[check1] > numbers[check1+1]){

// check if something needs swopping
/* Swop the two values numbers[check1] with numbers[check1+1]
* tmp = n[1] // save it or we errase on next line
* n[1] = n[3] // swop
* n[3] = tmp // restore
*/
tmp = numbers[check1]; // remember its value
numbers[check1] = numbers[check1+1]; // swop with other
numbers[check1+1] = tmp; // transfer value back
made_change=true; // tell loop we did something so go round again

}

}

}
return numbers;

}

• Bubble sort loops through the array swopping items with the next item if it is larger, it can make multiple swops per loop, if any changes were made the loop is run again
• Because a change could be made invalidating the previous checking, the loops must be done again and consequently the "made_change=true" is set and checked.
• When a change is found the items and swopped, it does not garantee these 2 numbers are in the correct order, further swopping is still possible.

STEP 4/4

Un-remark the call to bubbleSort in the main function and run!

---

The Task

Yes I am going to give you a small challenge after this example, sorry! The current code sorts the numbers in Descending order largest to smallest, change it so it sorts from smallest to largest!
Warning: You will want to change "if(numbers[i]==-1) break;" to not exit on the first -1 as your new bubble sort will put -1 first (the lowest possible number)

[click for answer]

I hope nobody kicks themselves here... I ofcourse did the easiest way :-)
Change 1.
On bubbleSort "if(numbers[check1] < numbers[check2]){" change to "if(numbers[check1] > numbers[check2]){
Change 2.
On main "if(numbers[i]==-1) break;" change to "if(numbers[i]==-1) continue; "
Remember continue quits the current code and goes back to the top of the loop
Run the new code!!!

Copyright (c) 2008, Martin Sykes.
Learning Center is a branch of Martrinex Systems, Martrinex.net
Do not copy any materials from this site without permission from the auther.