4 Replies Latest reply on Jun 14, 2007 2:17 AM by 807600

# Finding median of an array

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,
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
Does the code work?

• ###### 2. Re: Finding median of an array
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
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
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.