Sorting Algorithms


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 4 of 4

Thread: Sorting Algorithms

  1. #1
    Join Date
    Nov 2005
    Posts
    1

    Lightbulb Sorting Algorithms

    Hi, im trying to compare the runtime of 2 algorithms (an insertion sort algorithm and a quicksort algorithm), i've done the code for them correct i think but im having some problems..

    The code for the Insertion Sort:

    Code:
    public class InsertionSortAlgorithm
    {
    
    	public static void insertionSort(int[] arrayData, int numberItems)
    	{
    		for(int i=0;i<numberItems - 1;i++)
    		{
    			int j = i - 1;
    			int item = arrayData[i];
    
    			while (j >= 0 && arrayData[j] > item)
    			{
    				arrayData[j + 1] = arrayData[j];
    				j = j - 1;
    			}
    				arrayData[j + 1] = item;
    
    		}
    	}
    }
    Code for Quick Sort:

    Code:
    public class QuickSortAlgorithm
    {
    
    	public static int[] quickSort(int[] list, int lower, int upper)
    	{
    		if (upper > lower)
    		{
    			int j = partition(list,lower,upper);
    			quickSort(list,lower,j-1);
    			quickSort(list,j+1,upper);
    
    	}
    	return list;
    }
    	public static int partition(int[] list, int lower, int upper)
    	{
    		int i = lower;
    		int j = upper + 1;
    		int v = list[lower];
    		int t, t2;
    
    		do{
    			do{
    			i = i + 1;
    		}
    				while (list[i] < v);
    
    			do {
    			j = j - 1;
    			}
    				while (list[j] > v);
    
    			if (i < j){
    
    			t = list[i];
    			t2 = list[j];
    			list[j] = t;
    			list[i] = t2;
    }
    }
    
    		while (i<j);
    
    			t = list[lower];
    			t2 = list[j];
    			list[i] = t;
    			list[lower] = t2;
    
    		return j;
    }
    }
    Code to run each algorithm:

    Code:
    public class ArrayData
    {
    
    	private int[] data;
    	private int numberItems = 10000;
    
    	public static void main(String args[])
    	{
    		ArrayData myData = new ArrayData();
    
    	}
    
    	public ArrayData()
    	{
    
    		data = new int[numberItems];
    
    		long start1 = System.currentTimeMillis();
    
    		for (int i=0;i<numberItems;i++)
    		{
    			data[i] = (int) (Math.random() * 1000);
    
    		}
    
    		for( int j =0; j < 10; j++){
    
    	   	long start = System.currentTimeMillis();
    
    		int[] a =  QuickSortAlgorithm.quickSort(data, 0, numberItems - 1);
    
    		long end = System.currentTimeMillis();
    
    		long time = end - start;
    
    		System.out.println(time + "ms");
    
    }
    
    		long start2 = System.currentTimeMillis();
    		System.out.println("Total time: " + (start2 - start1) + " ms");
    
    	}
    }
    	/* public void output()
    	{
    		for (int i=0;i<numberItems;i++)
    		{
    
    		System.out.println(data[i]);
    
    		}
    
    
    	} */
    
    	/*public void algorithmTimer()
    	{
    		long start = System.currentTimeMillis();
    
    		QuickSortAlgorithm.quickSort(data, 0, numberItems - 1);
    
    		long end = System.currentTimeMillis();
    
    		long time = end - start;
    
    		System.out.println(time + "ms");
    
    	}
    }
    
    /*	public void algorithmTimer()
    	{
    		long start = System.currentTimeMillis();
    
    		InsertionSortAlgorithm.insertionSort(data, numberItems);
    
    		long end = System.currentTimeMillis();
    
    		long time = end - start;
    
    		System.out.println(time + "ms");
    
    	}
    } */
    Basically those 2 algorithms are in their own seperate classes and using the 3rd class ArrayData im calling them and timing the results of arrays of random integers. The insertion sort algorithm works fine i think.. but the quick sort im having problems with.. something about stack overflows.. it all compiles fine so im not sure whats wrong.. if anybody could help me out here would be appreciated.

    Thanks,

    Sandy

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    Walk your way through the execution of your code, watching how i and j walk toward each other. You should see that the place you want to put your "partition value" is actually one index past where j ended up - j and i have walked PAST each other and j needs to backtrack one to be at the index where the partition value should be inserted.

    So, swap your list[lower] with the value at list[j+1]; and then return j+1. You should stop having your stack overflows then.

    [In earlier versions of this post I got lost with the formatting and I'm just not used to the do - while structure. I didn't clear up my confusion until I reconstructed the code with the formatting I'm used to ...]
    Last edited by nspils; 11-14-2005 at 10:54 AM.

  3. #3
    Join Date
    Sep 2005
    Location
    istanbul / Turkey
    Posts
    133
    i tried to correct it , do-while loops were wrong.
    Code:
    class QuickSortAlgorithm {
      public static int[] quickSort(int[] list, int lower, int upper) {
        if (upper > lower) {
          int j = partition(list, lower, upper);
          quickSort(list, lower, j);
          quickSort(list, j == lower ? (j + 1) : j , upper);
        }
        return list;
      }
    
      public static int partition(int[] list, int lower, int upper) {
        int i = lower;
        int j = upper;
        int v = list[lower];
        int t, t2;
        do {
          while ( (i < j) && (list[i] < v)) {
            i = i + 1;
          }
    
          while ( (j > i) && (list[j] >= v)) {
            j = j - 1;
          }
    
          if (i < j) {
            t = list[i];
            t2 = list[j];
            list[j] = t;
            list[i] = t2;
          }
        }
        while (i < j);
        return j;
      }
    }

  4. #4
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You left out swapping your original (for each call to the sort procedure) list[lower] ( which you've stored as v) with the value at list[j+1]; and then return j+1, rather than j.

Similar Threads

  1. Sorting algorithms
    By srekcus in forum Java
    Replies: 8
    Last Post: 10-31-2005, 06:34 AM
  2. Replies: 3
    Last Post: 07-29-2005, 11:00 AM
  3. Replies: 1
    Last Post: 04-05-2002, 11:18 AM
  4. Algorithms
    By Jeremy in forum .NET
    Replies: 2
    Last Post: 04-05-2001, 08:15 PM
  5. Sorting for a JTable
    By Ramkumar in forum Java
    Replies: 1
    Last Post: 01-11-2001, 06:32 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center