Posted by: greencookie May 1, 2008
Login in to Rate this Post:
0
?
![](/wysiwyg/editor/images/smiley/msn/thumbs_up.gif)
![10 more flags than likes deactivates post.](/wysiwyg/editor/images/smiley/msn/thumbs_down.gif)
Hey techguy,
Thanks I was past that point tho:) but thanks anyways.
I have another BIG URGENT problem if you could help me out:
Here is my code:
import javax.swing.*;
import java.util.*;
/** Implements the quicksort algorithm. */
public class testQuickSort {
public static <T extends Comparable<T>> void sort(T[] table) {
quickSort(table,0,table.length - 1);
}
private static <T extends Comparable<T>> void quickSort(T[] table,int first, int last) {
if (first < last) {
int pivIndex = partition(table,first,last);
quickSort(table,first,pivIndex - 1);
quickSort(table,pivIndex +1,last);
}
}
private static <T extends Comparable<T>> void insertSort(T[] table) {
for (int nextPos = 1; nextPos < table.length; nextPos++) {
insert(table,nextPos);
}
}
private static <T extends Comparable<T>> void insert(T[] table, int nextPos) {
T nextVal = table [nextPos];
while (nextPos > 0 && nextVal.compareTo(table[nextPos -1]) < 0 ); {
nextPos--;
}
table[nextPos] = nextVal;
}
private static <T extends Comparable<T>> void swap(T[] table,int i, int j) {
T temp = table[i];
table[i] = table[j];
table[j] = temp;
}
private static <T extends Comparable<T>> int partition(T[] table,int first,int last) {
bubbleSort3(table,first,last);
swap(table,first,(first+last)/2);
T pivot = table[first];
int down = last;
int up = first;
do {
while ((up<last)&&(pivot.compareTo(table[up]) >= 0)) {
up++;
}
while (pivot.compareTo(table[down]) <0) {
down--;
}
if (up<down) {
swap(table,up,down);
}
}
while (up<down);
swap(table,first,down);
return down;
}
private static <T extends Comparable<T>> void bubbleSort3(T[] table,int first,int last) {
int middle = (first + last) / 2;
if (table[middle].compareTo(table[first])<0) {
swap(table,first,middle);
}
if (table[last].compareTo(table[middle])<0) {
swap(table,middle,last);
}
if (table[middle].compareTo(table[first])<0) {
swap(table,first,middle);
}
}
public static void main(String[] args) {
int size = Integer.parseInt(JOptionPane.showInputDialog("Enter Array size:"));
Integer[] items = new Integer[size];
Integer[] copy = new Integer[size];
Random rInt = new Random();
for (int i = 0; i < items.length; i++) {
items[i] = rInt.nextInt();
copy[i] = items[i];
}
long startTime = System.currentTimeMillis();
QuickSort.sort(items);
System.out.println("QuickSort time is " + (System.currentTimeMillis() - startTime) +"ms");
JOptionPane.showMessageDialog(null, "QuickSort successful (true/false): " + verify(items));
}
private static boolean verify(Comparable[] test) {
boolean ok = true;
int i = 0;
while (ok && i < test.length -1) {
ok = test[i].compareTo(test[i+1]) <= 0;
i++;
}
return ok;
}
}
-----------------------------------------------------------------------------
NOW! here's the problem!
If you read my assignment (in my previous post) I have to do an insertion sort when the array size is less than a certain constant. I don't know how to implement this.
Basically, according to the project I have to write code amongst the one i have above, which will allow the program to efficiently run insertion sort when the partition is small enough and run quicksort when it is large!
How do I do this?
I appreciate any help.
Thanks in advance.
Thanks I was past that point tho:) but thanks anyways.
I have another BIG URGENT problem if you could help me out:
Here is my code:
import javax.swing.*;
import java.util.*;
/** Implements the quicksort algorithm. */
public class testQuickSort {
public static <T extends Comparable<T>> void sort(T[] table) {
quickSort(table,0,table.length - 1);
}
private static <T extends Comparable<T>> void quickSort(T[] table,int first, int last) {
if (first < last) {
int pivIndex = partition(table,first,last);
quickSort(table,first,pivIndex - 1);
quickSort(table,pivIndex +1,last);
}
}
private static <T extends Comparable<T>> void insertSort(T[] table) {
for (int nextPos = 1; nextPos < table.length; nextPos++) {
insert(table,nextPos);
}
}
private static <T extends Comparable<T>> void insert(T[] table, int nextPos) {
T nextVal = table [nextPos];
while (nextPos > 0 && nextVal.compareTo(table[nextPos -1]) < 0 ); {
nextPos--;
}
table[nextPos] = nextVal;
}
private static <T extends Comparable<T>> void swap(T[] table,int i, int j) {
T temp = table[i];
table[i] = table[j];
table[j] = temp;
}
private static <T extends Comparable<T>> int partition(T[] table,int first,int last) {
bubbleSort3(table,first,last);
swap(table,first,(first+last)/2);
T pivot = table[first];
int down = last;
int up = first;
do {
while ((up<last)&&(pivot.compareTo(table[up]) >= 0)) {
up++;
}
while (pivot.compareTo(table[down]) <0) {
down--;
}
if (up<down) {
swap(table,up,down);
}
}
while (up<down);
swap(table,first,down);
return down;
}
private static <T extends Comparable<T>> void bubbleSort3(T[] table,int first,int last) {
int middle = (first + last) / 2;
if (table[middle].compareTo(table[first])<0) {
swap(table,first,middle);
}
if (table[last].compareTo(table[middle])<0) {
swap(table,middle,last);
}
if (table[middle].compareTo(table[first])<0) {
swap(table,first,middle);
}
}
public static void main(String[] args) {
int size = Integer.parseInt(JOptionPane.showInputDialog("Enter Array size:"));
Integer[] items = new Integer[size];
Integer[] copy = new Integer[size];
Random rInt = new Random();
for (int i = 0; i < items.length; i++) {
items[i] = rInt.nextInt();
copy[i] = items[i];
}
long startTime = System.currentTimeMillis();
QuickSort.sort(items);
System.out.println("QuickSort time is " + (System.currentTimeMillis() - startTime) +"ms");
JOptionPane.showMessageDialog(null, "QuickSort successful (true/false): " + verify(items));
}
private static boolean verify(Comparable[] test) {
boolean ok = true;
int i = 0;
while (ok && i < test.length -1) {
ok = test[i].compareTo(test[i+1]) <= 0;
i++;
}
return ok;
}
}
-----------------------------------------------------------------------------
NOW! here's the problem!
If you read my assignment (in my previous post) I have to do an insertion sort when the array size is less than a certain constant. I don't know how to implement this.
Basically, according to the project I have to write code amongst the one i have above, which will allow the program to efficiently run insertion sort when the partition is small enough and run quicksort when it is large!
How do I do this?
I appreciate any help.
Thanks in advance.