How to use quicksort method in class? (so I can call it in the main method)

Question

Thendi 0 Newbie Poster

15 Years Ago

Hi I am trying to put quicksort in my class like other methods and call it using the main method, I did it for Selection, Insertion, Bubble Sort and I need one more which is quicksort. I already made the calling code for quicksort but I don't know how to use quicksort in class.

I have the main method first then I have the classes

Main

/**ICS
 * @(#)sorting_problem_setting.java
 *
 * sorting_problem_setting application
 * author
 * James Samuel
 * 29/March/2011
 */


public class sorting_problem_setting {

    public static void main(String[] args) {
    	SortClass sl = new SortClass();

		// bubble sort
		int numbers[] = new int[10000];
		sl.makeData(numbers);
		sl.bubbleSort(numbers);
		sl.displayTen(numbers);

		// insertion sort
		int numbers2[] = new int[10000];
		sl.makeData(numbers2);
		sl.insertionSort(numbers2);
		sl.displayTen(numbers2);

		// selection sort
		int numbers3 [] = new int[10000];
		sl.makeData(numbers3);
		sl.selectionSort(numbers3);
		sl.displayTen(numbers3);

 		// quick sort
		int numbers3 [] = new int[10000];
		sl.makeData(numbers3);
		sl.selectionSort(numbers3);
		sl.displayTen(numbers3);
}
}

Class

//** 29/March/2011
//*
//** Author
//***** James Samuel
//** ICS


import java.util.*;
class SortClass {


		static public void makeData(int array[])
		{
			Random a = new Random();

			for (int ctr = 0; ctr < array.length; ctr++)
			{
				array[ctr] = Math.abs(a.nextInt()) % 999 + 1;
			}
		}

		static public int linearSearch (int numList [], int searchItem)
		{
			for (int ctr2=0; ctr2>numList.length;ctr2++)
			{
				if (searchItem==numList[ctr2])
				{
					return ctr2;
				}

			}
			return -1;
		}

		static public void displayTen (int array[])
		{
			for (int ctr = 0; ctr <100; ctr++)
			{
				System.out.print(array[ctr] + " ");
			}
			System.out.println("");
		}
//#########################################################################################
//Bubble sort
	static public void bubbleSort( int array2[] )
   {

      for ( int pass = 1; pass < array2.length; pass++ )
      {

         for ( int element = 0; element < array2.length - 1; element++ )
         {

            if ( array2[ element ] > array2[ element + 1 ] )
	     {
               swap( array2, element, element + 1 );
	     }

         }
      }

   }

   static public void swap( int array3[], int first, int second )
   {
      int hold;

      hold = array3[ first ];
      array3[ first ] = array3[ second ];
      array3[ second ] = hold;
   }
//#########################################################################################
//insertionSort
					public void insertionSort(int numList[])
					{
						int hold, ptr;
						for (int ctr = 1; ctr < numList.length; ctr++)
					{
						hold = numList[ctr];
						ptr = 0;
						while (hold > numList[ptr])
						{
							ptr++;
						}
						for (int count = ctr; count > ptr; count--)
						{
							numList[count] = numList[count - 1];
						}
						numList[ptr] = hold;
					}

					}

//#########################################################################################
	// Selection sort
			public void selectionSort(int array[]){


			for ( int ctr2 = 0; ctr2 < array.length; ctr2++)
			{
				for ( int ctr = ctr2; ctr < array.length; ctr++)
					{
						if (array[ctr2] > array [ctr])	
							 		{
										swap( array, ctr2, ctr );

							 		}

					}

			}



		 }	


}
//#########################################################################################


	//Quick Sort

Now I need a quicksort code in class so I can call it using the main method.
Can somebody help me or show me how to use quicksort.

Thanks in Advance

java object-oriented-programming

Edited 15 Years Ago by Thendi because: n/a

2 Contributors
2 Replies
671 Views
2 Days Discussion Span
Latest Post 15 Years Ago Latest Post by Thendi

Dani AI

Generated 10 Months Ago

A compact, reliable way to add quicksort to SortClass is to provide a public entry method that delegates to a private helper taking low/high indices, use a randomized pivot to avoid pathological inputs, and fall back to insertion sort for small partitions. Keeping the class consistent (all instance methods or all static) makes calling the method from main less confusing; the original code mixes both. Also note a few issues seen in the thread: the main method reuses the same variable name for multiple arrays, displayTen actually prints 100 entries, and the existing insertion/linear-search implementations have loop-condition bugs that should be corrected.

Add these members to SortClass (they use the existing swap method):

private final java.util.Random rnd = new java.util.Random();

public void quickSort(int[] a) {
    if (a == null || a.length < 2) return;
    quickSort(a, 0, a.length - 1);
}

private void quickSort(int[] a, int lo, int hi) {
    while (lo < hi) {
        if (hi - lo < 16) {                // small partition -> insertion sort
            insertionSortRange(a, lo, hi);
            break;
        }
        int p = partitionRandom(a, lo, hi);
        // recurse on smaller side first to limit stack depth
        if (p - lo < hi - p) {
            quickSort(a, lo, p - 1);
            lo = p + 1;
        } else {
            quickSort(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

private int partitionRandom(int[] a, int lo, int hi) {
    int pivotIndex = lo + rnd.nextInt(hi - lo + 1);
    swap(a, pivotIndex, hi);
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) swap(a, i++, j);
    }
    swap(a, i, hi);
    return i;
}

private void insertionSortRange(int[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = a[i], j = i - 1;
        while (j >= lo && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

Notes: the random pivot + tail-recursion-on-smaller-side reduces stack-use and avoids worst-case O(n^2) on sorted inputs; switching to insertion sort for tiny ranges improves real-world speed. For production use, java.util.Arrays.sort(int[]) is recommended because it’s highly tuned. Credit to for the quick sample in the thread and to for confirming a working approach.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

abhishek20 -3 Newbie Poster · Answer 1 · 2011-04-01T14:52:50+00:00

Add thess function in your sort class

public void quickSort(int array[]) 

{
	quickSort(array, 0, array.length - 1);              
}


public void quickSort(int array[], int start, int end)
{
     int i = start;                          
     int k = end;                            

     if (end - start >= 1)                   
     {
             int pivot = array[start];       
             while (k > i)                   
             {
                     while (array[i] <= pivot && i <= end && k > i)  
                             i++;                                    
                     while (array[k] > pivot && k >= start && k >= i) 
                         k--;                                        
                     if (k > i)                                       
                             swap(array, i, k);                      
             }
             swap(array, start, k);          
                                              
             quickSort(array, start, k - 1); 
             quickSort(array, k + 1, end);  
     }
     else    
     {
             return;                   
     }
}

Add this code to execute the sort from main

int numbers4 [] = new int[10000];
		sl.makeData(numbers4);
		sl.quickSort(numbers4);
		sl.displayTen(numbers4);

Thendi 0 Newbie Poster · Answer 2 · 2011-04-02T07:06:00+00:00

Thanks, I did a different method but this works to, I just tried it. :)