// Java
// Insertion Sort
// Sort.java
// Java - Insertion Sort v. Bubble Sort
// By Rami Jaloudi, Programmer
import java.util.*;
public class Sort {
public
static void main (String [] args){
int
n = 0;
boolean
run = true;
while(run){
Scanner
in = new Scanner(System.in);
System.out.println("Enter
the number of integers you would like to randomly populate: [RUN AGAIN & COMPARE]");
n
= in.nextInt();
int
A[] = new int[n];
Scanner
options = new Scanner(System.in);
System.out.println("Which
option would you like to select?");
System.out.println("(1)Insertion
Sort; "
+
"\n"
+
"(2)Bubble Sort; or "
+
"\n" +
"(3)Bubble
Sort 2nd Version");
int
optNumber;
optNumber
= options.nextInt();
if(optNumber
== 1){
populateArray(A);
System.out.println("Before
Sorting: ");
System.out.println("-----------------------------------------");
printArray(A);
//
sort the array
//insertionSort(A);
System.out.println("\nAfter
Sorting: ");
insertionSort(A);
System.out.println("-----------------------------------------");
printArray(A);
System.out.println("\n");
}
else {
}
if(optNumber
== 2){
populateArray(A);
System.out.println("Before
Sorting: ");
System.out.println("-----------------------------------------");
printArray(A);
//
sort the array
//insertionSort(A);
System.out.println("\nAfter
Sorting: ");
bubbleSort(A);
printArray(A);
System.out.println("-----------------------------------------");
System.out.println("\n");
}
else {
}
if(optNumber
== 3){
populateArray(A);
System.out.println("Before
Sorting: ");
System.out.println("-----------------------------------------");
printArray(A);
//
sort the array
//insertionSort(A);
System.out.println("\nAfter
Sorting: ");
bubbleSort2(A);
printArray(A);
System.out.println("-----------------------------------------");
System.out.println("\n");
}
else {
}
}
}
// Bubble sort:
public static void
bubbleSort(int[] list) {
int comps = 0;
int COMPCOUNT = 0;
for(int j = 0; j
< list.length - 1; j++) {
for(int i = 0; i
< list.length - 1; i++) {
// count the
number of comparisons
comps++;
// compare
neighboring elements
if(list[i]
> list[i+1]) {
// swap i
with i+1
int temp =
list[i];
list[i] =
list[i + 1];
list[i + 1]
= temp;
// count
number of swaps
COMPCOUNT++;
}
}
}
//System.out.println(list);
System.out.println("BUBBLE SORT 1: " + "Comparisons:
" + comps + " COMPCOUNT: " + COMPCOUNT);
}
//Variation of
Bubble Sort (improved)
//Stop sorting when
the array has become sorted & do not compare elements of the array with
elements that are in their correct sorted position
public static void
bubbleSort2(int[] list) {
int comps = 0;
int COMPCOUNT = 0;
boolean didSwap =
true;
// didSwap tracks
whether any elements of the array
// were swapped
during the last iteration of the loop.
// If no elements
were swapped, the the array is
// sorted, so we
can stop.
for(int j = 0; j
< list.length - 1 && didSwap; j++) {
didSwap = false;
// at this
point, j elements are already in their
// correct
sorted position, so we do not compare
// with the last
j elements in the list
for(int i = 0; i
< list.length - 1 - j; i++) {
// count the
number of comparisons
comps++;
// compare
neighboring elements
if(list[i]
> list[i+1]) {
didSwap =
true;
// swap i
with i+1
int temp =
list[i];
list[i] =
list[i + 1];
list[i + 1]
= temp;
// count
number of swaps
COMPCOUNT++;
}
}
}
//System.out.println(list);
System.out.println("BUBBLE SORT 2: " + "Comparisons:
" + comps + " COMPCOUNT: " + COMPCOUNT);
}
/**
* Insertion sort:
* - pick an element
and put it into its correct
* position in the
sorted part of the list
* - repeat
list.length times
*/
public static void insertionSort(int[]
list) {
int comps = 0,
COMPCOUNT = 0;
for(int i = 1; i
< list.length; i++) {
int j = i;
// compare i
with sorted elements and insert it
// sorted
elements: [0..i-1]
while (j
> 0 && list[j] < list[j - 1]) {
int temp =
list[j];
list[j] =
list[j - 1];
list[j - 1] =
temp;
COMPCOUNT++;
comps++; // loop condition true
j--;
}
comps++; //
checking loop condition when false
}
//System.out.println(list);
System.out.println("INSERTION SORT: " + "Comparisons:
" + comps + " COMPCOUNT: " + COMPCOUNT);
}
public static void
printArray(int[] B) {
System.out.println(Arrays.toString(B));
}
public static void
populateArray(int[] B) {
for (int i = 0;
i < B.length; i++) {
B[i] = (int)
(Math.random() * 100);
}
}
}
No comments:
Post a Comment