QuickSort depending on number of elements in array

Question

I've done already a quicksort using the median of three element. Now I want to do a task where if the number of ele in array is lower than 1000 it uses my median of three otherwise the pivot is chosen to be the median of 21 equally spaced elements within of the considered subset Here is the median of three:

def quickSort(ele, ascending = True):
    quicksorthelp(ele, 0, len(ele), ascending)


def mediana(ele, primeiro, ultimo):
        mid = (primeiro + ultimo - 1) // 2
        a = ele[primeiro]
        b = ele[mid]
        c = ele[ultimo - 1]
        if a <= b <= c:
            return b, mid
        if c <= b <= a:
            return b, mid
        if a <= c <= b:
            return c, ultimo - 1
        if b <= c <= a:
            return c, ultimo - 1
        return a, primeiro

def quicksorthelp(ele, primeiro, ultimo, ascending = True):
    result = 0
    if primeiro < ultimo:
        pivot_location, result = Partition(ele, primeiro, ultimo, ascending)
        result += quicksorthelp(ele, primeiro, pivot_location, ascending)
        result += quicksorthelp(ele, pivot_location + 1, ultimo, ascending)
    return result


def Partition(ele, primeiro, ultimo, ascending = True):
    result = 0
    pivot, pidx = mediana(ele, primeiro, ultimo)
    ele[primeiro], ele[pidx] = ele[pidx], ele[primeiro]
    i = primeiro + 1
    for j in range(primeiro + 1, ultimo, 1):
        result += 1
        if (ascending and ele[j] < pivot) or (not ascending and ele[j] > pivot):
            ele[i], ele[j] = ele[j], ele[i]
            i += 1
    ele[primeiro], ele[i - 1] = ele[i - 1], ele[primeiro]
    return i - 1, result

arr = []
tam = int(input(""))

for i in range(tam):
    ele = int(input(""))
    arr.append(ele)

quickSort(arr, True)
for tam in arr:
    print(tam)

Please update your question with the code for the median of 21. — quamrana, Oct 30 '22 at 19:42
@quamrana I need help with that! That is what I'm saying sorry to be misleading — André Cunha, Oct 30 '22 at 19:50
Ok, but you could at least write the code that calls your other function and the function definition, even if it does nothing. — quamrana, Oct 30 '22 at 19:55
Also, FYI, a link about choosing [evenly spaced elements](https://stackoverflow.com/questions/9873626/choose-m-evenly-spaced-elements-from-a-sequence-of-length-n) and also finding [median](https://stackoverflow.com/questions/24101524/finding-median-of-list-in-python) — quamrana, Oct 30 '22 at 20:11

score 0 · Answer 1 · answered Oct 31 '22 at 14:48

Example code for median of 3 medians of 3. Med3 of 3 sorts a[lo], a[md], a[hi].

Med9(a, lo, hi)
{
    md = lo + (hi - lo) / 2
    d = (hi - lo + 1) / 8;
    Med3(a, lo, lo + d, lo + 2 * d);
    Med3(a, md - d, md, md + d);
    Med3(a, hi - 2 * d, hi - d, hi);
    Med3(a, lo + d, md, hi - d);
    return a[md];
}

21 would be awkward, but 27 could be implemented with 3 calls to Med9.

QuickSort depending on number of elements in array

1 Answers1