Одно и то же ли количество вызовов функции подкачки и количество подкачки при сортировке выбора? - PullRequest
Новая
       4

Одно и то же ли количество вызовов функции подкачки и количество подкачки при сортировке выбора?

0 голосов
/ 28 мая 2020

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

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

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

1 Ответ

2 голосов
/ 28 мая 2020

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

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

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

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;
}

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

...