Largest of array without sorting?

Unity Engine
1

Searched around and couldn’t find a answer.

Can anyone help me get the largest, second largest, and so on out of a int array without sorting it please?

2

//try something like this;

var largest : int = 0; // can be float also
var seclargest : int =0;

var testarr : Array = new Array(48,1,3,4,5,7,2,4,0,15,36); // your array here
var i : int = 0;

for(i=0;i<testarr.length;i++)
{
if(largest < testarr*)*
{
seclargest = largest;
largest = testarr*;*
}
else if((seclargest < testarr*) ( seclargest < largest))*
{
seclargest = testarr*;*
}
}
Debug.Log(largest + " " + seclargest);

3

// actually more like this

//try something like this;

var largest : int = 0; // can be float also
var seclargest : int =0;

var testarr : Array = new Array(48,1,3,4,5,7,2,4,0,15,36); // your array here
var i : int = 0;

for(i=0;i<testarr.length;i++)
{
if(largest < testarr*)*
{
seclargest = largest;
largest = testarr*;*
}
else if(seclargest < testarr*)*
{
seclargest = testarr*;*
}
}
Debug.Log(largest + " " + seclargest);

4

Well, here’s a start. This code will find the largest number of any array of numbers called myArray, as well as which position it’s in:

function Awake() {
	var largestVar = 0;
	var largestVarPlace = 0;
	for (i=0; i<myArray.length; i++) {
		var tempVar = myArray[i];
		if (tempVar > largestVar) {
			largestVar = tempVar;
			largestVarPlace = i;
		}
	}
	//print (largestVar);
	//print (largestVarPlace);
}

Now that you know where the largest number is, as well as it’s place, you have to take it out of the array, and then go through the process again… I’m a little short on time, but hopefully this is a place to start.

EDIT: Looks like someone beat me too it… his solution should work too, as long as you always know the length of the array, since you need to hold a seperate variable for each one.

5

Thanks! :smile:

6

Heres what i got working if anyone needs it (may have a bug but seems fine). placea is a length 5 array of ints indexed in a specific order:

var i : int = 0;
var largest : int = 0;
var secondlargest : int =0;
var thirdlargest : int = 0;
var fourthlargest : int =0;
var fifthlargest : int = 0;
for(i=0;i<placea.length;i++) {
if (largest < placea[i]) {
fifthlargest = fourthlargest;
fourthlargest = thirdlargest;
thirdlargest = secondlargest;
secondlargest = largest;
largest = placea[i];
} 
else if (secondlargest < placea[i]) {
fifthlargest = fourthlargest;
fourthlargest = thirdlargest;
thirdlargest = secondlargest;
secondlargest = placea[i];
}
else if (thirdlargest < placea[i]) {
fifthlargest = fourthlargest;
fourthlargest = thirdlargest;
thirdlargest = placea[i];
}
else if (fourthlargest < placea[i]) {
fifthlargest = fourthlargest;
fourthlargest = placea[i];
}
else if (fifthlargest < placea[i]) { 
fifthlargest = placea[i];
}
}

var first : int = (System.Array.IndexOf(placea, largest));
var second : int = (System.Array.IndexOf(placea, secondlargest));
var third : int = (System.Array.IndexOf(placea, thirdlargest));
var fourth : int = (System.Array.IndexOf(placea, fourthlargest));
var fifth : int = (System.Array.IndexOf(placea, fifthlargest));

print (placeb[first] + " is first " +placeb[second] + " is second " + placeb[third] + " is third " +placeb[fourth] + " is fourth " +placeb[fifth] +" is fifth");
7

all of that is sorting (single run through of bubble sort basically), you are just not storing the sort.

you can’t find the largest without checking each item at least once and by doing so you are actually sorting it.

the difference is that not doing sorting actually will do the whole sorting work over and over again should you search for the maximum more than once.

Generally the cheapest way to get “sorting” without sorting is a binary heap. it does “get max/min” instantanous and inserts / removes on a log(n) base (with n beeing number of elements). also its dead simple to implement and understand with many c# sources on the web.

8

Good point there from Dreamora. Another very effective technique is a modification of quicksort known as “quickselect”. It’s essentially the same algorithm as quicksort, but you just don’t bother recursively sorting parts of the array you aren’t interested in. The subject of selection is covered quite well on Wikipedia, although that may have changed by the time you read the article :wink:

9

Why not just make a copy of the array and sort the copy. Then you can pull out the highest values.

10

because you do the sorting again on each “get maximum” call as the copy won’t be up to date.

Thats the benefit of heaps, they are always up to date as the “min first” / “max first” criteria can’t be broken (they often form the base of priority queues or are priority queues, always depending on the requirements)