Quicksort median of three pivot help

Expand Post »

Hello, BTW the program compiles. Im trying to change a quick sort program so that it picks a median of three for the pivot instead of the first low number. My code is not running right, can somebody help me out. thanks

java Syntax (Toggle Plain Text)
public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};
 
 
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }
 
  public static void quick_srt(int array[],int low, int n){
    int swap;
 
	 int lo = low;
    int hi = n;
    if (lo >= n) {
      return;
    }
	 //Pivot median of three
    int mid = array[(lo + hi) / 2];
	 if(array[mid] < array[lo]){
	swap = array[lo];
	 array[lo]=array[mid];
	 array[mid]=swap;
	 }
	 if(array[hi] < array[lo]){
	 swap = array[lo];
	 array[lo]= array[hi];
	 array[hi]= swap;
	 }
	 if(array[mid] < array[lo]){
	 swap = array[mid];
	 array[mid]= array[hi];
	 array[hi] = swap;
	 }
	 swap = array[mid];
	 array[mid]= array[hi-1];
	 array[hi-1]= swap;
 
    while (lo < hi) {
      while (lo<hi && array[lo] < mid) {
        lo++;
      }
      while (lo<hi && array[hi] > mid) {
        hi--;
      }
      if (lo < hi) {
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    quick_srt(array, low, lo);
    quick_srt(array, lo == low ? lo+1 : lo, n);
  }
}
public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};

   
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }

  public static void quick_srt(int array[],int low, int n){
    int swap;
	
	 int lo = low;
    int hi = n;
    if (lo >= n) {
      return;
    }
	 //Pivot median of three
    int mid = array[(lo + hi) / 2];
	 if(array[mid] < array[lo]){
	swap = array[lo];
	 array[lo]=array[mid];
	 array[mid]=swap;
	 }
	 if(array[hi] < array[lo]){
	 swap = array[lo];
	 array[lo]= array[hi];
	 array[hi]= swap;
	 }
	 if(array[mid] < array[lo]){
	 swap = array[mid];
	 array[mid]= array[hi];
	 array[hi] = swap;
	 }
	 swap = array[mid];
	 array[mid]= array[hi-1];
	 array[hi-1]= swap;
	 
    while (lo < hi) {
      while (lo<hi && array[lo] < mid) {
        lo++;
      }
      while (lo<hi && array[hi] > mid) {
        hi--;
      }
      if (lo < hi) {
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    quick_srt(array, low, lo);
    quick_srt(array, lo == low ? lo+1 : lo, n);
  }
}

Similar Threads

Dio1080

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

47 posts
since Aug 2007

Permalink

Apr 28th, 2009

Re: Quicksort median of three pivot help

Dear,

There are some missing statement in your program.

Please compare following code with your source code.

Java Syntax (Toggle Plain Text)
public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};
 
 
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }
 
  public static void quick_srt(int []k,int lb,int ub) {
      boolean flag=true;
      int i,j,key,temp;
 
      if(lb<ub)
         {
            i=lb;
            j=ub+1;
            key=k[lb];
            while(flag) {
                i++;
                while(k[i]<key && i<ub)
                    i++;
                j--;
                while(k[j]>key && j>lb)
                    j--;
                if(i<j) {
                    temp=k[i]; k[i]=k[j]; k[j]=temp;
                }
                else
                   flag=false;
            }
            temp=k[lb];
            k[lb]=k[j];
            k[j]=temp;
            quick_srt(k,lb,j-1);
            quick_srt(k,j+1,ub);
         }
  }
}
public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};

   
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }

  public static void quick_srt(int []k,int lb,int ub) {
      boolean flag=true;
      int i,j,key,temp;

      if(lb<ub)
         {
            i=lb;
            j=ub+1;
            key=k[lb];
            while(flag) {
                i++;
                while(k[i]<key && i<ub)
                    i++;
                j--;
                while(k[j]>key && j>lb)
                    j--;
                if(i<j) {
                    temp=k[i]; k[i]=k[j]; k[j]=temp;
                }
                else
                   flag=false;
            }
            temp=k[lb];
            k[lb]=k[j];
            k[j]=temp;
            quick_srt(k,lb,j-1);
            quick_srt(k,j+1,ub);
         }
  }
}

adatapost

Moderator

Reputation Points: 2136

Solved Threads: 1228

Posting Genius

Offline

6,527 posts
since Oct 2008

Permalink

Apr 29th, 2009

Re: Quicksort median of three pivot help

Personally I wouldn't listen to anyone who pastes code at you and doesn't explain it at all, but that's just me. I don't understand what you mean by "median of three", care to explain?

BestJewSinceJC

Reputation Points: 874

Solved Threads: 352

Posting Maven

Offline

2,758 posts
since Sep 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Java Forum Timeline: Sharing Entity Class Between Computers

Next Thread in Java Forum Timeline: Reading data to a file

DaniWeb Message

Cancel Changes

User Name
Password