Results 1 to 5 of 5
Thread: Need for Algorithm

112011, 17:13 #1Registered User
 Join Date
 Nov 2011
 Posts
 2
Need for Algorithm
Hello everyone,
i have an assignment and i would really appreciate it if any of you could help me.
The assignment is:
"You have a relation EMPLOYEES (clustered) sized B(R)>M,where M being the memory of your system.The EMPLOYEES has one attribute salary and you want to calculate the median of the salary of the employees in this relation:
SELECT MEDIAN(Employees.salary)FROM Employees.
Describe a sufficient algorithm (not SQL/code) that calculates questions as the above.
What is the cost of your algorithm"
I'd be very thankful if someone could help.Last edited by ugabuga; 112011 at 17:16.

112111, 18:08 #2Resident Curmudgeon
 Join Date
 Feb 2004
 Location
 In front of the computer
 Posts
 15,579
In theory, theory and practice are identical. In practice, theory and practice are unrelated.

112311, 18:04 #3Registered User
 Join Date
 Nov 2011
 Posts
 2
I'm not sure whether the cost is going to be 2,5B(R) or 3B(R).
I mean what do you do:read from the disk and sort in the memory and then flush to disk which has cost 2B(R) and then just read by the half and you'll find the median OR write to memory once more to sort the sorted sublists and then just pull the middle tuple therefor the cost is 3B(R) plus one tuplet???

113011, 13:19 #4World Class Flame Warrior
 Join Date
 Jun 2003
 Location
 Ohio
 Posts
 12,595
No problem.
First, get some more M. M is cheap. No excuse for running low on M these days.
Count the number of employees. Divide by two. Step through the employees sorted by salary until you hit that number.
$29.99, and I accept PayPal.
Again, no problem.If it's not practically useful, then it's practically useless.
blindman
www.chess.com: "sqlblindman"
www.LobsterShot.blogspot.com

120211, 17:13 #5Programming since 1BC
 Join Date
 Sep 2009
 Location
 Ontario
 Posts
 1,057
Here are some more ways:
Selection algorithm  Wikipedia, the free encyclopedia