4 Replies Latest reply: Jun 13, 2007 9:17 PM by 807600 RSS

    Finding median of an array

    807600
      I need to find the middle of an array, partition the array that contains the middle elememt and sort it. I'm stuck in the approach to take in coming up with a solution. Here is what I've come up with but am not sure if this is correct. Any ideas will greatly be appreciated!

      I used the recQuickSort(int, int) to partition the array and set the pivot, but I don't know how to find the middle.
      class ArrayPar
         {
         private long[] theArray;          // ref to array theArray
         private int nElems;               // number of data items
      //--------------------------------------------------------------
         public ArrayPar(int max)          // constructor
            {
            theArray = new long[max];      // create the array
            nElems = 0;                    // no items yet
            }
      //--------------------------------------------------------------
         public void insert(long value)    // put element into array
            {
            theArray[nElems] = value;      // insert it
            nElems++;                      // increment size
            }
      //--------------------------------------------------------------
         public int size()                 // return number of items
            { return nElems; }
      //--------------------------------------------------------------
         public void display()             // displays array contents
            {
            System.out.print("A=");
            for(int j=0; j<nElems; j++)    // for each element,
               System.out.print(theArray[j] + " ");  // display it
            System.out.println("");
            }
      
      //--------------------------------------------------------------
      
      public void quickSort()
      {
      recQuickSort(0, nElems-1);
      }
      
      //--------------------------------------------------------------
      
      public void recQuickSort(int left, int right)
      {
           int size = right - left + 1;
           if(size <= 3)          // insertion sort if small
                insertionSort(left, right);
      
           if(right-left <= 0) // if size <= 4,
                return; // already sorted
           else // size is 4 or larger
           {
                long pivot = theArray[right]; // rightmost item
      
                                    // partition range
                int partition = partitionIt(left, right, pivot);
                recQuickSort(left, partition-1); // sort left side
                recQuickSort(partition+1, right); // sort right side
           }
      } // end recQuickSort()
      
      //--------------------------------------------------------------
      
      public void insertionSort(int left, int right)
      {
           int in, out;
           
           for(out = left+1; out <= right; out++)
           {
                long temp = theArray[out];
                in = out;
                
                while(in > left && theArray[in-1] >= temp)
                {
                     theArray[in] = theArray[in-1];          // shift item to right
                     --in;
                }
                theArray[in] = temp;
           }  //end for
      }  //end insertionSort()
      
      //--------------------------------------------------------------
          public int partitionIt(int left, int right, long pivot)
             {
             int leftPtr = left - 1;           // right of first elem
             int rightPtr = right + 1;         // left of pivot
             while(true)
                {
                while(leftPtr < right &&       // find bigger item
                      theArray[++leftPtr] < pivot)
                   ;  // (nop)
      
                while(rightPtr > left &&       // find smaller item
                      theArray[--rightPtr] > pivot)
                   ;  // (nop)
                if(leftPtr >= rightPtr)        // if pointers cross,
                   break;                      //    partition done
                else                           // not crossed, so
                   swap(leftPtr, rightPtr);    //    swap elements
                }  // end while(true)
             return leftPtr;                   // return partition
             }  // end partitionIt()
      //--------------------------------------------------------------
         public void swap(int dex1, int dex2)  // swap two elements
            {
            long temp;
            temp = theArray[dex1];             // A into temp
            theArray[dex1] = theArray[dex2];   // B into A
            theArray[dex2] = temp;             // temp into B
            }  // end swap()
      //--------------------------------------------------------------
         }  // end class ArrayPar
      ////////////////////////////////////////////////////////////////
      class PartitionApp
         {
         public static void main(String[] args)
            {
            int maxSize = 16;             // array size
            ArrayPar arr;                 // reference to array
            arr = new ArrayPar(maxSize);  // create the array
      
            for(int j=0; j<maxSize; j++)  // fill array with
               {                          // random numbers
               long n = (int)(java.lang.Math.random()*199);
               arr.insert(n);
               }
            arr.display();                // display unsorted array
      
            long pivot = 99;              // pivot value
            System.out.print("Pivot is " + pivot);
            int size = arr.size();
                                          // partition array
            int partDex = arr.partitionIt(0, size-1, pivot);
      
            System.out.println(", Partition is at index " + partDex);
            arr.display();                // display partitioned array
            }  // end main()
         }  // end class PartitionApp
      ////////////////////////////////////////////////////////////////
        • 1. Re: Finding median of an array
          807600
          Does the code work?

          Also, your comments are meaningless and only clutter your code.
          • 2. Re: Finding median of an array
            807600
            No that code ended up not working correctly after I made changes to it.
            Thanks for the tip on the comments.

            This program works but is not giving me the output I'm looking for.

            A = 38 158 108 160 38 132 100 54 95 85 159 188 194 28 137 149
            Middle Number: 54
            Middle Number: 149
            A = 16 28 38 54 132 85 95 100 137 149 194 158 159 188
            class ArrayPar
               {
               private long[] theArray;         
               private int nElems;               
            
               public ArrayPar(int max)          
                  {
                  theArray = new long[max];      
                  nElems = 0;                    
                  }
            
               public void insert(long value)   
                  {
                  theArray[nElems] = value;      
                  nElems++;                     
                  }
            
               public int size()                 // return number of items
                  { return nElems; }
            
               public void display()             // displays array contents
                  {
                  System.out.print("A=");
                  for(int j=0; j<nElems; j++)    
                     System.out.print(theArray[j] + " ");  
                  System.out.println("");
                  }
            
            public void quickSort()
            {
            recQuickSort(0, nElems-1);
            }
            
            
            public void recQuickSort(int left, int right)
            {
                 int size = right - left + 1;
            
                 if(size < 10)                    // insertion sort if small
                      insertionSort(left, right);
                 else
                 {
                      long median = median(left, right);
                      System.out.println("Middle Number: " + median + " ");
                      int partition = partitionIt(left, right, median);
            
                      recQuickSort(left, partition-1); 
                      recQuickSort(partition+1, right); 
                 } // end else
            
            } // end recQuickSort()
            
            
            public long median(int left, int right)
            {     
                 int center = (left + right) / 2;
                 
                 if( theArray[left] > theArray[center] )
                      swap(left, center);
            
                 if( theArray[left] > theArray[right] )
                      swap(center, right);
            
                 if( theArray[center] > theArray[right] )
                      swap(center, right);
            
                 swap(center, right-1);
                 
                 return theArray[right-1];
            } // end median()
            
            
            public void insertionSort(int left, int right)
            {
                 int in, out;
                 
                 for(out = left+1; out <= right; out++)
                 {
                      long temp = theArray[out];
                      in = out;
                      
                      while(in > left && theArray[in-1] >= temp)
                      {
                           theArray[in] = theArray[in-1];          
                           --in;
                      }
                      theArray[in] = temp;
                 }  //end for
            }  //end insertionSort()
            
                public int partitionIt(int left, int right, long pivot)
                   {
                   int leftPtr = left - 1;       
                   int rightPtr = right + 1;        
                   while(true)
                      {
                      while(leftPtr < right &&     
                            theArray[++leftPtr] < pivot)
                         ;  // (nop)
            
                      while(rightPtr > left &&      
                            theArray[--rightPtr] > pivot)
                         ;  // (nop)
                      if(leftPtr >= rightPtr)       
                         break;                     
                      else                          
                         swap(leftPtr, rightPtr);    
                      }  // end while(true)
                   return leftPtr;                   
                   }  // end partitionIt()
            
            
               public void swap(int dex1, int dex2)  
                  {
                  long temp;
                  temp = theArray[dex1];           
                  theArray[dex1] = theArray[dex2];   
                  theArray[dex2] = temp;             
                  }  // end swap()
            
               }  // end class ArrayPar
            
            class PartitionApp
               {
               public static void main(String[] args)
                  {
                  int maxSize = 16;            
                  ArrayPar arr;               
                  arr = new ArrayPar(maxSize);
            
                  for(int j=0; j<maxSize; j++) 
                     {                        
                     long n = (int)(java.lang.Math.random()*199);
                     arr.insert(n);
                     }
                  arr.display();                // display unsorted array  
                  arr.quickSort();              
                  arr.display();                // display partitioned array
                  }  // end main()
               }  // end class PartitionApp
            • 3. Re: Finding median of an array
              807600
              partition the array that contains the middle elememt and sort it.
              Seems a strange requirement. The easiest way to find the median is to have all the values already sorted.
              • 4. Re: Finding median of an array
                807600
                I may not have worded it very well. The array has 16 elements. The middle element is 8. If you partition this array and the pivot ends up at 9, then you need to partition again from 0 to 9 (the partition that contains the 8), not 10 to 16. If the pivot ends up at 2, you need to partition from 2 to 16 not 0 to 1. You continue partitioning the appropriate partitions recursively, always checking if the pivot falls on the middle element.