Max and Min in Array

[Benh]

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

 

[specci48]

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

sampleArray(0)

and

sampleArray(ArrayLen(sampleArray()) - 1)

or vice versa.


specci48

 

[agraham]

maybe it's not the fastest solution

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.

 

[RB Smissaert]

I don't think anything else would be faster than that.

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:

Sub Globals
   Public arr(100000) As int64
   Public bDoTiming
   Public lTicks(1) As Int64
End Sub

Sub 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 Sub

Sub StartTimer
   lTicks(0) = dzHW.GetTickCount 
End Sub

Sub 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 If
End 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

 

[Benh]

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

 

[RB Smissaert]

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

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

 

[Benh]

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

 

[Benh]

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

Many thanks again, Ben

 

[RB Smissaert]

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

RBS

 

[Erel]

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

 

[RB Smissaert]

I expected the difference to be bigger and maybe it is on the device. Not tested that yet.
BTW, Erel, I have no idea how I got that award as I have done no beta-testing.

RBS

 

[RB Smissaert]

On the device (Samsung Omnia, optimized compiled) the difference is a lot bigger. Some 6-7 times slower when done with array sorting, compared to a simple loop.

RBS