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

Insertion sort

Another popular method of sorting is the inersion sort, this is infact simpler then bubble sort however in most cases it is also slower then bubble sort as it can only make 1 change per loop.

Because we are doing the same as the previous tutorial... sorting numbers you can use the same main code:

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
numbers = insSort(numbers;
// 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]);

}

}

Notice:
Remembers to change:

Code:
numbers = bubbleSort(numbers); // call to sort array un-remark once you have done step 3
/* with */
numbers = insSort(numbers;

The new insSort function Ok so in, insSort we loop through the array checking each value of the array against all the over values, this requires two loops, one to collect the item to check and one to check that item against all other items in that array, the second loop must ofcourse be inside that loop.

Code:
public static int[] insSort(int[] numbers){

int tmp;
// loop through array collecting items to check
for(int check=0; check<numbers.length-1; check++){

// loop through array again check each item with check
for(int check_against=check+1; check_against<numbers.length; check_against++){

if(numbers[check] < numbers[check_against]){

// do the swop
tmp = numbers[check];
numbers[check] = numbers[check_against];
numbers[check_against] = tmp;

}

}

}
return numbers;

}

---

Excersize 1

Like the previous tutorial change insSort so it sorts in accending order.

[click for answer]

1. Swop: "if(numbers[check] < numbers[check_against]){" with "if(numbers[check] > numbers[check_against]){"
2. Swop: "if(numbers[i]==-1) break;" with "if(numbers[i]==-1) continue;"

Excersize 2

I'm feeling lazy and don't like entering 50 numbers manually everytime.
Change the program so it:
1. asks how many random numbers ('x') you want between 0 and 50
2. Sets 'x' amount of numbers to random numbers using a loop and:
Using: int int_var_name = (int)(Math.random()*2147483647); // this sets int_var_name to a random number between 0 and 2147483647

Notice:
Math.random() actually gives a number between 0 and 1, multiplying it by another number specifies the range, I chose 2147483647 because it is the largest possible number for an integer!

[click for answer]

Redundant code:

Code:
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;

}

}

Replaced with:

Code:
// ask user for input
System.out.println("How many random numbers do you want? 0-50");
strInput = stdin.readLine();
intInput = Integer.parseInt(strInput);
if(intInput > numbers.length) intInput=numbers.length; // stop program from crashing if input wrong

// fill in the array randomly
for(i=0; i<intInput; i++){

numbers[i] = (int)(Math.random()*2147483647); //2147483647 is max size of int

}

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.