Whats the Best Way to Find Heighest Number in A List?

[riveryu]

As topic title stated, Whats the Best Way to Find Heighest Number in A List?
heres what i know so far:

Turing:

var nums : array 1 .. 6 of int := init (60, 42, 29, 90, 22, 91) fcn Hnum (var nums : array 1 .. * of int) : int %compile time expression was freaking needed var n : int     for i : lower (nums) .. upper (nums)                 n := nums (lower (nums))         if n <= nums (i)                 then             n := nums (i)         end if     end for     result n end Hnum put Hnum (nums)

[CodeMonkey2000]

Off the top of my head:

Turing:

var nums : array 1 .. 6 of int := init (60, 42, 29, 90, 22, 91) fcn Hnum (var nums : array 1 .. * of int) : int %compile time expression was freaking needed     var n := nums (lower (nums))     for i : lower (nums) .. upper (nums)         n := max (n, nums (i))     end for     result n end Hnum put Hnum (nums)

[Tony]

You could do some fancy optimization if you know that your list is sorted. Otherwise you'd have to check every single number once. So what CodeMonkey has posted.

[riveryu]

thx guys, isnt there a recursive method for this or something?

[[Gandalf]]

Sure, but you're probably talking about sorting it first and then searching through the ordered list? If so, you can look up methods of doing this such as linear search, binary search, bubble sort, quick sort, etc. Most of these are either recursive in nature or have a recursive implementation.

[r691175002]

If the list is not sorted, you are going to have to check every number at some point. There isn't much you can do about it.

If the list is sorted, then you just pick off the top number. I believe good sorting algorithms can beat a linear search in very large arrays but I am not sure.

[gitoxa]

I'm very doubtful about that. A sorting algorithm has to go through every single value in order to make sure they're all in order. I may not know too many different sorting algorithms, but logic says that if it doesn't actually look at some numbers, those numbers may not be in the correct position.

[Tony]

r691175002 @ Wed May 21, 2008 9:26 pm wrote:

I believe good sorting algorithms can beat a linear search in very large arrays but I am not sure.

I'm sure that a lot of people would love to see a sort algorithm that matches O(n), let alone be faster.

[Reality Check]

The way you have it, you'd have to check each one and compare them one by one. This, of course, gets very inefficient once your list gets bigger. Now, is this a saved list in a file or is there a new list every time the program is run? If you save the info in a file or something and use these numbers often, sort them first (and sort every time you add a new number). Once it's sorted, you can use Binary Search for very fast searching (look up Binary Search). For sorting, look up Quick Sort or Bubble Sort.

But ultimately, as has been suggested in this topic before, the answer to your search of efficiency is to sort your information first.

[Vermette]

Reality Check @ May 22nd 2008, 20:39 wrote:

Once it's sorted, you can use Binary Search for very fast searching (look up Binary Search)

Binary search would only be valuable to him if he was looking for the existence of a particular value within a sorted array. If you know a list is sorted, finding the largest value is O(1) (simply look at the proper index value instead of the O(log n) required of a binary search.)

In very large datasets, Heapsort can be superior to Quicksort (dependent on implementation of course). Quicksort in the worst case can take O(n^2), whereas Heapsort is always O(n log n). Quicksort implementations can avoid worst case by randomizing what the pivot value will be, reducing the complexity to an average case of O(n log n). This is good, but heapsort is also an in-place sorting algorithm, never needing to allocate additional storage for sorting beyond a fixed amount. Quicksort, in the best case requires O(log n) space to sort.

[Reality Check]

Hmm, I'd never heard of Heapsort...better look that up.

[riveryu]

So..uh..
Theres no better way to find the highest number in a random unsorted list because the problem its too shallow?

Also, what does "O(n)" mean?

Thanks for all who responded.

[Tony]

O(n) is Big-O of order n -- meaning linear. If you have an array of size n, the algorithm will perform a (constant multiple of) n operations. (so for each element it will check it one, for example)

Other common functions are O(n^2) -- quadratic, such as in a bubble sort. Because for every element you check it against every other element, so n^2 operations for an array of size n.

Big-O is a common way to compare efficiencies of the algorithms.

[riveryu]

thanks Tony, that clears it.

[chopperdudes]

hey river, navabi's class had to make a program where you enter the number of numbers you want to compare, and then enter all the numbers, then output the list and the biggest number. here's what i've came up, i guess not rly any dif than thsoe posted here though.

code:

var N : int var number : real var Max : real := 0 put "please input value of N " .. get N put "please input ", N, " numbers " var numbers : array 1 .. N of real for i : 1 .. N     put "please input number " ..     get number     numbers (i) := number     if i not= 1 then         Max := max (numbers (i), Max)     end if end for for i : 1 .. N     put numbers (i), ", " .. end for put "" put "The biggest number is ", Max, "."

btw how'd u do the turing code thingy?