Re: sort algorithm
Re: sort algorithm
- Subject: Re: sort algorithm
- From: Dan Messing <email@hidden>
- Date: Sun, 29 Jan 2006 14:18:57 -0600
Sounds like a Binary Search:
http://en.wikipedia.org/wiki/Binary_search
If you were sorting (it sounds like you're searching an already
sorted list, not sorting), the similar idea is called Quicksort.
Dan Messing
Stunt Software
http://www.stuntsoftware.com/
On Jan 29, 2006, at 2:01 PM, email@hidden wrote:
Message: 7
Date: Sun, 29 Jan 2006 14:50:53 -0500
From: Robert Dell <email@hidden>
Subject: sort algorithm
To: Cocoa List <email@hidden>
Message-ID: <email@hidden>
Content-Type: text/plain; charset=us-ascii; format=flowed
out of curiosity, i'm wondering what this algorithm is called (if
it has a name or is it my own creation)
i start out entering the routine with 0 and [myRoomArray count]-1.
it takes the middle point and tests it
if it finds it then it returns immediately. if it's less than that
then it takes 0 and mid-1, if greater it takes mid+1 and max and
sends that to the routine again
guaranteed to find anything or insert anything in an array of say
30,000 in 15 tests (30 for double testing)
----- clip -----
-(long)treeSearchWithLeft: (long) leftRec withRight: (long) rightRec;
{
NSComparisonResult myCompareResult;
long returnval = 0;
long split = 0;
if ((rightRec > leftRec) && (leftRec > -1))
{
split = ((rightRec-leftRec)/2)+leftRec;
myCompareResult = [[[myRoomArray objectAtIndex: split]
objectForKey: @"roomTitle"] caseInsensitiveCompare: roomTitle];
if (myCompareResult == NSOrderedDescending) // gt
{
returnval = [self treeSearchWithLeft: leftRec withRight:
split-1];
}
else if (myCompareResult == NSOrderedAscending) // lt
{
returnval = [self treeSearchWithLeft: split+1 withRight:
rightRec];
}
else if (myCompareResult == NSOrderedSame) // eq
{
myCompareResult = [[[myRoomArray objectAtIndex: split]
objectForKey: @"roomDescription"] caseInsensitiveCompare:
roomDescription];
if (myCompareResult == NSOrderedDescending) // gt
{
returnval = [self treeSearchWithLeft: leftRec withRight:
split-1];
}
else if (myCompareResult == NSOrderedAscending) // lt
{
returnval = [self treeSearchWithLeft: split+1 withRight:
rightRec];
}
else if (myCompareResult == NSOrderedSame) // eq
{
returnval = [[[myRoomArray objectAtIndex: split]
objectForKey: @"RoomIndex"] longValue];
}
}
}
else
{
myCompareResult = [[[myRoomArray objectAtIndex: leftRec]
objectForKey: @"roomTitle"] caseInsensitiveCompare: [NSString
stringWithString: roomTitle]];
if (myCompareResult == NSOrderedDescending) // gt
{
[self insertRoomAtIndex: leftRec];
returnval = [[[myRoomArray objectAtIndex: leftRec]
objectForKey: @"RoomIndex"] longValue];
}
else if (myCompareResult == NSOrderedAscending) // lt
{
[self insertRoomAtIndex: leftRec + 1];
returnval = [[[myRoomArray objectAtIndex: (leftRec + 1)]
objectForKey: @"RoomIndex"] longValue];
}
else if (myCompareResult == NSOrderedSame) // eq
{
myCompareResult = [[[myRoomArray objectAtIndex: leftRec]
objectForKey: @"roomDescription"] caseInsensitiveCompare:
roomDescription];
if (myCompareResult == NSOrderedDescending) // gt
{
[self insertRoomAtIndex: leftRec];
returnval = [[[myRoomArray objectAtIndex: leftRec]
objectForKey: @"RoomIndex"] longValue];
}
else if (myCompareResult == NSOrderedAscending) // lt
{
[self insertRoomAtIndex: leftRec+1];
returnval = [[[myRoomArray objectAtIndex: (leftRec + 1)]
objectForKey: @"RoomIndex"] longValue];
}
else if (myCompareResult == NSOrderedSame) // eq
{
returnval = [[[myRoomArray objectAtIndex: leftRec]
objectForKey: @"RoomIndex"] longValue];
}
}
}
return returnval;
};
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden