Max and Min in Array

Discussion in 'Questions (Windows Mobile)' started by Benh, Jul 3, 2009.

I have an array in integers.

Is there an easy way to find the Max and Min in the array and their index positions?

Many thanks, Ben

Hi Benh,

maybe it's not the fastest solution but if you use the ArraysEx library of agraham you can sort the array so that the min and max value are
Code:
`sampleArray(0)`
and
Code:
`sampleArray(ArrayLen(sampleArray()) - 1)`
or vice versa.

specci48

Last edited: Jul 3, 2009

I don't think anything else would be faster than that. Internally it seems it uses the QuickSort algorithm which is probably the fastest in this situation.

I couldn't believe that getting the min and max of an array was faster with sorting then just running a simple loop, so I tested it and unless I am overlooking something a simple loop is indeed about 50% faster:

Code:
`Sub Globals   Public arr(100000) As int64   Public bDoTiming   Public lTicks(1) As Int64End SubSub App_Start   Dim i   Dim lMin   Dim lMax      dzHW.New1   ArraysEx.New1      'fill the array   '--------------   For i = 0 To 99999      arr(i) = Rnd (100, 1000)   Next i      lMin = arr(0)      'first get min and max without sorting   '-------------------------------------   StartTimer      For i = 0 To 99999      If arr(i) > lMax Then         lMax = arr(i)      Else         If arr(i) < lMin Then            lMin = arr(i)         End If      End If   Next i      StopTimer("get min and max without sorting")      Msgbox("minimum: " & lMin, "maximum: " & lMax)      'then get min and max with sorting   '---------------------------------   StartTimer      ArraysEx.Sort(arr(),0, 100000, cNumber)      StopTimer("get min and max with sorting")      Msgbox("minimum: " & arr(0), "maximum: " & arr(99999))   End SubSub StartTimer   lTicks(0) = dzHW.GetTickCount End SubSub StopTimer(strProcedure)   If Msgbox("Time taken in " & strProcedure & CRLF & CRLF & _             dzHW.GetTickCount - lTicks(0) & " milli-seconds", _             "Code timer", _             cMsgboxOKCancel, cMsgboxNone) = cCancel Then      bDoTiming = False   End IfEnd Sub`

Also it is simple to get the index of the min and max with a simple loop, but it will involve some more coding if you do a sort.

RBS

Thanks Guys

Where do I find the ArraysEx library?

Will this method preserve the index position of the max and Min values?

I actually need to use a 2d array. I not only need to find the Max and Min but also the value of their 'pair'. I hope that makes sense.

Thanks again, Ben

To get the min and max and the index of those values:

Code:
`Sub App_Start   Dim i   Dim lMin   Dim lMax   Dim lMinIndex   Dim lMaxIndex      dzHW.New1   ArraysEx.New1      'fill the array   '--------------   For i = 0 To 99999      arr(i) = Rnd (100, 1000)   Next i      lMin = arr(0)      'first get min and max without sorting   '-------------------------------------   StartTimer      For i = 0 To 99999      If arr(i) > lMax Then         lMax = arr(i)         lMaxIndex = i      Else         If arr(i) < lMin Then            lMin = arr(i)            lMinIndex = i         End If      End If   Next i      StopTimer("get min and max without sorting")      Msgbox("minimum: " & lMin & " at index: " & lMinIndex, _         "maximum: " & lMax & " at index: " & lMaxIndex)   End Sub`

RBS

Thanks RBS

You post poped in while I was writing my reply!

I like your simple min max method.

It soudldn't be too hard to find their index either.

Ben

hey....... you did it agian!

Many thanks again, Ben

I though it would be funny to get the answer in before the question.

RBS

The books agree with RBS. Sorting the array is O(n*log(n)) operation, while going over all the items in a simple way is O(n) operation. So if all you need is the min and max values then this is the best solution. Big O notation - Wikipedia, the free encyclopedia