Max and Min in Array

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

  1. Benh

    Benh Member Licensed User

    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
     
  2. specci48

    specci48 Well-Known Member Licensed User

    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
  3. agraham

    agraham Expert Licensed User

    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.
     
  4. RB Smissaert

    RB Smissaert Well-Known Member Licensed User

    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(100000As int64
       
    Public bDoTiming
       
    Public lTicks(1As 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 (1001000)
       
    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(),
    0100000, 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
     
  5. Benh

    Benh Member Licensed User

    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
     
  6. RB Smissaert

    RB Smissaert Well-Known Member Licensed User

    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 (1001000)
       
    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
     
  7. Benh

    Benh Member Licensed User

    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
     
  8. Benh

    Benh Member Licensed User

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

    Many thanks again, Ben
     
  9. RB Smissaert

    RB Smissaert Well-Known Member Licensed User

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

    RBS
     
  10. Erel

    Erel Administrator Staff Member Licensed User

    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
     
  11. RB Smissaert

    RB Smissaert Well-Known Member Licensed User

    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
     
  12. RB Smissaert

    RB Smissaert Well-Known Member Licensed User

    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
     
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice