15jen
asked on
How do I get QuickSort to work this java program?
Please refer to my code. I have got all sorting algorithms to work. I cannot figure out how to implement the quicksort though? Look over where I am trying to implement the quicksort and please let me know what I am doing wrong???
Jim Cakalic
Please post your code.
ASKER
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.*;
import java.io.*;
public class Homework2copy {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
int selection = 0;
System.out.println("");
System.out.println("Input the amount of Numbers you want to sort:");
int elements = scan.nextInt();
scan.nextLine();
Number numgen = new Number();
numgen.generate(elements);
numgen.show_numbers(elemen
numgen.put_numbers(element
System.out.println("Select
System.out.println("1) Selection Sort");
System.out.println("2) Bubble Sort");
System.out.println("3) Insertion Sort");
System.out.println("4) Shell Sort");
System.out.println("5) Rec Quick Sort");
int swaps = 0;
switch (scan.nextInt()) {
case 1:
selection = 1;
numgen.selectionsort(eleme
numgen.show_numbers(elemen
break;
case 2:
selection = 2;
numgen.bubblesort(elements
numgen.show_numbers(elemen
break;
case 3:
selection = 3;
numgen.insertionsort(eleme
numgen.show_numbers(elemen
break;
case 4:
selection = 4;
numgen.shellsort(elements)
numgen.show_numbers(elemen
break;
case 5:
selection = 5;
numgen.recquicksort(elemen
numgen.show_numbers(elemen
break;
default:
System.out.println("Error"
break;
}
numgen.put_numbers(element
System.out.println("Amount
}
static class Number {
int[] randomnumbers;
public void generate(int elements) {
int min = 1;
int max = 2000;
randomnumbers = new int[elements];
for (int i = 0; i < elements; i++) {
randomnumbers[i] = (int) (Math.random() * (max - min + 1))
+ min;
}
}
public void put_numbers(int elements) throws IOException {
try {
PrintWriter out = new PrintWriter(new FileWriter("random.txt",
true));
for (int j = 0; j < randomnumbers.length; j++) {
out.println(randomnumbers[
}
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public void show_numbers(int elements) {
for (int j = 0; j < elements; j++) {
System.out.println(randomn
}
}
public int selectionsort(int elements) throws IOException {
int outside, inside, min, swaps = 0;
for (outside = 0; outside < elements - 1; outside++) {
min = outside;
for (inside = outside + 1; inside < elements; inside++)
if (randomnumbers[inside] < randomnumbers[min])
min = inside;
swap(outside, min);
swaps++;
}
System.out.println("Number
return swaps;
}
public int bubblesort(int elements) {
int outside, inside, swaps = 0;
for (outside = elements - 1; outside > 1; outside--)
for (inside = 0; inside < outside; inside++)
if (randomnumbers[inside] > randomnumbers[inside + 1]) {
swap(inside, inside + 1);
swaps++;
}
System.out.println("Number
return swaps;
}
public int insertionsort(int elements) {
int inside, outside, swaps = 0;
for (outside = 1; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > 0) && (randomnumbers[inside - 1] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - 1];
--inside;
swaps++;
}
randomnumbers[inside] = temp;
}
System.out.println("Number
return swaps;
}
public int shellsort(int elements) {
int inside, outside, h = 1, swaps = 0;
while (h <= elements / 3)
h = h * 3 + 1;
while (h > 0)
{
for (outside = h; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > h - 1) && (randomnumbers[inside - h] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - h];
inside -= h;
swap(outside, inside);
swaps++;
}
randomnumbers[inside] = temp;
}
h = (h - 1) / 3;
}
System.out.println("Number
return swaps;
}
public void swap(int one, int two) {
int temp = randomnumbers[one];
randomnumbers[one] = randomnumbers[two];
randomnumbers[two] = temp;
}
}
public void recQuickSort(int left, int right) {
if(right - left <= 0)
return;
else
{
long pivot = randomnumbers[right];
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while(true)
{
while(randomnumbers[++left
while((rightPtr > 0) && (randomnumbers[--rightPtr]
if(leftPtr > rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right);
return leftPtr;
}
public void swap(int dex1, int dex2) {
long temp = randomnumbers[dex1];
randomnumbers[dex1] = randomnumbers[dex2];
randomnumbers[dex2] = temp;
}
}
}
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.*;
import java.io.*;
public class Homework2copy {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
int selection = 0;
System.out.println("");
System.out.println("Input the amount of Numbers you want to sort:");
int elements = scan.nextInt();
scan.nextLine();
Number numgen = new Number();
numgen.generate(elements);
numgen.show_numbers(elemen
numgen.put_numbers(element
System.out.println("Select
System.out.println("1) Selection Sort");
System.out.println("2) Bubble Sort");
System.out.println("3) Insertion Sort");
System.out.println("4) Shell Sort");
System.out.println("5) Rec Quick Sort");
int swaps = 0;
switch (scan.nextInt()) {
case 1:
selection = 1;
numgen.selectionsort(eleme
numgen.show_numbers(elemen
break;
case 2:
selection = 2;
numgen.bubblesort(elements
numgen.show_numbers(elemen
break;
case 3:
selection = 3;
numgen.insertionsort(eleme
numgen.show_numbers(elemen
break;
case 4:
selection = 4;
numgen.shellsort(elements)
numgen.show_numbers(elemen
break;
case 5:
selection = 5;
numgen.recquicksort(elemen
numgen.show_numbers(elemen
break;
default:
System.out.println("Error"
break;
}
numgen.put_numbers(element
System.out.println("Amount
}
static class Number {
int[] randomnumbers;
public void generate(int elements) {
int min = 1;
int max = 2000;
randomnumbers = new int[elements];
for (int i = 0; i < elements; i++) {
randomnumbers[i] = (int) (Math.random() * (max - min + 1))
+ min;
}
}
public void put_numbers(int elements) throws IOException {
try {
PrintWriter out = new PrintWriter(new FileWriter("random.txt",
true));
for (int j = 0; j < randomnumbers.length; j++) {
out.println(randomnumbers[
}
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public void show_numbers(int elements) {
for (int j = 0; j < elements; j++) {
System.out.println(randomn
}
}
public int selectionsort(int elements) throws IOException {
int outside, inside, min, swaps = 0;
for (outside = 0; outside < elements - 1; outside++) {
min = outside;
for (inside = outside + 1; inside < elements; inside++)
if (randomnumbers[inside] < randomnumbers[min])
min = inside;
swap(outside, min);
swaps++;
}
System.out.println("Number
return swaps;
}
public int bubblesort(int elements) {
int outside, inside, swaps = 0;
for (outside = elements - 1; outside > 1; outside--)
for (inside = 0; inside < outside; inside++)
if (randomnumbers[inside] > randomnumbers[inside + 1]) {
swap(inside, inside + 1);
swaps++;
}
System.out.println("Number
return swaps;
}
public int insertionsort(int elements) {
int inside, outside, swaps = 0;
for (outside = 1; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > 0) && (randomnumbers[inside - 1] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - 1];
--inside;
swaps++;
}
randomnumbers[inside] = temp;
}
System.out.println("Number
return swaps;
}
public int shellsort(int elements) {
int inside, outside, h = 1, swaps = 0;
while (h <= elements / 3)
h = h * 3 + 1;
while (h > 0)
{
for (outside = h; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > h - 1) && (randomnumbers[inside - h] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - h];
inside -= h;
swap(outside, inside);
swaps++;
}
randomnumbers[inside] = temp;
}
h = (h - 1) / 3;
}
System.out.println("Number
return swaps;
}
public void swap(int one, int two) {
int temp = randomnumbers[one];
randomnumbers[one] = randomnumbers[two];
randomnumbers[two] = temp;
}
}
public void recQuickSort(int left, int right) {
if(right - left <= 0)
return;
else
{
long pivot = randomnumbers[right];
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while(true)
{
while(randomnumbers[++left
while((rightPtr > 0) && (randomnumbers[--rightPtr]
if(leftPtr > rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right);
return leftPtr;
}
public void swap(int dex1, int dex2) {
long temp = randomnumbers[dex1];
randomnumbers[dex1] = randomnumbers[dex2];
randomnumbers[dex2] = temp;
}
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
I keep getting compiler errors with my method. I am oh so very close, please take a look at the code and let me know what I am doing wrong. I have spent over 3 hours on this....
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.*;
import java.io.*;
public class QuickSort {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
int selection = 0;
System.out.println("");
System.out.println("Input the amount of Numbers you want to sort:");
int elements = scan.nextInt();
scan.nextLine();
Number numgen = new Number();
numgen.generate(elements);
numgen.show_numbers(elements);
numgen.put_numbers(elements);
System.out.println("Select the Sort Type?");
System.out.println("1) Selection Sort");
System.out.println("2) Bubble Sort");
System.out.println("3) Insertion Sort");
System.out.println("4) Shell Sort");
System.out.println("5) Rec Quick Sort");
int swaps = 0;
switch (scan.nextInt()) {
case 1:
selection = 1;
numgen.selectionsort(elements);
numgen.show_numbers(elements);
break;
case 2:
selection = 2;
numgen.bubblesort(elements);
numgen.show_numbers(elements);
break;
case 3:
selection = 3;
numgen.insertionsort(elements);
numgen.show_numbers(elements);
break;
case 4:
selection = 4;
numgen.shellsort(elements);
numgen.show_numbers(elements);
break;
case 5:
selection = 5;
numgen.recquicksort(elements);
numgen.show_numbers(elements);
break;
default:
System.out.println("Error");
break;
}
numgen.put_numbers(elements);
System.out.println("Amount of Swaps is Displayed below the Selected Sort");
}
static class Number {
int[] randomnumbers;
public void generate(int elements) {
int min = 1;
int max = 2000;
randomnumbers = new int[elements];
for (int i = 0; i < elements; i++) {
randomnumbers[i] = (int) (Math.random() * (max - min + 1))
+ min;
}
}
public void put_numbers(int elements) throws IOException {
try {
PrintWriter out = new PrintWriter(new FileWriter("random.txt",
true));
for (int j = 0; j < randomnumbers.length; j++) {
out.println(randomnumbers[j]);
}
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public void show_numbers(int elements) {
for (int j = 0; j < elements; j++) {
System.out.println(randomnumbers[j]);
}
}
public int selectionsort(int elements) throws IOException {
int outside, inside, min, swaps = 0;
for (outside = 0; outside < elements - 1; outside++) {
min = outside;
for (inside = outside + 1; inside < elements; inside++)
if (randomnumbers[inside] < randomnumbers[min])
min = inside;
swap(outside, min);
swaps++;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int bubblesort(int elements) {
int outside, inside, swaps = 0;
for (outside = elements - 1; outside > 1; outside--)
for (inside = 0; inside < outside; inside++)
if (randomnumbers[inside] > randomnumbers[inside + 1]) {
swap(inside, inside + 1);
swaps++;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int insertionsort(int elements) {
int inside, outside, swaps = 0;
for (outside = 1; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > 0) && (randomnumbers[inside - 1] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - 1];
--inside;
swaps++;
}
randomnumbers[inside] = temp;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int shellsort(int elements) {
int inside, outside, h = 1, swaps = 0;
while (h <= elements / 3)
h = h * 3 + 1;
while (h > 0)
{
for (outside = h; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > h - 1) && (randomnumbers[inside - h] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - h];
inside -= h;
swap(outside, inside);
swaps++;
}
randomnumbers[inside] = temp;
}
h = (h - 1) / 3;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int quicksort(int elements) {
recquicksort(0, elements - 1);
}
public int recquicksort(int left, int right) {
if(right - left <= 0)
return;
else
{
long pivot = randomnumbers[right];
int partition = partitionIt(left, right, pivot);
recquicksort(left, partition - 1);
recquicksort(partition + 1, right);
}
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while(true)
{
while(randomnumbers[++leftPtr] < pivot);
while((rightPtr > 0) && (randomnumbers[--rightPtr] > pivot));
if(leftPtr > rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
}
public void swap(int one, int two) {
int temp = randomnumbers[one];
randomnumbers[one] = randomnumbers[two];
randomnumbers[two] = temp;
}
}
}
you are missing some returns, and also have a return that does not return a value (when one is expected)
> numgen.recquicksort(elemen
and that method expects two input, left and right
and that method expects two input, left and right
ASKER
for > numgen.recquicksort(elemen
how would I write the method so that the inputs left and right would compile?
how would I write the method so that the inputs left and right would compile?
looks like u are callinmg the wrong method, try:
numgen.quicksort(elements)
numgen.quicksort(elements)
ASKER
I finally got the methods corrected, now I cannot figure out where the missing return statement is?????
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.*;
import java.io.*;
public class QuickSort {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
int selection = 0;
System.out.println("");
System.out.println("Input the amount of Numbers you want to sort:");
int elements = scan.nextInt();
scan.nextLine();
Number numgen = new Number();
numgen.generate(elements);
numgen.show_numbers(elements);
numgen.put_numbers(elements);
System.out.println("Select the Sort Type?");
System.out.println("1) Selection Sort");
System.out.println("2) Bubble Sort");
System.out.println("3) Insertion Sort");
System.out.println("4) Shell Sort");
System.out.println("5) Rec Quick Sort");
int swaps = 0;
switch (scan.nextInt()) {
case 1:
selection = 1;
numgen.selectionsort(elements);
numgen.show_numbers(elements);
break;
case 2:
selection = 2;
numgen.bubblesort(elements);
numgen.show_numbers(elements);
break;
case 3:
selection = 3;
numgen.insertionsort(elements);
numgen.show_numbers(elements);
break;
case 4:
selection = 4;
numgen.shellsort(elements);
numgen.show_numbers(elements);
break;
case 5:
selection = 5;
numgen.quicksort(elements);
numgen.show_numbers(elements);
break;
default:
System.out.println("Error");
break;
}
numgen.put_numbers(elements);
System.out.println("Amount of Swaps is Displayed below the Selected Sort");
}
static class Number {
int[] randomnumbers;
public void generate(int elements) {
int min = 1;
int max = 2000;
randomnumbers = new int[elements];
for (int i = 0; i < elements; i++) {
randomnumbers[i] = (int) (Math.random() * (max - min + 1))
+ min;
}
}
public void put_numbers(int elements) throws IOException {
try {
PrintWriter out = new PrintWriter(new FileWriter("random.txt",
true));
for (int j = 0; j < randomnumbers.length; j++) {
out.println(randomnumbers[j]);
}
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public void show_numbers(int elements) {
for (int j = 0; j < elements; j++) {
System.out.println(randomnumbers[j]);
}
}
public int selectionsort(int elements) throws IOException {
int outside, inside, min, swaps = 0;
for (outside = 0; outside < elements - 1; outside++) {
min = outside;
for (inside = outside + 1; inside < elements; inside++)
if (randomnumbers[inside] < randomnumbers[min])
min = inside;
swap(outside, min);
swaps++;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int bubblesort(int elements) {
int outside, inside, swaps = 0;
for (outside = elements - 1; outside > 1; outside--)
for (inside = 0; inside < outside; inside++)
if (randomnumbers[inside] > randomnumbers[inside + 1]) {
swap(inside, inside + 1);
swaps++;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int insertionsort(int elements) {
int inside, outside, swaps = 0;
for (outside = 1; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > 0) && (randomnumbers[inside - 1] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - 1];
--inside;
swaps++;
}
randomnumbers[inside] = temp;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int shellsort(int elements) {
int inside, outside, h = 1, swaps = 0;
while (h <= elements / 3)
h = h * 3 + 1;
while (h > 0)
{
for (outside = h; outside < elements; outside++) {
int temp = randomnumbers[outside];
inside = outside;
while ((inside > h - 1) && (randomnumbers[inside - h] >= temp)) {
randomnumbers[inside] = randomnumbers[inside - h];
inside -= h;
swap(outside, inside);
swaps++;
}
randomnumbers[inside] = temp;
}
h = (h - 1) / 3;
}
System.out.println("Number of swaps = " + swaps);
return swaps;
}
public int quicksort(int elements) {
recquicksort(0, elements - 1);
}
public void recquicksort(int left, int right) {
if(right - left <= 0)
return;
else
{
long pivot = randomnumbers[right];
int partition = partitionIt(left, right, pivot);
recquicksort(left, partition - 1);
recquicksort(partition + 1, right);
}
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while(true)
{
while(randomnumbers[++leftPtr] < pivot);
while((rightPtr > 0) && (randomnumbers[--rightPtr] > pivot));
if(leftPtr > rightPtr)
break;
else
swap(leftPtr, rightPtr);
} // end while(true)
swap(leftPtr, right);
return leftPtr;
}
public void swap(int one, int two) {
int temp = randomnumbers[one];
randomnumbers[one] = randomnumbers[two];
randomnumbers[two] = temp;
}
}
}
public int quicksort(int elements) {
recquicksort(0, elements - 1);
}
looks like it should not be declared to return an int
recquicksort(0, elements - 1);
}
looks like it should not be declared to return an int
It looks like if you fix the return on that method then the rest is correct. Your imports are a little excessive although that really doesn't make a difference in correctness. Just not clean. All you really need to import is:
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
ASKER
I get that I have to fix the return and that the imports are excessive. I just have left them there from previous work. But I do not know how to fix the return statement. If I change the return from int to void then the program does not compile correctly. Any suggestions on the return statements>>> suggestions meaning what do I have to do to fix it???
Hmm. I copied your code and tried to compile it. The only error was:
public int quicksort(int elements)
When I change the return type of the method to:
public void quicksort(int elements)
Then it compiles and runs as it should.
public int quicksort(int elements)
When I change the return type of the method to:
public void quicksort(int elements)
Then it compiles and runs as it should.
I don't understand the reason for the delete request here. The question seems to be understood and we appear to have been answering it correctly.