Hey i have the task to write a code to compute the median from an array. I My teacher gave me the following instructions:

Algorithm for the list l with length n > 1 and the position i:

1. divide the n elements from the list L in ⌊n/5⌋ groups with 5 elements and <= 1 group with n mod 5 elements.

2. compute the median from each of the ⌈n/5⌉ groups

3. compute recursively the median x of the medians from step 2

4. partition the list L in 2 lists L1 with all numbers < x and L2 with all numbers > x. Also compute the length l1 and l2 of the lists (x will be on the position k = l1 1)

5. if i = k return x, if i < k compute the first element of L1 recursively and if i > k compute the (i-k)th element in L2 recursively.

So my question is, what exactly is the "i"? i already wrote the code and everything is working good, except step 5 because i don't know what the i is and how to use it. How is it defined and how does it change in the recursion?

CodePudding user response：

This is honestly a too much common term in programming and also a very basic concept. Here, 'i' means current index. So, for instance, if you're on the index 4 and l1 is 3 then i == k (as it's mentioned before that k = l1 1), you have to return x!

CodePudding user response：

The algorithm you’ve listed solves the following problem:

Given an (unsorted) array A and an index i, return the ith smallest item in array A.

So, for example, if you have an array A of length 5, then if i = 0 you’re asking for the smallest element in the array, if i = 2 you’re asking for the median, and if i = 4 you’re asking for the largest element of the array.

(This use of the variable i is specific to the problem statement as it was given to you. It’s not something that generally has this meaning.)