asked on

quicksort prog in java

I am newbie in programming. i just read the quicksort algo and was trying to convert it to a java program. But as expected it doesn't work.
Can some one please correct it.

class QuickSortProg {

private static int lower[] = new int[10];
private static int upper[] = new int[10];
private static int temp;
      public static void main(String[] args)       {

       int array [] = {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66};
int top = 0;
            int n = array.length;

            if(n>1) {
              top = top + 1;
              lower[0] = 1;
              upper[0] = n;
            }

while(top != 0) {
top = top-1;
int beg = lower[top];
                   int end = upper[top];
       quick(array, n, beg, end);
            }
      }

static void quick(int a[], int n, int beg, int end) {

             int left = beg;
             int right = end;
             int loc = beg;

for(int i=0; i<n; i++)
       {
              while(a[loc] <= a[right] && loc != right) {
              right = right-1;
              }
if(loc == right)
                  return;

              if(a[loc] > a[right]) {
              temp = a[loc];
                   a[loc] = a[right];
                   a[right] = temp;
              }

              while(a[loc] <= a[left] && left != loc) {
              left = left+1;
              }
              if(loc == left)
                    return;

       if(a[left] > a[loc]) {
temp = a[left];
            a[left] = a[loc];
       a[loc] = temp;
              }
System.out.println(a);
       }
}
}

thanks

x4u

Sorry, I don't have the time right now to look closer at you program. But here is a quicksort in Java that will work.

public static void quickSortI( int[] arr, int pos, int end )
{
int idx = ( pos + end ) >> 1, idy = end;
int pivot = arr[ idx ];
arr[ idx ] = arr[ pos ];
idx = pos;

while( true )
{
while( ++idx < end && arr[ idx ] < pivot );
while( --idy > pos && pivot < arr[ idy ] );
if( idx > idy ) break;
int tmp = arr[ idx ];
arr[ idx ] = arr[ idy ];
arr[ idy ] = tmp;
}
arr[ pos ] = arr[ idy ];
arr[ idy ] = pivot;
if( pos + 1 < idy ) quickSort( arr, pos, idy );
if( idx + 1 < end ) quickSort( arr, idx, end );
}

ASKER CERTIFIED SOLUTION

sudhakar_koundinya

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

fini21

ASKER

thank you so much.
The solutions are slightly difficult for me to understand.
I have created the following program, it does the first pass that is 1 right scan and 1 left scan. Can someone plz tell me how to make it do successive scans. May be calling it recursilvely is the answer but how do i do it.
thanks a lot

class Sort {
      public static void main(String[] args)       {

            int a [] = {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66};
            int n = a.length;
            int right = n; //val
            int loc = 0;
       int left = 0;
            while(a[loc] < a[--right]) ;

            if(loc == right) return;
            if(a[loc] > a[right]) {

              int temp = a[loc];
              a[loc] = a[right];
              a[right] = temp;
loc = right;
       }

       while(a[left] < a[loc]) left++;

       if(loc == left) return;

       if(a[loc] < a[left]) {

       int temp = a[loc];
              a[loc] = a[left];
              a[left] = temp;
       loc = left;
       }
      }
}

fini21

ASKER

may be something like this

class Sort {
      public static void main(String[] args)       {
       Sort s = new Sort();
             s.sortMethod(new int[] {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66});
      }

      public void sortMethod(int []a) {

            int n = a.length;
            int right = n;
            int loc = 0;
       int left = 0;
            while(a[loc] < a[--right]) ;

            if(loc == right) return;
            if(a[loc] > a[right]) {

              int temp = a[loc];
              a[loc] = a[right];
              a[right] = temp;
loc = right;
       }

       while(a[left] < a[loc]) left++;

       if(loc == left) return;

       if(a[loc] < a[left]) {

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

      }
}

fini21

ASKER

may be this would be helpful in calling it recursively

class Sort {
      public static void main(String[] args)       {
       Sort s = new Sort();
             s.sortMethod(new int[] {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66}, 0, 12, 0);
      }

      public void sortMethod(int []a, int beg, int end, int loc) {

            int n = a.length;
            int right = n;
            loc = beg;
       int left = beg;
            while(a[loc] < a[--right]) ;

            if(loc == right) return;
            if(a[loc] > a[right]) {

              int temp = a[loc];
              a[loc] = a[right];
              a[right] = temp;
loc = right;
       }

       while(a[left] < a[loc]) left++;

       if(loc == left) return;

       if(a[loc] < a[left]) {

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

      }
}

JohnnyAffa

fini,

in your above example your not using recursion. to recurse, you must call the method itself ie

public [return type] sortMethod(int a[], int b, int c, int d)
{
while ( [condition] == true )
{
return sortMethod(a,b,c,d);
}
}

given you want to return an array you would return a[]

ie

public int[] sortMethod(int a[], int b, int c, int d)
{
while ( [condition] )
{
if ( [condition] )
return sortMethod(a,b,c,d);
else
doSomethingElse();

}

}

see sudhakar_koundinya example

sudhakar_koundinya

fini,

If you need of non recursive logic, here it is

/** Non-Recursive QuickSort */
static public void qsort(int[] array)
      {
      qsort_h(array, 0, array.length-1);
      }

/** Insertion Sort */
static public void inssort(int[] array)
      {
      int tmp;

      for (int i=1; i<array.length; i++) // Insert i'th record
       for (int j=i; (j>0) && (array[j]<array[j-1]); j--)
            //DSutil.swap(array, j, j-1);
            { tmp = array[j]; array[j] = array[j-1]; array[j-1] = tmp; }
      }

static private void qsort_h(int[] array, int oi, int oj)
      {
      int[] stack = new int[MAXSTACKSIZE]; // Stack for array bounds
      int listsize = oj-oi+1;
      int top = -1;
      int pivot;
      int pivotindex, l, r;
      int tmp;

      stack[++top] = oi; // Initialize stack
      stack[++top] = oj;

      while (top > 0) // While there are unprocessed subarrays
       {
       // Pop stack
       int j = stack[top--];
       int i = stack[top--];

       // Findpivot
       pivotindex = (i+j)/2;
       pivot = array[pivotindex];
       //DSutil.swap(array, pivotindex, j); // Stick pivot at end
       tmp = array[pivotindex]; array[pivotindex] = array[j]; array[j] = tmp;
       // Partition
       l = i-1;
       r = j;
       do
            {
            while (array[++l] < pivot);
            while ((r!=0) && (array[--r] > pivot));
            //DSutil.swap(array, l, r);
            tmp = array[l]; array[l] = array[r]; array[r] = tmp;
            } while (l < r);
       //DSutil.swap(array, l, r); // Undo final swap
       tmp = array[l]; array[l] = array[r]; array[r] = tmp;
       //DSutil.swap(array, l, j); // Put pivot value in place
       tmp = array[l]; array[l] = array[j]; array[j] = tmp;

       // Put new subarrays onto stack if they are small
       if ((l-i) > THRESHOLD) // Left partition
            {
            stack[++top] = i;
            stack[++top] = l-1;
            }
       if ((j-l) > THRESHOLD) // Right partition
            {
            stack[++top] = l+1;
            stack[++top] = j;
            }
       }
      inssort(array); // Final Insertion Sort
      }

Regards
Sudhakar

Mayank S

Better not go for the non-recursive version ;-) and let the JVM manage the stacks.

fini21

ASKER

thank you so much for replying.
what i wanted to know was is it possible to use recursion in the above code i have written. Is it even possible or i am on the wrong track.

sudhakar_koundinya

I haven't tested this but try

static void quick(int a[], int n, int beg, int end) {

int left = beg;
int right = end;
int loc = beg;

for(int i=0; i<n; i++)
{
while(a[loc] <= a[right] && loc != right) {
right = right-1;
}

if(a[loc] > a[right]) {
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
}

while(a[loc] <= a[left] && left != loc) {
left = left+1;
}
if(a[left] > a[loc]) {
temp = a[left];
a[left] = a[loc];
a[loc] = temp;
}
if(loc<right)
quick(a,loc,right);

if(loc<left)
quick(a,loc,left);

}
}
}

fini21

ASKER

getting ArrayindexoutofBoundsException here

while(a[loc] <= a[right] && loc != right) {
right = right-1;

sudhakar_koundinya

int[] sortMethod(int a[], int beg, int end) throws Exception
{
int left= beg;
int right = end;
int loc;

if ( end > beg)
{
loc = a[ ( beg + end ) / 2 ];
while( left<= right )
{
while( ( left< end ) && ( a[left] < loc ))
++left;
while( ( right > beg ) && ( a[right] > loc ))
--right;
if( left<= right )
{
int temp;
temp = a[left];
a[left] = a[right];
a[right] = temp;
++left;
--right;
}
}
if( beg < right )
sortMethod( a, beg, right );
if( left < end )
sortMethod( a, left, end );
}
return a;

}