[ C언어 ] 버블 정렬 (Bubble Sort)에 대해서 -1

[C언어] 버블 정렬 (Bubble Sort)에 대해서 -1

 

 

 

 

버블 정렬 (Bubble Sort) 란?

 

 

원소의 이동들이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다

 

 

 [무작위 배열의 수(데이터)가 버블 정렬되는 예시]

 

 

 

버블 정렬 (Bubble sort ) 실행 과정 살펴보기

 

 

* 7개의 로또 번호가 추첨 되었습니다*

버블 정렬을 이용해 작은수를 앞으로 큰수를 뒤로 보내는 과정을 설명합니다.

 

10

45

25

5

6

35

1

 

 

 

 

 

 

[1번째 반복 - 첫번째 비교] 전

10

45

25

5

6

35

1

 

[1번째 반복 - 첫번째 비교] 후 (데이터 그대로)

10

45

25

5

6

35

1

 

- 최초 10과 45를 비교합니다.

- 작은 수를 왼쪽으로(처음)으로 보내야 합니다. 하지만 10보다 25가 더 큰수이기 때문에 두 데이터는 자리 이동을 하지 않습니다.

  10과 25는 그대로 두고 다음 단계로 넘어갑니다.

 

 

 

 

 

 

 

[1번째 반복 - 두번째 비교] 전

10

45

25

5

6

35

1

 

[1번째 반복 - 두번째 비교] 후 (데이터 이동)

10

25

45

5

6

35

1

 

- 다음 수인 45와 25를 비교합니다.

- 45 > 25 임으로 두 수의 자리가 바뀝니다.

 

 

 

 

 

 

 

[ 1번째 반복 - 세번째 비교] 전

10

25

45

5

6

35

1

 

[ 1번째 반복 - 세번째 비교] 후 (데이터 이동)

10

25

5

45

6

35

1

 

- 다음 수인 45와 5를 비교합니다.

- 45 > 5 임으로 두 수의 자리를 바꿉니다.

 

 

 

↓

↓

↓

↓

 

 

 

쭉쭉쭉 ... 이런 식으로 진행이 되면 결국 45는 맨 뒤로 갑니다.. 이해 가시나요!?

 

[ 1번째 반복 - 여섯번째 비교]

10

25

5

6

35

1

45

 

- 45가 맨 뒤로 갔습니다. 즉 가장 큰수가 첫번째 반복으로 정렬이 되었습니다.

- 총 1번째 반복의 6번 비교를 통해 45를 맨 끝으로 보냈습니다. (2중 for문)

 

 

 

 

여기서 느낌이 오십니까??!!

 

7개의 데이터를 처음 정렬에 총 6번 비교하여 가장 큰수를 끝에 뒀습니다.

다시!! 처음부터 데이터를 비교하며 정렬을 합니다.

그럼 5번만 비교하면 그 다음 큰 수인 35를 45 앞에 위치 시키겠죠??

이미 가장 큰 수를 알고있으니..

 

 

 

2번째 반복 -> [ 5번 비교 ]

10

5

6

25

1

35

45

 

3번째 반복 -> [ 4번 비교]

5

6

10

1

25

35

45

 

4번째 반복 -> [ 3번 비교]

5

6

1

10

25

35

45

 

5번째 반복 -> [ 2번 비교]

5

1

6

10

25

35

45

 

6번째 반복 -> [1번 비교]

1

5

6

10

25

35

45

 

 

이런식으로..

비교 횟수가 점점 줄어듭니다.

(속도 측면에서는 선택정렬과 같습니다. )

 

자세히 보면 규칙이 존재합니다.

 

반복 횟수가 증가 할때마다 비교 횟수는 감소하는!?

 

저희는 이것을 C언어로 표현해 보겠습니다.

 

 

 

 

감사합니다. 공감 한번 부탁드립니다.

[ 다음 장 ]

[ C언어 ] 버블 정렬(Bubble Sort) 오름차순 소스보기 : http://popbox.tistory.com/6 

[ C언어 ] 버블 정렬(Bubble Sort) 내림차순 소스보기 : http://popbox.tistory.com/7