Algorithms For Dummies

 Challenging Difficult Problems

The value index is called k, and the algorithm is also known as the largest kth value 

algorithm. It uses the following steps to obtain a result:

1. 

Determine a pivot number in the data list and split the list into two parts, a left 

list whose numbers are less than the pivot number, and a right list whose 

numbers are higher.

2. 

Determine the length of each list. When the length of the left list is larger than 

the kth position, the median value is inside the left part. The algorithm applies 

itself recursively to just that list.

3. 

Compute the number of pivot number duplicates in the list (subtract from the 

length of the list the length of the left and right sides).

4. 

Determine whether the number of duplicates is more than k.

a.  When this condition is true, it means that the algorithm has found the 

solution because the kth position is contained in the duplicates (it’s the 

pivot number).

b.  When this condition isn’t true, remove the number of duplicates from k and 

apply the result recursively to the right side, which must contain the value of 

the kth position.

Now that you understand the process, you can look at some code. The following 

example shows how to implement a Quickselect algorithm.

def quickselect(series, k):

    pivot = choice(series)

    left, right = list(),list()

    for item in series:

        if item < pivot:

            left.append(item)

        if item > pivot:

            right.append(item)

    length_left = len(left)

    if length_left > k:

        return quickselect(left, k)

    k -= length_left

    duplicates = len(series) - (length_left 

+ len(right))

    if duplicates > k:

        return float(pivot)

    k -= duplicates

---

CHAPTER 17