def find_kthbest(k, data, left, right, statistics):
    pivotindex = random.randint(left, right)

    # flytta pivot till kanten
    data[pivotindex], data[right] = data[right], data[pivotindex]

    # damerna först med avseende på pivotdata
    pivot = data[right]
    pivotmid = partition(data, left, right, pivot, statistics)

    # flytta tillbaka pivot
    data[pivotmid], pivot = pivot, data[pivotmid]

    statistics.nr_comparisons += 1
    if pivotmid == k:
        return data[pivotmid]
    elif k < pivotmid:
        return find_kthbest(k, data, left, pivotmid - 1, statistics)
    else:
        return find_kthbest(k, data, pivotmid + 1, right, statistics)


def partition(data, left, right, pivot, statistics):
    while True:
        #left += 1 överflödig

        while data[left] > pivot:
            statistics.nr_comparisons += 1
            left += 1

        right -= 1    # hoppa över pivot

        while right != 0 and data[right] < pivot:
            statistics.nr_comparisons += 1
            right -= 1

        data[left], data[right] = data[right], data[left]

        statistics.nr_comparisons += 1
        if left >= right:
            break

    data[left], data[right] = data[right], data[left]       # Varför finns denna rad?

    return left