Улучшение алгоритма сортировки выбора? - PullRequest
Новая
       38

Улучшение алгоритма сортировки выбора?

0 голосов
/ 12 июня 2018

Я новый студент CS.Прямо сейчас я изучаю введение в программирование.Я изучал Алгоритм сортировки выбора, и я думаю, что внесение этого изменения в сортировку выбора сделает его более эффективным, это правда или я что-то упустил ??изменение вместо вызова функции подкачки каждый раз, даже когда в массив не вносятся изменения, мы можем добавить логическую переменную changeMade и использовать ее для вызова функции только тогда, когда в массив внесены изменения.Пожалуйста, поправьте меня, если я ошибаюсь 

Declare Integer startScan, i, minValue
Declare Integer minIndex


//the boolean variable
//that could make algorithim
//more efficient 
Declare Boolean changemade

//Declare the array and Declare it is size
//and initialize it
Constant Integer SIZE = 5
Declare Integer array[SIZE]=1, 4, 8, 2, 5

For StartScan = 0 To SIZE-2
    set changeMade = False
    set array[startScan]= minValue
    For i= startScan+1 To SIZE-1
        If array[i]<minValue Then
            set minValue=array[i]
            set minIndex= i
            set changeMade=True //the modification 
        End If
    End For  
    If ChangeMade = True Then
    call swap(array[minIndex], array[startScan])
End For

Module swap(Integer Ref a, Integer Ref b)
    Declare Integer temp
    set temp = a
    set a = b
    set b = temp
End Module

Ответы [ 2 ]

0 голосов
/ 12 июня 2018

Это звучит как ложная хорошая идея.

Эта эвристика эффективна для элементов, которые уже находятся в правильной позиции.

Предположим, что их 10%, что можно считать оптимистичным,При сортировке N элементов вы сэкономите 0,1 N перестановок, но добавите к флагу большое количество назначений (до N 2/2!) И N тестов флага (условные инструкции очень медленные).

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

Конечно, лучше сбросить флаг и протестировать minIndex != startScan, но даже в этом случаене уверены, что избежание свопа уравновесит дополнительные сравнения.

0 голосов
/ 12 июня 2018

Такие операции, как своп, практически игнорируются при расчете сложности.

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

В качестве примера ссортировка выбора: когда вы учитываете все затраты оператора, вы получаете функцию f (n) = an2 + bn + c (a, b и c являются константами и зависят от архитектуры машины).Здесь доминирующим термином является an2.Так мы можем сказать, Временная сложность селекционной сортировки O (an2). Мы также игнорируем коэффициент ведущих слагаемых a, так как a не меняет скорость роста.

Читали ли вы об асимптотике?анализ и обозначения, такие как тэта, омега, большой О. Посмотрите на них, это поможет вам получить ответ на свой вопрос.

...