bubble 정렬을 개선한 소트 방법으로 두개의 변수로 소트할 구역을 알아냅니다.

• low : 소트할 배열의 하단 위치
• high : 소트할 배열의 상단 위치

• low : 1 , high : 7 이면 1 번째 ~ 7 번째가 소트할 대상
• low : 3 , high : 5 이면 3 번째 ~ 5 번째가 소트할 대상 즉 1 번 에서 2 번까지 , 6 번에서 7 번까지는 이미 소트가 이루어진 것을 의미 합니다.
• low >= high 이면 이미 소트가 끝났다는 것을 의미

• 한 번은 아래에서 위로 ... 마지막으로 자리바꿈이 이루어진 위치를 high 변수로 재 지정
• 한 번은 위에서 아래로 ... 마지막으로 자리바꿈이 이루어진 위치를 low 변수로 재 지정
• low < high 참이면 반복

예를 들면,

• step1.

       6 2 9 8 3 4 7
  
       --->
       2 6 8 3 4 7 9 ... right 6
  
            <----
       2 3 6 8 4 7 9 ... left 3
  

  

• step2. .....

입력

n 은 1000 이하의 양의 정수이다.

출력

입출력 예

입력

7 
6 2 9 8 3 4 7

출력

3

추천:elfhero