сортировка выбора до z-й наивысшей позиции python

Я пытаюсь реализовать алгоритм сортировки выбором для сортировки несортированного списка/массива, вот что я получил на данный момент:

list1 = [14,3,2,21,23,12,3,4]#unsorted array
z = 3
for i in range(len(list1)):
    for j in range(i, len(list1)):
        if list1[i] < list1[j]:     
            list1[i], list1[j] = list1[j], list1[i]

print(list1)

Проблема, с которой я сталкиваюсь, состоит в том, чтобы получить самые высокие предметы z. т.е. напечатать самый высокий элемент до индекса z

Итак, следует напечатать:

[23,21,14]

Он должен возвращать количество выполненных сравнений элементов (но должен быть алгоритмом сортировки выбором). И не должен делать больше сравнений, чем нужно (должен остановить алгоритм, как только будет найден z-й самый высокий элемент)

обновление: я попытался настроить интерактивную реализацию Python... Я просто не могу понять это

это то, что у меня есть

def selectionSort(alist, k):
    count = 0
    while count < k:
        for fillslot in range(len(alist)-1,0,-1):
            print(count)
            count += 1
            positionOfMax = 0
            for location in range(1,fillslot+1):
                if alist[location] < alist[positionOfMax]:
                    positionOfMax = location

            temp = alist[fillslot]
            alist[fillslot] = alist[positionOfMax]
            alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist , 3)
print(alist)

Это печатает:

0
1
2
3 # should it not stop here since count is less than k?
4
5
6
7
[93, 77, 55, 54, 44, 31, 26, 20, 17]

python sorting algorithm selection-sort
person snuffles101    schedule 19.10.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward 

import itertools

def limitedInsertionSort(L, z):
    comps = 0
    if z > len(L):
        raise ValueError("List too small")
    for i,j in itertools.product(range(z), range(len(L))):
        if L[i] < L[j]:
            L[i], L[j] = L[j], L[i]
        comps += 1
    return comps

Но, конечно, поскольку вы заботитесь только об увеличении компов:

def countComps(L, z):
    if z > len(L):
        raise ValueError("List too small")
    comps = 0
    for i,j in itertools.product(range(z), range(len(L))):
        comps += 1
    return comps

Но затем, поскольку вы знаете, сколько раз вы увеличиваете comps, вы можете просто выполнить умножение:

def countComps(L, z):
    if z > len(L):
        raise ValueError("List too small")
    comps = z*len(L)
    return comps
person inspectorG4dget    schedule 19.10.2015

arrow_upward
0
arrow_downward

Я нашел эту реализацию Python

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheSelectionSort.html

Для людей, которые не очень хорошо осведомлены об алгоритме, он не только сравнивает, но и помещает самый большой элемент на последнее место, второй по величине элемент на второе по величине место. Таким образом, мы можем увеличить скорость алгоритма сортировки.

Надеюсь, это может помочь.

person Pappu Jha    schedule 19.10.2015
comment
Итак, используя интерактивный пример Python, могу ли я просто поставить цикл while перед первым циклом for и иметь счет в цикле for? тогда скажите, пока это количество меньше, чем значение z сделать алгоритм? - person snuffles101; 19.10.2015