Реализация алгоритма сортировки вставкой Insertion Sort

uran238 · 8 Ноя 2020

Доброго времени!
Пытаюсь реализовать на Autoit алгоритм сортировки вставкой. Общий смысл алгоритма мне более-менее ясен, но с технической частью не могу разобраться. В книге "Кормена - Алгоритмы построение и анализ" описан псевдокод по которому собственно и пытаюсь понять техническую сторону данного алгоритма. То что пробовал:

Код:

#include <Array.au3>
Global $aArraySortable[7] = [15, 1, 6, 7, 3, 74]
AAR()
Func AAR()
    For $i = 0 To 5
        $aKey = $aArraySortable[$i]
        $J = $i - 1
        While $aJ >= 0 And $aKey < $aArraySortable[$aJ]
            $J -= 1
            $aArraySortable[$J + 1] = $aKey
        WEnd
    Next
    Return $aArraySortable
EndFunc   ;==>AAR
_ArrayDisplay($aArraySortable)

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

IMStrelcov · 8 Ноя 2020

Вот мои наработки, какие то, по сортировкам.
Баловался когда то, уже и не вспомню что там к чему (вникать нет времени).
Может что и найдете для себя, на свежую голову.

Код:

#NoTrayIcon
#include <Array.au3>

$iSize = 0
$iCirc = 1

$aArray = FileRead('FolderListBig.txt')
$aArray = StringSplit($aArray, @CRLF, 3)


$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    _ArraySort($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('Array'&@TAB&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    QuickInsSort_($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('QuickIns'&@TAB&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    QuickInsRecSort_($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('QuickInsRec'&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    _ArraySort($aData, 0, 0, 0, 0, 1)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('ArrayDual'&@TAB&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    QuickInsRecDualSort_($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('QuickInsRecDual'&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    QuickSort_($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('Quick'&@TAB&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    SmartQuickInsRecSort_($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('Smart2'&@TAB&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

$iTimeAve = 0
For $iA = 1 To $iCirc
    $aData = $aArray
    $iTimer = TimerInit()
    SmartSort_($aData)
    $iTimer = TimerDiff($iTimer)
    $iTimeAve += $iTimer
Next
ConsoleWrite('Smart'&@TAB&@TAB&@TAB&'Random'&@TAB&$iSize&@TAB&@TAB&Round($iTimeAve/$iA,3)&@TAB&Round($iTimeAve,3)&@CRLF)

ConsoleWrite(@CRLF)

Exit

Func SmartSort_(ByRef $_aArray, $_iBegin = 0, $_iEnd = -1, $_iNum = 0)
    If $_iBegin < 0 Then $_iBegin = 0
    If $_iEnd < 0 Then $_iEnd = UBound($_aArray) -1
    If $_iEnd <= $_iBegin Then Return
    SmartQuickInsRecSort_($_aArray, $_iBegin, $_iEnd, $_iNum)
    Local $_sLeft, $_sRight, $_iLeft = $_iBegin, $_iRight = $_iBegin +1
    $_sLeft = StringGetWord_($_aArray[$_iLeft], $_iNum)
    While $_iRight < $_iEnd
        $_sRight = StringGetWord_($_aArray[$_iRight], $_iNum)
        If $_sRight <> $_sLeft Then
            If $_iLeft < ($_iRight -1) Then
                SmartSort_($_aArray, $_iLeft, $_iRight -1, $_iNum +1)
            EndIf
            $_iLeft = $_iRight
            $_sLeft = $_sRight
        EndIf
        $_iRight += 1
    WEnd
    If $_iLeft < ($_iRight -1) Then
        SmartSort_($_aArray, $_iLeft, $_iRight -1, $_iNum +1)
    EndIf
EndFunc

Func SmartQuickInsRecSort_(ByRef $_aArray, $_iBegin = 0, $_iEnd = -1, $_iNum = 0)
    If $_iBegin < 0 Then $_iBegin = 0
    If $_iEnd < 0 Then $_iEnd = UBound($_aArray) -1
    If $_iEnd <= $_iBegin Then Return
    Local $_sBuffer, $_iLeft = $_iBegin, $_iRight = $_iEnd
    Local $_sPivot = $_aArray[Int(($_iBegin +$_iEnd) /2)]
    $_sPivot = StringGetWord_($_sPivot, $_iNum)
    Local $_sPivotType = StringGetType_($_sPivot)
    While $_iLeft <= $_iRight
        While 1
            $_sBuffer = StringGetWord_($_aArray[$_iLeft], $_iNum)
            If StringCompare_($_sPivot, $_sBuffer, $_sPivotType) <= 0 Then ExitLoop
            $_iLeft += 1
        WEnd
        While 1
            $_sBuffer = StringGetWord_($_aArray[$_iRight], $_iNum)
            If StringCompare_($_sPivot, $_sBuffer, $_sPivotType) >= 0 Then ExitLoop
            $_iRight -= 1
        WEnd
        If $_iLeft <= $_iRight Then
            $_sBuffer = $_aArray[$_iLeft]
            $_aArray[$_iLeft] = $_aArray[$_iRight]
            $_aArray[$_iRight] = $_sBuffer
            $_iLeft += 1
            $_iRight -= 1
        EndIf
    WEnd
    If $_iBegin < $_iRight Then SmartQuickInsRecSort_($_aArray, $_iBegin, $_iRight, $_iNum)
    If $_iLeft < $_iEnd Then SmartQuickInsRecSort_($_aArray, $_iLeft, $_iEnd, $_iNum)
EndFunc

Func QuickSort_(ByRef $_aArray, $_iBegin = 0, $_iEnd = -1)
    If $_iBegin < 0 Then $_iBegin = 0
    If $_iEnd < 0 Then $_iEnd = UBound($_aArray) -1
    If $_iEnd <= $_iBegin Then Return
    Local $_sBuffer, $_iLeft = $_iBegin, $_iRight = $_iEnd
    Local $_sPivot = $_aArray[Int(($_iBegin +$_iEnd) /2)]
    While $_iLeft <= $_iRight
        While $_aArray[$_iLeft] < $_sPivot
            $_iLeft += 1
        WEnd
        While $_aArray[$_iRight] > $_sPivot
            $_iRight -= 1
        WEnd
        If $_iLeft <= $_iRight Then
            $_sBuffer = $_aArray[$_iLeft]
            $_aArray[$_iLeft] = $_aArray[$_iRight]
            $_aArray[$_iRight] = $_sBuffer
            $_iLeft += 1
            $_iRight -= 1
        EndIf
    WEnd
    If $_iBegin < $_iRight Then QuickSort_($_aArray, $_iBegin, $_iRight)
    If $_iLeft < $_iEnd Then QuickSort_($_aArray, $_iLeft, $_iEnd)
EndFunc

Func QuickInsRecDualSort_(ByRef $_aArray, $_iBegin = 0, $_iEnd = -1, $_iPos = 1)
    If $_iBegin < 0 Then $_iBegin = 0
    If $_iEnd < 0 Then $_iEnd = UBound($_aArray) -1
    If $_iEnd <= $_iBegin Then Return
    Local $_sBuff, $_iLeft, $_iRight
    Local $_sLeftChar, $_sRightChar, $_sLeftType, $_sRightType
    If ($_iEnd - $_iBegin) < 20 Then
        For $_iRight = $_iBegin +1 To $_iEnd
            $_sBuff = $_aArray[$_iRight]
            For $_iLeft = $_iRight -1 To $_iBegin Step -1
                If $_sBuff <= $_aArray[$_iLeft] Then ExitLoop
                $_aArray[$_iLeft +1] = $_aArray[$_iLeft]
            Next
            $_aArray[$_iLeft +1] = $_sBuff
        Next
    Else
        Local $_sPivot = $_aArray[Int(($_iBegin +$_iEnd) /2)]
        Local $_iLeftBegin = $_iBegin
        Local $_iLeftEnd = $_iBegin
        Local $_iRightBegin = $_iEnd
        Local $_iRightEnd = $_iEnd
        Do
            Do
                If $_sPivot < $_aArray[$_iLeftEnd] Then
                    ExitLoop
                ElseIf $_sPivot = $_aArray[$_iLeftEnd] Then
                    $_sBuff = $_aArray[$_iLeftBegin]
                    $_aArray[$_iLeftBegin] = $_aArray[$_iLeftEnd]
                    $_aArray[$_iLeftEnd] = $_sBuff
                    $_iLeftBegin += 1
                EndIf
                $_iLeftEnd += 1
            Until $_iLeftEnd > $_iRightBegin
            Do
                If $_sPivot > $_aArray[$_iRightBegin] Then
                    ExitLoop
                ElseIf $_sPivot = $_aArray[$_iRightBegin] Then
                    $_sBuff = $_aArray[$_iRightEnd]
                    $_aArray[$_iRightEnd] = $_aArray[$_iRightBegin]
                    $_aArray[$_iRightBegin] = $_sBuff
                    $_iRightEnd -= 1
                EndIf
                $_iRightBegin -= 1
            Until $_iLeftEnd > $_iRightBegin
            If $_iLeftEnd <= $_iRightBegin Then
                $_sBuff = $_aArray[$_iLeftEnd]
                $_aArray[$_iLeftEnd] = $_aArray[$_iRightBegin]
                $_aArray[$_iRightBegin] = $_sBuff
                $_iLeftEnd += 1
                $_iRightBegin -= 1
            EndIf
        Until $_iLeftEnd > $_iRightBegin
        If $_iLeftBegin < $_iLeftEnd Then
            If $_iLeftBegin > $_iBegin Then
                Do
                    $_iLeftBegin -= 1
                    $_iLeftEnd -= 1
                    $_sBuff = $_aArray[$_iLeftEnd]
                    $_aArray[$_iLeftEnd] = $_aArray[$_iLeftBegin]
                    $_aArray[$_iLeftBegin] = $_sBuff
                Until $_iBegin >= $_iLeftBegin
            EndIf
            QuickInsRecDualSort_($_aArray, $_iLeftBegin, $_iLeftEnd -1)
        EndIf
        If $_iRightBegin < $_iRightEnd Then
            If $_iRightEnd < $_iEnd Then
                Do
                    $_iRightBegin += 1
                    $_iRightEnd += 1
                    $_sBuff = $_aArray[$_iRightEnd]
                    $_aArray[$_iRightEnd] = $_aArray[$_iRightBegin]
                    $_aArray[$_iRightBegin] = $_sBuff
                Until $_iRightEnd >= $_iEnd
            EndIf
            QuickInsRecDualSort_($_aArray, $_iRightBegin +1, $_iRightEnd)
        EndIf
        If $_iLeftEnd > $_iRightBegin Then
            QuickInsRecDualSort_($_aArray, $_iLeftEnd, $_iRightBegin, $_iPos +1)
        EndIf
    EndIf
EndFunc

Func QuickInsSort_(ByRef $_aArray, $_iStart = 0, $_iEnd = -1)
    If $_iStart < 0 Then $_iStart = 0
    If $_iEnd < 0 Then $_iEnd = UBound($_aArray) -1
    If $_iEnd <= $_iStart Then Return
    Local $_sBuff, $_iLeft, $_iRight, $_sPivot
    Local $_aStack[2][2] = [[1, 0], [$_iStart, $_iEnd]]
    Do
        $_iStart = $_aStack[$_aStack[0][0]][0]
        $_iEnd = $_aStack[$_aStack[0][0]][1]
        ReDim $_aStack[$_aStack[0][0]][2]
        $_aStack[0][0] -= 1
        If ($_iEnd - $_iStart) < 20 Then
            For $_Right = $_iStart +1 To $_iEnd
                $_sBuff = $_aArray[$_Right]
                For $_iLeft = $_Right -1 To $_iStart Step -1
                    If $_sBuff >= $_aArray[$_iLeft] Then ExitLoop
                    $_aArray[$_iLeft +1] = $_aArray[$_iLeft]
                Next
                $_aArray[$_iLeft +1] = $_sBuff
            Next
        Else
            $_sPivot = $_aArray[Int(($_iStart +$_iEnd) /2)]
            $_iLeft = $_iStart
            $_iRight = $_iEnd
            Do
                While ($_aArray[$_iLeft] < $_sPivot)
                    $_iLeft += 1
                WEnd
                While ($_aArray[$_iRight] > $_sPivot)
                    $_iRight -= 1
                WEnd
                If $_iLeft <= $_iRight Then
                    $_sBuff = $_aArray[$_iLeft]
                    $_aArray[$_iLeft] = $_aArray[$_iRight]
                    $_aArray[$_iRight] = $_sBuff
                    $_iLeft += 1
                    $_iRight -= 1
                EndIf
            Until $_iLeft > $_iRight
            $_aStack[0][0] += 2
            ReDim $_aStack[$_aStack[0][0] +1][2]
            $_aStack[$_aStack[0][0] -1][0] = $_iStart
            $_aStack[$_aStack[0][0] -1][1] = $_iRight
            $_aStack[$_aStack[0][0]][0] = $_iLeft
            $_aStack[$_aStack[0][0]][1] = $_iEnd
        EndIf
    Until $_aStack[0][0] < 1
EndFunc

Func QuickInsRecSort_(ByRef $_aArray, $_iStart = 0, $_iEnd = -1)
    If $_iStart < 0 Then $_iStart = 0
    If $_iEnd < 0 Then $_iEnd = UBound($_aArray) -1
    If $_iEnd <= $_iStart Then Return
    Local $_sBuff, $_iLeft, $_iRight
    If ($_iEnd - $_iStart) < 20 Then
        For $_Right = $_iStart +1 To $_iEnd
            $_sBuff = $_aArray[$_Right]
            For $_iLeft = $_Right -1 To $_iStart Step -1
                If $_sBuff >= $_aArray[$_iLeft] Then ExitLoop
                $_aArray[$_iLeft +1] = $_aArray[$_iLeft]
            Next
            $_aArray[$_iLeft +1] = $_sBuff
        Next
    Else
        Local $_sPivot = $_aArray[Int(($_iStart +$_iEnd) /2)]
        $_iLeft = $_iStart
        $_iRight = $_iEnd
        Do
            While ($_aArray[$_iLeft] < $_sPivot)
                $_iLeft += 1
            WEnd
            While ($_aArray[$_iRight] > $_sPivot)
                $_iRight -= 1
            WEnd
            If $_iLeft <= $_iRight Then
                $_sBuff = $_aArray[$_iLeft]
                $_aArray[$_iLeft] = $_aArray[$_iRight]
                $_aArray[$_iRight] = $_sBuff
                $_iLeft += 1
                $_iRight -= 1
            EndIf
        Until $_iLeft > $_iRight
        QuickInsRecSort_($_aArray, $_iStart, $_iRight)
        QuickInsRecSort_($_aArray, $_iLeft, $_iEnd)
    EndIf
EndFunc

Func MergeInsSort_(ByRef $_aArray, $_iStart = 0, $_iEnd = -1)
    If $_iEnd < 0 Then
        $_iEnd = UBound($_aArray) -1
    EndIf
    Local $_iSize = ($_iEnd -$_iStart) +1
    If ($_iEnd - $_iStart) < 20 Then
        For $_Right = $_iStart +1 To $_iEnd
            $_sBuff = $_aArray[$_Right]
            For $_iLeft = $_Right -1 To $_iStart Step -1
                If $_sBuff >= $_aArray[$_iLeft] Then ExitLoop
                $_aArray[$_iLeft +1] = $_aArray[$_iLeft]
            Next
            $_aArray[$_iLeft +1] = $_sBuff
        Next
    Else
        Local $_iPivot = Int($_iSize /2)
        Local $_iLeftStart = $_iStart
        Local $_iLeftEnd = $_iStart +$_iPivot
        Local $_iRightStart = $_iLeftEnd +1
        Local $_iRightEnd = $_iEnd
        MergeInsSort_($_aArray, $_iLeftStart, $_iLeftEnd)
        MergeInsSort_($_aArray, $_iRightStart, $_iRightEnd)
        Local $_iLeftSize = ($_iLeftEnd -$_iLeftStart) +1
        Local $_iRightSize = ($_iRightEnd -$_iRightStart) +1
        Local $_iA, $_aBuff[$_iRightSize]
        For $_iA = 0 To $_iRightSize -1
            $_aBuff[$_iA] = $_aArray[$_iRightStart +$_iA]
        Next
        Do
            If $_aArray[$_iLeftEnd] >  $_aBuff[$_iRightSize -1] Then
                $_aArray[$_iRightEnd] = $_aArray[$_iLeftEnd]
                $_iLeftEnd -= 1
            Else
                $_aArray[$_iRightEnd] = $_aBuff[$_iRightSize -1]
                $_iRightSize -= 1
            EndIf
            $_iRightEnd -= 1
        Until ($_iRightSize < 1) Or ($_iLeftStart > $_iLeftEnd)
        If $_iRightSize > 0 Then
            For $_iA = 0 To $_iRightSize -1
                $_aArray[$_iLeftStart +$_iA] = $_aBuff[$_iA]
            Next
        EndIf
    EndIf
EndFunc

;ШЕЛЛА
Func ShellSort_(ByRef $_aArray, $_iStart = 0, $_iEnd = 0)
    If $_iEnd < 1 Then
        $_iEnd = UBound($_aArray) -1
    EndIf
    Local $_sBuff, $_iLeft, $_Right
    Local $_iStep = $_iEnd -$_iStart
    Do
        $_iStep = Int($_iStep/2)
        For $_Right = $_iStart +$_iStep To $_iEnd
            $_sBuff = $_aArray[$_Right]
            For $_iLeft = $_Right -$_iStep To $_iStart Step -$_iStep
                If $_sBuff >= $_aArray[$_iLeft] Then ExitLoop
                $_aArray[$_iLeft +$_iStep] = $_aArray[$_iLeft]
            Next
            $_aArray[$_iLeft +$_iStep] = $_sBuff
        Next
    Until $_iStep < 2
EndFunc

;СЛИЯНИЕМ
Func MergeSort_(ByRef $_aArray, $_iStart = 0, $_iEnd = -1)
    If $_iEnd < 0 Then
        $_iEnd = UBound($_aArray) -1
    EndIf
    Local $_iSize = ($_iEnd -$_iStart) +1
    Switch $_iSize
        Case 1
            Return
        Case 2
            If $_aArray[$_iStart] > $_aArray[$_iEnd] Then
                $_sBuff = $_aArray[$_iEnd]
                $_aArray[$_iEnd] = $_aArray[$_iStart]
                $_aArray[$_iStart] = $_sBuff
            EndIf
        Case Else
            Local $_iPivot = Int($_iSize /2)
            Local $_iLeftStart = $_iStart
            Local $_iLeftEnd = $_iStart +$_iPivot
            Local $_iRightStart = $_iLeftEnd +1
            Local $_iRightEnd = $_iEnd
            MergeSort_($_aArray, $_iLeftStart, $_iLeftEnd)
            MergeSort_($_aArray, $_iRightStart, $_iRightEnd)
            Local $_iLeftSize = ($_iLeftEnd -$_iLeftStart) +1
            Local $_iRightSize = ($_iRightEnd -$_iRightStart) +1
            Local $_iA, $_aBuff[$_iRightSize]
            For $_iA = 0 To $_iRightSize -1
                $_aBuff[$_iA] = $_aArray[$_iRightStart +$_iA]
            Next
            Do
                If $_aArray[$_iLeftEnd] >  $_aBuff[$_iRightSize -1] Then
                    $_aArray[$_iRightEnd] = $_aArray[$_iLeftEnd]
                    $_iLeftEnd -= 1
                Else
                    $_aArray[$_iRightEnd] = $_aBuff[$_iRightSize -1]
                    $_iRightSize -= 1
                EndIf
                $_iRightEnd -= 1
            Until ($_iRightSize < 1) Or ($_iLeftStart > $_iLeftEnd)
            If $_iRightSize > 0 Then
                For $_iA = 0 To $_iRightSize -1
                    $_aArray[$_iLeftStart +$_iA] = $_aBuff[$_iA]
                Next
            EndIf
    EndSwitch
EndFunc

;ВСТАВКАМИ
Func InsertionSort_(ByRef $_aArray, $_iStart = 0, $_iEnd = 0)
    If $_iEnd < 1 Then
        $_iEnd = UBound($_aArray) -1
    EndIf
    Local $_sBuff, $_iLeft, $_Right
    For $_Right = $_iStart +1 To $_iEnd
        $_sBuff = $_aArray[$_Right]
        For $_iLeft = $_Right -1 To $_iStart Step -1
            If $_sBuff >= $_aArray[$_iLeft] Then ExitLoop
            $_aArray[$_iLeft +1] = $_aArray[$_iLeft]
        Next
        $_aArray[$_iLeft +1] = $_sBuff
    Next
EndFunc

Func StringGetWord_(ByRef $_sStr, $_iNum = 0)
    Local $_sResult = StringRegExpReplace($_sStr, '(?:[A-zА-яЁё]{1,}|[0-9]{1,}|[^0-9A-zА-яЁё]{1,}){'&$_iNum&'}([A-zА-яЁё]{1,}|[0-9]{1,}|[^0-9A-zА-яЁё]{1,})?(?:[A-zА-яЁё]{1,}|[0-9]{1,}|[^0-9A-zА-яЁё]{1,}){0,}', '$1', 1)
    If @extended Then
        Return $_sResult
    EndIf
    Return SetError(1, 0, '')
EndFunc

Func StringGetType_(ByRef $_sStr)
    If StringIsAlpha($_sStr) Then Return 2
    If StringIsDigit($_sStr) Then Return 1
    Return 0
EndFunc

Func StringCompare_(ByRef $_sLeftChar, ByRef $_sRightChar, $_sLeftType = -1)
    If $_sLeftType < 0 Then $_sLeftType = StringGetType_($_sLeftChar)
    Local $_sRightType = StringGetType_($_sRightChar)
    Switch $_sLeftType
        Case 0
            If $_sRightType > 0 Then Return -1
            Return StringCompare($_sLeftChar, $_sRightChar)
        Case 1
            If $_sRightType < 1 Then Return 1
            If $_sRightType > 1 Then Return -1
            If Number($_sLeftChar) > Number($_sRightChar) Then Return 1
            If Number($_sLeftChar) < Number($_sRightChar) Then Return -1
            Return 0
        Case 2
            If $_sRightType < 2 Then Return 1
            Return StringCompare($_sLeftChar, $_sRightChar)
    EndSwitch
EndFunc

xXx · 8 Ноя 2020

uran238 сказал(а):
пытаюсь понять техническую сторону данного алгоритма.

Вот, почти как в книге (только ее увидел, надо почитать), за исключением того что массивы в Autoit начинаются с индекса [0].

Код:

#include <Array.au3>
Global $aA[6] = [16, 15, 6, 7, 74, 3]

For $j = 1 To UBound($aA) - 1
    $iKey = $aA[$j]
    $i = $j - 1
    While ($i >= 0 And $aA[$i] > $iKey)
        $aA[$i + 1] = $aA[$i]
        $i = $i - 1
        $aA[$i + 1] = $iKey
    WEnd
Next

_ArrayDisplay($aA)

uran238 · 9 Ноя 2020

Спасибо. xXx, можете пояснить назначение 8,9,10 строк?

xXx · 9 Ноя 2020

uran238 сказал(а):
можете пояснить

Немного подправил цикл While...WEnd

Код:

#include <Array.au3>
Global $aA[6] = [16, 15, 6, 7, 74, 3]

For $j = 1 To UBound($aA) - 1
    ; Берем следующее по порядку значение и сохраняем вне массива, т.е. в независимой переменной $iKey.
    ; Это текущее значение которому необходимо будет найти новое место в массиве.
    ; (При первом проходе цикла For...Next равно [1])
    $iKey = $aA[$j]
    ; (Массив сортируется в данном случае сверху вниз => подразумевается то, что сверху текущей взятой на
    ; рассмотрение ячейки уже все отсортировано между собой, а что снизу еще предстоит обработать.)
    $i = $j - 1 ; $i - это индекс предыдущей ячейки массива (При первом проходе цикла For...Next равно [0])
    ; Цикл While...WEnd - сравнение $iKey с уже отсортированными значениями массива по порядку снизу вверх,
    ; т.е. от последнего (отсортированного) к первому.
    ; Цикл будет продолжаться до тех пор, пока не встретится значение больше или равно $iKey
    ; или индекс $i не станет меньше 0 - т.е. после сравнивания $iKey с самой первой ячейкой массива.
    While ($i >= 0 And $aA[$i] > $iKey)
        ; Если $iKey меньше значению текущей сравниваемой ячейки ($aA[$i]), то
        ; присваиваем это значение ячейке с индексом больше на 1, т.е. "смещаем" значение по массиву вниз.
        ; При этом старое значение ячейки $aA[$i + 1] никуда не девается...
        $aA[$i + 1] = $aA[$i]
        ; ... при первом и последующих проходах цикла While...WEnd оно всегда будет равно $iKey
        $aA[$i] = $iKey ; при следующем проходе обращение к значению текущей переменной $aA[$i]
        ; будет выглядеть как $aA[$i + 1] потому что...
        $i = $i - 1 ; Уменьшаем $i на 1 и отправляемся на следующий проход цикла While...WEnd
    WEnd
Next

_ArrayDisplay($aA)

uran238 · 9 Ноя 2020

xXx спасибо!

Автор темы	Похожие темы	Форум	Ответы	Дата
V	Существует лив autoIt реализация SQLite функции Count(*)?	Общие вопросы по AutoIt	1	1 Сен 2018
S	[Автоматизация] [Вопрос] [Теория] Поиск пикселя по зонам. Правильная реализация	Разработка ботов	2	20 Мар 2017
	Реализация демонстрации экрана	Общие вопросы по AutoIt	1	19 Апр 2016
	Реализация демонстрации экрана	Общие вопросы по AutoIt	0	19 Апр 2016
	Реализация предпросмотра изображений в ListView	GUI - Графический интерфейс пользователя	20	26 Фев 2016

Поиск

Поиск

Реализация алгоритма сортировки вставкой Insertion Sort

uran238

Новичок

IMStrelcov

CTPEJIbLLOB

xXx

╚{■_■}╗

uran238

Новичок

xXx

╚{■_■}╗

uran238

Новичок