제1 2 장 Cach é 알고리즘 과 데이터 구조 거품 정렬

글 목록

제1 2 장 Cach é 알고리즘 과 데이터 구조 거품 정렬

사상

실례

1 라운드

2 라운드

3 라운드

4 라운드

5 라운드

6 라운드

7 라운드

코드 구현

1 판

2 판

최적화

제3 판

최적화

제1 2 장 Cach é 알고리즘 과 데이터 구조 거품 정렬
그것 은 기본 적 인 교환 정렬 이다.
사상
인접 한 요 소 를 두 가지 로 비교 하면 한 요소 가 오른쪽 인접 요소 보다 클 때 그들의 위 치 를 교환 합 니 다. 한 요소 가 오른쪽 인접 요소 보다 작 거나 같 을 때 위 치 는 변 하지 않 습 니 다.
실례
수열 은 다음 과 같 습 니 다:

{5,8,6,3,9,2,1,7}

제1 라운드

1 차 5 와 8 은 5 대 8 보다 작 아 변 하지 않 았 다.

{5,8,6,3,9,2,1,7}

2 차 8 과 6 비교 8 대 6 의 교환 위치.

{5,6,8,3,9,2,1,7}

3 차 8 과 3 비교 8 대 3 의 교환 위치.

{5,6,3,8,9,2,1,7}

4 차 8 과 9 는 8 대 9 보다 작 아 변 하지 않 았 다.

{5,6,3,8,9,2,1,7}

다섯 번 째 9 와 2 는 9 대 2 의 교환 위치 가 크다.

{5,6,3,8,2,9,1,7}

6 차 9 와 1 비교 9 대 1 의 교환 위치.

{5,6,3,8,2,1,9,7}

7 차 9 와 7 비교 9 대 7 의 교환 위치.

{5,6,3,8,2,1,7,9}

이차

첫 5 와 6 은 5 대 6 보다 작 아 변 하지 않 았 다.

{5,6,3,8,2,1,7,9}

2 차 6 과 3 비교 6 대 3 의 교환 위치.

{5,3,6,8,2,1,7,9}

세 번 째 6 과 8 은 6 대 8 보다 작 아 변 하지 않 았 다.

{5,3,6,8,2,1,7,9}

4 차 8 과 2 비교 8 대 2 의 교환 위치.

{5,3,6,2,8,1,7,9}

다섯 번 째 8 과 1 비교 8 대 1 의 교환 위치.

{5,3,6,2,1,8,7,9}

여섯 번 째 8 과 7 은 8 대 7 의 교환 위치 가 크다.

{5,3,6,2,1,7,8,9}

7 차 8 과 9 는 8 대 9 보다 작 아 변 하지 않 는 다.

{5,3,6,2,1,7,8,9}

제3 차

{3,5,2,1,6,7,8,9}

제4 라운드

{3,2,1,5,6,7,8,9}

제5 차

{2,1,3,5,6,7,8,9}

제6 차

{1,2,3,5,6,7,8,9}

제7 라운드

{1,2,3,5,6,7,8,9}

거품 정렬 은 안정 적 인 정렬 이 고 값 이 같은 요 소 는 원래 의 순 서 를 흐 트 러 뜨리 지 않 습 니 다.정렬 정렬 알고리즘 을 바 꾸 려 면 매 라운드 모든 요 소 를 옮 겨 다 녀 야 하기 때문에 (요소 수량 - 1) 바퀴 를 옮 겨 다 녀 야 하기 때문에 평균 시간 복잡 도 는 O (n ^ 2) 입 니 다.
코드 구현
초판

/// d ##class(PHA.YX.Arithmetic).BubbleSortFirst()
ClassMethod BubbleSortFirst()
{
	 s array = $lb(5,8,6,3,9,2,1,7)
	 
	 f i = 1 : 1 : $ll(array) - 1 d
	 .f j = 1 : 1 : $ll(array) - i d
	 ..s tmp = 0
	 ..i ($li(array, j) > $li(array, j + 1)) d
	 ...s tmp = $li(array, j)
	 ...s $li(array, j) = $li(array, j + 1)
	 ...s $li(array, j + 1) = tmp
	 zw array
}

DHC-APP> d ##class(PHA.YX.Arithmetic).BubbleSortFirst()
array=$lb(1,2,3,5,6,7,8,9)

제2판
최적화 하 다.
수열 {5, 8, 6, 3, 9, 2, 1, 7} 이 6 라운드, 7 라운드 로 정렬 되 었 을 때

6 라운드

{1,2,3,5,6,7,8,9}

7 라운드

{1,2,3,5,6,7,8,9}

여섯 차례 의 정렬 을 거 친 후, 전체 수열 은 이미 질서 가 있 게 되 었 다.하지만 알고리즘 은 7 라운드 까지 진행 됐다.
이런 상황 에서 수열 이 질서 가 있다 고 판단 할 수 있다 면 나머지 몇 차례 의 정렬 은 실행 보다 못 하 다.
순환 sortFlag 표 시 를 종료 하 는 것 을 표시 하기 위해 서 quitFlag 을 추가 합 니 다.
코드 는 다음 과 같 습 니 다:

/// d ##class(PHA.YX.Arithmetic).BubbleSortSecond()
ClassMethod BubbleSortSecond()
{
	 s array = $lb(5,8,6,3,9,2,1,7)
	 /*        */
	 s quitFlag = 1
	
	 f i = 1 : 1 : $ll(array) -1  q:quitFlag=0  d
	 .s sortFlag = 1    /*     ，         true */
	 .f j = 1 : 1 : $ll(array) - i  d
	 ..s tmp = 0
	 ..i ($li(array, j) > $li(array, j + 1)) d
	 ...s tmp = $li(array, j)
	 ...s $li(array, j) = $li(array, j + 1)
	 ...s $li(array, j + 1) = tmp
	 ...s sortFlag = 0  /*          ，       ，    false */
	 .i sortFlag = 1  s quitFlag = 0
	 .zw array
}

우 리 는 배열 을 s array = $lb(2,1,3,4,5,6,7,8) 로 바 꾸 고 그들의 값 을 좀 더 늘 렸 다.

/// d ##class(PHA.YX.Arithmetic).BubbleSortSecond()
ClassMethod BubbleSortSecond()
{

	 s array = $lb(2,1,3,4,5,6,7,8)
	 s quitFlag = 1
	
	 f i = 1 : 1 : $ll(array) -1  q:quitFlag=0  d
	 .w "i:"_i,!
	 .s sortFlag = 1
	 .f j = 1 : 1 : $ll(array) - i  d
	 ..w "j:"_j,!
	 ..s tmp = 0
	 ..i ($li(array, j) > $li(array, j + 1)) d
	 ...s tmp = $li(array, j)
	 ...s $li(array, j) = $li(array, j + 1)
	 ...s $li(array, j + 1) = tmp
	 ...s sortFlag = 0
	 .i sortFlag = 1  s quitFlag = 0
	 .w "sortFlag:"_sortFlag,!
	 .zw array
}

실행 결과: 2 라운드 에서 정렬 이 중단 되 었 습 니 다. 배열 이 질서 있 는 수열 이 되 었 기 때 문 입 니 다.

DHC-APP>d ##class(PHA.YX.Arithmetic).BubbleSortSecond()
i:1
j:1
j:2
j:3
j:4
j:5
j:6
j:7
sortFlag:0
array=$lb(1,2,3,4,5,6,7,8)
i:2
j:1
j:2
j:3
j:4
j:5
j:6
sortFlag:1
array=$lb(1,2,3,4,5,6,7,8)

제3 판
최적화 하 다.
이 문 제 를 설명 하기 위해 서 우 리 는 새로운 수열 을 예 로 들 었 다. w i j sortFlag이 수열 의 특징 은 앞부분 (3, 4, 2, 1) 이 무질서 하고 후반 부분의 원소 (5, 6, 7, 8) 가 오름차 순 으로 배열 되 어 있다 는 것 이다.
1 라운드:

첫 번 째 3 과 4 는 3 대 4 로 작 았 다.

(3,4,2,1,5,6,7,8)

두 번 째 4 와 2 는 4 대 2 의 교환 위치 가 크다.

(3,2,4,1,5,6,7,8)

세 번 째 4 와 1 을 비교 하면 4 대 1 의 교환 위치 가 크다.

(3,2,1,4,5,6,7,8)

뒤의 비 교 는 여전히 질서 가 있 음 을 발 견 했 지만 N 차 비 교 를 했다.뒤의 여러 번 원 소 를 비교 하 는 것 은 무의미 하 다.
우 리 는 마지막 교환 이 무질서 한 경 계 였 고 그 다음은 질서 있 는 경 계 였 다 는 것 을 발견 했다.그래서 마지막 교환 위 치 를 기록 하기 위해 lastExchange Index 를 추가 합 니 다.

/// d ##class(PHA.YX.Arithmetic).BubbleSortThird()
ClassMethod BubbleSortThird()
{
	 s array = $lb(3,4,2,1,5,6,7,8)
	 s quitFlag = 1
	 /*             */
	 s lastExchangeIndex = 0
	 /*        ，              */
	 s sortBorder = $ll(array) -1  
	
	 f i = 1 : 1 : $ll(array) -1  q:quitFlag=0  d
	 .w "i:"_i,!
	 .s sortFlag = 1
	 .f j = 1 : 1 : sortBorder  d
	 ..w "j:"_j,!
	 ..s tmp = 0
	 ..i ($li(array, j) > $li(array, j + 1)) d
	 ...s tmp = $li(array, j)
	 ...s $li(array, j) = $li(array, j + 1)
	 ...s $li(array, j + 1) = tmp
	 ...s sortFlag = 0
	 ...s lastExchangeIndex = j  /*                */
	 ...w "lastExchangeIndex  "_lastExchangeIndex,!
	 .s sortBorder = lastExchangeIndex
	 .i sortFlag = 1  s quitFlag = 0
	 .zw array
}

운행. 저희 가 결 과 를 볼 게 요.

DHC-APP>d ##class(PHA.YX.Arithmetic).BubbleSortThird()
i:1
j:1
j:2
lastExchangeIndex  2
j:3
lastExchangeIndex  3
j:4
j:5
j:6
j:7
array=$lb(3,2,1,4,5,6,7,8)
i:2
j:1
lastExchangeIndex  1
j:2
lastExchangeIndex  2
j:3
array=$lb(2,1,3,4,5,6,7,8)
i:3
j:1
lastExchangeIndex  1
j:2
array=$lb(1,2,3,4,5,6,7,8)
i:4
j:1
array=$lb(1,2,3,4,5,6,7,8)

세 번 째 코드 에서 sortBorder 는 무질서 한 수열 의 경계 입 니 다. 매 라운드 정렬 에서 sortBorder 다음 에 있 는 요 소 는 비교 할 필요 가 없습니다.질서 가 있 을 거 야.