Hello friends,

I would like your help and assistance if possible on my final Java program. Unfortunately I am ashamed to say that I haven't yet learnt the basics of java entirely so forgive me if any of my questions sound 'noobish' or wierd.

Here is the assignment:

# Implement a quicksort that selects the median of the first, middle and last as the pivot.
#Implement the sort so that it uses an insertion sort whenever the number of items to be sorted is less than some constant (i.e 20). you can choose to either build the insertion sort directly into the quicksort or make it a separate method.
#use java's random number generator to fill an array with random integers. Be certain to use the seed operation to always generate exactly the same set of random numbers for repeatability of  your results.

Now so far here is what I have for my QuickSort.java program :

/** Implements the quicksort algorithm. */

public class  QuickSort {
    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>> int partition(T[] table,int first,int last) {
        bubbleSort3(table,first,last);
        swap(table,first,(first+last)/2);
            T pivot = table[first];
        int up = first;
        int down = last;
        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);
            }
        }
   
}

compiling this results in a couple of errors. Mainly its not recognizing the swap method. Do I have to import something?

Secondly, I dont know how to insert the random number seeder into this program. If any of you have ideas, they are more than welcome!!

Thanks in advance!!!

!bump

Thnx suike for your feedback! Yeah I had to code swap and put a random seed generator in main.

Here is my assignment if you wanna take a look.

hey GC ,

did u solve it, if not here is the code, added swap and main and remove that generic thing, now works only with int.

Happy programming...

** Implements the quicksort algorithm. */

public class  QuickSort {
    public static void sort(int[] table) {      
        quickSort(table,0,table.length - 1);
    }
    private static  void quickSort(int[] 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 int partition(int[] table,int first,int last) {
        bubbleSort3(table,first,last);
        swap(table,first,(first+last)/2);
            int pivot = table[first];
        int up = first;
        int down = last;
        do {
            while ((up<last)&&(((Integer)pivot).compareTo(table[up]) >= 0)) {
                up++;
            }
            while (((Integer)pivot).compareTo(table[down]) <0) {
                down--;
            }
            if (up<down) {
                swap(table,up,down);
            }
        }
        while (up<down);
        swap(table,first,down);
        return down;
    }
   
        private static  void bubbleSort3(int[] table,int first,int last) {
            int middle = (first + last) / 2;
           
            if (((Integer)table[middle]).compareTo(table[first])<0) {
                swap(table,first,middle);
            }
            if (((Integer)table[last]).compareTo(table[middle])<0) {
                swap(table,middle,last);
            }
            if (((Integer)table[middle]).compareTo(table[first])<0) {
                swap(table,first,middle);
            }
        }
   
       private static  void swap(int[] table, int a, int b)
{
      
     int temp=table[a];
      table[a]=table[b];
     table[b]=temp;
}

public static void main(String args[])
 {
int [] a={6,4,2,1,4,3,5,7};
 sort(a);

   for(int i=0;i<a.length;i++)
       System.out.println(a[i]);

}

}

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.

hey green code, for some reason i couldnot run the code u have posted above, but if u want to use the logic for constant , then this is how u do it, if u can run ur code, the following will also work, u just need to write code for insertion sort though

Happy programming.

import javax.swing.*;
import java.util.*;

//declare constant
interface Constants
{
public static final  int insertionTest= 10;
}

 

/** 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:"));

   if(size<=Constants.insertionTest)

{
      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));
    }

else

{

 //call insertion sort here

}
}
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;
}
}

 

Techie Bro,

Thanks a Tonne for your help!

Here is my completed program. Works like a charm.

PEace.