위조 코드의 함수 거품 정렬

거품 정렬은 매우 간단한 정렬 알고리즘으로 목록에서 교체되고 필요에 따라 인접 원소를 교환하여 끝에 도달할 때까지 한다.그리고 목록이 정렬될 때까지 이 과정을 반복합니다.
이 알고리즘은 본질적으로 목록을 두 가지 다른 유형의 데이터로 간주한다.첫 번째는 목록 자체입니다. 이것은 임의의 길이의 그룹입니다.두 번째는 고려된 주어진 항목이 옳고 본질적으로 하나의 원조이다.모든 원조는 단독으로 정렬되어 목록에 다시 삽입된 다음에 다른 원조를 고려한 다음에 목록의 끝에 도달할 때까지 다른 원조를 고려한다.
물론 목록을 통해 전체 정렬을 하는 사람은 드물다.이 알고리즘의 복잡성은 목록이 완전히 정렬될 때까지 계속 실행되어야 한다는 데 있다.가장 간단한 방법은 전체 목록에서 n = list.length회를 완성하는 것이지만 몇 가지 방법으로 최적화할 수 있다.
첫 번째 최적화는 거품이 목록에 정렬되는 작업 방식을 고려해서 찾을 수 있습니다. 한 번에 한 쌍입니다.각 쌍에서 큰 요소는 가장 엄격한 위치로 이동합니다.이것은 비교적 큰 원소가 다음 쌍의 고려에 포함된다는 것을 의미한다.따라서 첫 번째 정렬 후에 우리는 최종 원소가 정확한 위치에 있어야 한다고 확신할 수 있다.이것은 우리가 목록의 두 번째 순환을 시작할 때, 전체 목록이 아닌 n-1개의 요소만 고려해야 한다는 것을 의미한다.두 번째 순환 후에 마지막 두 원소가 정확하게 정렬되면 우리는 고려해야 할 목록을 두 원소로 줄일 수 있다.첫 번째 원조만 고려할 때까지 계속될 겁니다.그래서 첫 번째 최적화는 목록의 모든 순환에서 우리가 정렬해야 하는 목록은 마지막 요소를 생략해서 줄일 수 있다는 것이다.
두 번째 최적화는 이러한 관찰에서 나온다. 최종적으로 거품 정렬 알고리즘이 부여된 많은 목록(대다수가 아니라면)은 자신이 의외로 정렬된 것을 발견할 수 있다.목록은 처음부터 이런 상태일 수도 있고, 원소 하나만 닫을 수도 있습니다. (따라서 목록에서 한 번만 순환하면 됩니다.)우리가 이 목록을 몇 번이나 훑어보았든지 간에, 우리가 그 즐거운 우연한 상태에 도달했을 때, 우리는 비교를 멈추고, 우리의 정렬 목록만 보여줄 수 있다. 이것은 좋은 일이다.인간에게 이것은 상당히 직관적인 일이다. 만약 우리가 목록을 자세히 살펴보고 질서가 있다는 것을 깨닫게 된다면, 우리는 다시는 반복하지 않을 것이다.그러나 우리의 알고리즘은 직각을 어떻게 활용하는지 알려주고 자신을 최적화시켜 작업량을 줄여야 한다.
이 글에서, 나는 '함수' 방법을 사용하여 거품 정렬 알고리즘을 개술할 것이다.그 밖에 이것은'컨트롤 흐름'메커니즘이 아니라 귀속에 의존한다는 것을 의미한다.또한 테스트부터 시작하여 다음부터 시작하겠습니다.

위조 코드:

퀴즈:

expect: bubble-sort (4 2 1 6 3 5) -> [1,2,3,4,5,6]
expect: bubble-sort (1 2 3 4 5 6) -> [1,2,3,4,5,6] // case: already sorted
expect: bubble-sort (1) -> [1] // case: single element should return itself

모듈 데이터 형식:
"tuple"데이터 형식부터 시작합시다. 비교를 위한 단일 쌍으로 전송됩니다.

// tuple -> tuple
define: tuple-sort ( x, y ):
    if ( x < y ): return ( x, y )
    else: return ( y, x )

이것이 바로 짝짓기의 정렬이다.

목록 반복 찾아보기
이제 전체 목록을 어떻게 전달하는지 생각해 봅시다.

// list -> list
define: list-iteration ( list ):
    if ( list.length <= 1 ): return list
    else: list[0,1] =  tuple-sort ( list[0], list[1] )
        list-iteration ( list[1:] )

이것은 교체 목록에 사용되는 간단한 귀속 함수이다.기본적으로 목록에는 하나의 요소만 포함되어 있기 때문에 비교할 원조가 없습니다.비교나 정렬할 수 있는 내용이 없는 '빈' 목록을 포착합니다.이러한 상황에서'list'는 간단하게 되돌아옵니다. 기존 함수 호출을 통해 되돌아오고, 이 목록을 교체된 모든 원조 정렬로 되돌려줍니다.

여러 번 목록 통과:list-iteration 함수는 우리가 목록을 한 번에 통과할 수 있도록 한다.하지만 한 번 통과하면 명단을 정렬하기 어렵다.반대로 모든 요소가 정렬될 때까지 목록을 계속 훑어보아야 한다.
정의상 거품 정렬의 작업 방식 때문에 길이가 i인 목록의 매 교체 l, l-i개의 요소가 정렬된다.다시 말하면 첫 번째 교체 후에 마지막 원소가 정렬된다는 것이다.두 번째 교체 후에 밑에서 두 번째 원소를 정렬하여 유추할 것이다.이것은 모든 원조를 비교할 때 비교적 큰 요소가 두 번째 위치에서 되돌아오기 때문이다. (목록의 끝에 더욱 가깝다.)다음 원조 쌍은 이 비교적 큰 요소를 다시 포함할 것이기 때문에 원조 쌍 중 비교적 큰 원소라면 두 번째로 되돌아갈 것이다.이 과정이 중복될 때, 목록에서 가장 큰 요소는 항상 tuple-sort 함수로 되돌아오는 두 번째 요소로 끝난다.따라서 목록을 완성할 때 최종 tuple-sort 비교가 되돌아오는 최종 요소가 됩니다.사실'buble sort'라는 이름은 여기서 나온 것이다. 모든 과정에서 가장 큰 요소인'buble up'은 목록의 끝까지 이어진다.
이것은 우리에게 전체 목록을 어떻게 정렬하는지에 대한 힌트를 제공했다.list-iteration 함수에서 우리는 목록을 처음부터 끝까지 처리했다.list-sort 함수에서 우리는 상반된 일을 처음부터 끝까지 할 수 있다.

// list -> sorted list
define: list-sort ( list ):
    if ( list.length <= 1 ): return list
    else: list = list-iteration ( list )
        list-sort ( list[:final] )

본질적으로, 이것은 목록의 list-iteration 함수를 호출하지만, 매번 목록의 마지막 요소를 삭제합니다.그리고 단축된 목록을 다음 귀속 호출에 전달합니다.이것은 list-iteration을 실행할 때마다 완전한 목록을 되돌려 주는 것을 제외하고는 시작할 것 같다.만약 우리가 이 모든 목록을 한데 조합한다면, 우리는 정렬 목록을 얻지 않고, 일련의 부분의 정렬 목록을 얻을 수 있을 것이다.우리가 진정으로 원하는 것은 매번 운행하는 마지막 요소이다. (우리는 이 요소가 정렬되었음을 알고 있기 때문이다.)그래서 우리가 필요로 하는 것은 어떤 "지금까지 완성된 일"용기이다.

// list -> sorted list
define: list-sort ( list ):
    local define: list-sort ( list, slist ):
        if ( list.length <= 1 ): return list + slist // append the last item to the front of slist
        else:
            list = list-iteration ( list )
            slist = list[final] + slist // append the last item on the list to the front of slist
            list-sort ( list[:final], slist )
    list-sort ( list, [] ) // start with an emply slist

현재 우리가 하고 있는 일은 slist항을 사용하여 우리의 정렬 목록을 만드는 것입니다.list-iteration을 처음 실행하는 마지막 항목부터 slist의 앞에 새 항목을 추가합니다. 매번 list-iteration을 실행하면 목록에 하나만 남습니다.(이 점에서 slist의 앞에 추가하여 결과를 반환합니다.이렇게 하면 정렬 알고리즘이 완성됩니다.이것은 귀속 특성상 소개에서 논의한 첫 번째 최적화에 의해 구축됩니다.각 순환은 점점 더 짧은 목록을 고려합니다.마지막 요소는 삭제되고 정렬된 것으로 간주되기 때문입니다.
향상된 최적화:
우리는 테스트에서 두 가지 특수한 상황을 확정했다.

목록에 원소가 하나만 있거나 실제로 원소가 없으면 목록을 되돌려주면 됩니다.

목록이 정렬되었으면, 우리도 목록

을 되돌려야 한다
첫 번째 상황은 우리 프로그램의 귀속 구조가 자연적으로 처리한다. 왜냐하면 기본 상황을 촉발하고 간단하게 자신에게 되돌아오기 때문이다.간단해.
두 번째 상황은 좀 까다로워서 어떤 상태 변수가 필요하다.가장 간단한 방법은 목록의 이전 교체에서 어떤 교환이 이루어졌는지 추적하기 위해 브리 값을 사용하는 것이다.이 브리지는 false에서 시작하여 교환을 하지 않았다는 것을 의미하며 교환을 진행할 때 tuple-sort 방법으로 뒤집힌다.다시 말하면 그것은 하나의 단독 함수가 아니라 우리의 전체 교실로 확대될 것이다.

define: bubble-sort (list):
    local define: list-sort ( list, slist, needed-sort ):
        if ( list.length <=1 || needed-sort = false ): return list + slist
        else:
            list = list-iteration ( list, false ) // set needed-sort to false when starting the list-iteration run
            slist = list[final] + slist
            list-sort ( list[:final], slist, needed-sort )
     list-sort ( list, [], true ) // start with an empty slist and with needed-sort set to true so we go through at least one iteration

     define: list-iteration ( list, needed-sort ):
         if (list.length <=1): return list
         else: list[0,1] = tuple-sort( list[0], list[1], needed-sort )
             list-iteration( list[1:]

     define: tuple-sort( x, y, needed-sort ):
         if ( x < y ): return ( x, y )
         else: 
             needed-sort = true
             return ( y, x )

본질적으로, 우리는 needed-sort에서true로 설정하여, 목록에 최소한 한 번의 교체가 있어야 한다. (목록이 한 요소만 길지 않으면)우리가 교체를 시작할 때, 우리는 needed-sort을false로 설정하고, 정렬을 실행하면 tuple-sort을true로 변경합니다.이것은 교환의 매번 교체를 실행한 후에, 우리는 목록에서 적어도 한 번의 교체를 보장할 수 있다는 것을 의미한다.교환되지 않은 첫 번째 교체 후 (목록이 완전히 정렬되었음을 표시함) 기본 상황을 터치하고 종료하여 정렬된 목록을 되돌려줍니다.
이로써 함수식 인코딩을 사용한 거품 정렬 알고리즘의 위조 코드 버전이 완성되었다.만약 어떤 문제나 본고에서 기술한 알고리즘의 다른 최적화를 발견하면 저에게 알려 주십시오.읽어주셔서 감사합니다!