Results 1 to 2 of 2
  1. #1
    Join Date
    Mar 2012
    Posts
    23
    Rep Power
    0

    Default Trouble with quick sort code

    Hey I seem to be having a problem trying to implement some Java quick sort code over an array of 10,000 random numbers. I have a text file containing the numbers which are placed into an array, which is then passed to the sorting algorithm to be sorted. My aim is to time how long it takes to time the sorting increasing the numbers sorted each time using the timing loop I have. Not sure if each time the sorting code is being ran on the sorted array. I just keep getting this graph for best case (best case meaning the textfile is already sorted) : http://i.imgur.com/jIXxj.jpg rather than a O(n log n) graph.


    Java Code:
    import java.io.*;
    import java.util.*;
    public class Quicksort {
    
    public static void main(String args[]) throws IOException {
    //Import the random integer text file into an integer array
    File fil = new File("randomASC.txt");
    FileReader inputFil = new FileReader(fil);
    int [] myarray = new int [10000];
    Scanner in = new Scanner(inputFil);
    
    for(int q = 0; q < myarray.length; q++)
    {
      myarray[q] = in.nextInt();
    }
    in.close();
    
    
    
    for (int n = 100; n < 10000; n += 100) { 
    long total = 0;
    for (int r = 0; r < 10; ++r) {  
      long start = System.nanoTime ();    
          quickSort(myarray,0,n-1);
          total += System.nanoTime() - start;
        }
      System.out.println (n + "," + (double)total / 10.0);
    } 
    }
    
     public static void quickSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q=partition(a,p,r);
            quickSort(a,p,q);
            quickSort(a,q+1,r);
        }
    }
    
    private static int partition(int[] a, int p, int r) {
    
        int x = a[p];
        int i = p-1 ;
        int j = r+1 ;
    
        while (true) {
            i++;
            while ( i< r && a[i] < x)
                i++;
            j--;
            while (j>p && a[j] > x)
                j--;
    
            if (i < j)
                swap(a, i, j);
            else
                return j;
        }
    }
    
    private static void swap(int[] a, int i, int j) {
        // TODO Auto-generated method stub
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    }

  2. #2
    Join Date
    Mar 2012
    Posts
    23
    Rep Power
    0

    Default Re: Trouble with quick sort code

    latest news I'm getting this now! http://i.imgur.com/rMr0Y.jpg but that's now for average/best AND worst.... _

Similar Threads

  1. Quick sort problem
    By fishy8158 in forum New To Java
    Replies: 0
    Last Post: 02-18-2012, 05:21 AM
  2. Need help with quick sort method
    By Get_tanked in forum New To Java
    Replies: 1
    Last Post: 03-14-2011, 10:44 PM
  3. Quick Sort explanation.
    By hawaiifiver in forum New To Java
    Replies: 4
    Last Post: 03-10-2009, 03:28 AM
  4. Quick sort with median-of-three partitioning
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 08:40 PM
  5. Simple version of quick sort
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 08:40 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •