악명 높은 버블 정렬에서 부울을 사용하는 것을 이해하지 못합니다.

Question

나는 이해하기 위해 애쓰는 한 가지 문제를 명확히하기 위해 여기에 등록 할 기회가 없었습니다. 저는 코딩 경험이 거의없는 더미인데 AppleScript와 제가 읽고있는 교과서를 배우고 있습니다 (H.Rosenthal, H.Sanderson, Mac OSX.2010, 3rd Edition의 스크립팅 및 자동화에 대한 종합 가이드) 나는 비틀 거리며 Bubble 정렬에 대한 간단한 개요. 문제의 예는 다음과 같습니다

on bubblesort(the_list) 
    set is_sorted to false 
    repeat until is_sorted 
    set is_sorted to true 
    repeat with i from 1 to (count the_list) 
    if item i of the_list > item (i + 1) of the_list then 
    set {item i of the_list, item (i + 1) of the_list} to {item (i + 1) of  the_list, item i of the_list} 
    set is_sorted to false 
    end if 
    end repeat 
    end repeat 
    end bubblesort 

내가 루프가 문을 "반복"을 사용하는 경우 하나가한다고뿐만 아니라 작동 방법을 알고, 버블 정렬의 본질을 이해합니다. 내가 짐작할 수없는 것은 불법 사용법이며,이 알고리즘에서 부울을 사용하는 것과 두 루프가 서로 상호 작용하는 방식에 관한 설명을 찾지 못했습니다. 저는 누락 된 경우 여기 내 논리의 날 수정하시기 바랍니다 :

1. 를 우리가 주어진 목록에 적용 할거야 정렬의 종류는 우리가 이가지 반복 루프를 활용하는 것이다 사이클 과정이기 때문에 "반복 with ... from ... to ... "를 사용하여 the_list의 모든 항목을 반복하고"until until "을 반복하여 프로세스에 필요한만큼의 단계를 수행합니다.
2. "반복 할 때까지"는 바깥 쪽 루프가되고 "반복 할 때 ...에서 ...까지 ..."는 전자 안에 중첩됩니다.
3. 바깥 쪽 루프의 부울 식은 새로 생성 된 변수 is_sorted의 값이되며, 클래스의 의미대로 다양한 값이 저장됩니다. 변수를 정의해야하므로 루프 외부에서 변수를 "false"로 설정합니다.

4. item i of the_list > item (i + 1) 인 경우 내부 루프의 조건문 "if"가 "true"로 간주됩니다. 이 조건이 충족되면 is_sorted는 "false"가됩니다 (설정된대로). 결국 목록 (the_list)의 모든 항목이 정렬 될 때이 조건은 "true"로 변경되므로 is_sorted 값이됩니다. 내가 맞습니까? 그리고 여기에 문제가 나온다 :

5. 목록 항목

   • 행동의 정확한 순서는 무엇입니까?
   • 내부 루프 내부의 동작이 처음 실행되거나 위쪽에서 아래쪽 두 루프 내의 모든 동작이 있습니까?
   • is_sorted가 "false"값을 얻는 경우이 변수의 출력이 나중에 어디로 향하는가?
   • 내부 루프의 is_sorted 변수가 "false"이면 is_sorted이 "false"로 설정 될 때까지 "바운스"동작이 반복됩니까?
   • 내부 루프 내에서 is_sorted는 외부 루프의 is_sorted과 어떻게 이야기합니까? 왜 즉시 "false"로 선언 한 후에 is_sorted의 값을 "true"로 변경해야합니까?
   • is_sorted은 정확히 어떻게 내부 루프가 내부 루프의 결과에 응답하기 전에 true로 설정됩니까?

이러한 질문을 공식화하기 어려운, 그래서 응답을 제공하고있어 있다면 감사하겠습니다. 내가 잊어 버린 몇 가지 질문은 건너 뛰었지만 다행히도 나중에 복구 할 것이라고 확신한다.악명 높은 거품 논리 값의

Visualisation of my understanding of bubble sort

Answer 1

사용은 일종의

그것은 단지 하나의 부울, is_sorted해야합니다. 버블 정렬을위한 조기 종료 최적화로 사용됩니다. 바깥 쪽 루프는 is_sorted을 true로 설정하고 내부 루프의 코드가 잘못된 순서로 요소를 검색하면 요소를 바꿀뿐 아니라 is_sorted도 false로 설정합니다. 들의 유사 코드 들여 쓰기되는 경우는 이것을 이해하는 것이 더 쉬울 수 있습니다 어떤 스왑가 발생하면

bubblesort(the_list) 
    set is_sorted to false 
    repeat until is_sorted 
     set is_sorted to true 
     repeat with i from 1 to (count the_list) 
      if item i of the_list > item (i + 1) of the_list then 
       set {item i of the_list, item (i + 1) of the_list} to 
        {item (i + 1) of the_list, item i of the_list} 
       set is_sorted to false 
      end if 
     end repeat 
    end repeat 
end bubblesort 

또 다른 이름과 부울의 의미는 지표가 될 것이며, 더 스왑이 발생하지 않는 경우, 다음 요소는 정렬 할 것 . 이 경우 스왑은 처음에는 true로 설정되고, 바깥 쪽 루프에서는 false로 설정되고, 순서가 잘못된 요소가 감지되고 바뀌면 내부 루프에서 true로 설정됩니다.