Является ли количество вызовов функции свопинга и количество свопов, выполненных при сортировке выбором, одним и тем же?

Я знаю, что для n элементов в сортировке выбором:

В лучшем случае выполнен 1 обмен. В худшем случае: выполнено n-1 обменов. Средние случаи: выполнено (n-1)/2 обмена.

Итак, если бы я сказал, что количество вызовов функции подкачки равно количеству подкачек, выполненных в 3 разных случаях, был бы я прав?


c++ sorting algorithm data-structures selection-sort
person GlitchInTheMatrix    schedule 28.05.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Ну, во-первых, я не уверен, почему минимальное количество свопов должно быть равно единице. Для уже отсортированного массива он должен быть равен нулю.

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

Другими словами, что-то вроде (псевдокод):

def selSort(items):
    # This position is the ever-moving border between
    # 'sorted on left' and 'unsorted from here to end'.

    for position in 0 thru items.length - 2 inclusive:
        # Scan all unsorted, finding the lowest (starting
        # default is the first unsorted).

        lowestUnsorted = position
        for checkPos = position + 1 thru items.length inclusive:
            # If lower than current lowest, replace.

            if items[checkPos] < items[lowestUnsoreted]:
                lowestUnsorted = checkPos

        # Swap if need be.

        if lowestUnsorted != position:
            temp = items[position]
            items[position] = items[lowestUnsorted]
            items[lowestUnsorted] = temp

Но, с точки зрения вашего фактического вопроса, могу поспорить, что это одно и то же. Если ваша функция swap не имеет условного кода, который может не выполнять обмен при определенных обстоятельствах(a), или кода, который каждый раз меняет местами более одного элемента, каждый вызов функции обмена аналогичен обмену.

(a) Вы можете сделать так, чтобы функция подкачки могла быть вызвана независимо от того, находится ли элемент уже в правильном положении, и она просто определяет это и не меняет местами , что-то типа:

void doSwap (Item *item1, Item * item2) {
    if (item1 != item2):
        Item tempItem = *item1;
        *item1 = *item2;
        *item2 = tempItem;
}

В этом случае вызовы функции свопинга могут отличаться от реальных свопов. Но, если честно, эту проверку, вероятно, лучше выполнять на уровне выше (согласно псевдокоду), поскольку вызовы функций, хотя и относительно дешевы, редко обходятся без затрат.

person paxdiablo    schedule 28.05.2020