6.1 버블 정렬
= 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환한다.
즉, 두 개씩 비교해서 둘 중에 큰 숫자가 한 칸씩 뒤로 간다.
– 작은 수는 배열의 앞부분으로 이동하는데, 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 한다.
[패스(pass)란? ]
= 배열 전체를 근접한 2개씩 비교하여 큰 것이 뒤로 가게 하는 과정을 반복한다.
1 패스는 = 한 번 입력을 처음부터 끝까지 연속된 두 수를 비교하는 것을 말한다.
1 패스를 수행한 결과는 = 제일 큰 값이 제일 끝에 위치하게 된다. 1패스를 수행하여 제일 큰 값을 정렬하는 데 성공한 것이다.
→ 그러므로 제일 큰 수를 제외하고 나머지들끼리 다시 위의 과정을 반복한다. (1, 2, 3...n패스를 반복하며 정렬을 수행한다.)
전체 정렬이 완료되기 위해서 N개의 원소가 있다면 N-1번의 패스가 수행된다.
[의사코드]
입력: 크기가 n인 배열 A
출력: 정렬된 배열 A
1. for pass = 1 to n-1
2. for i = 1 to n-pass // n-1, n-2, n-3... 1까지 줄어들면서 반복
3. if (A[i-1] > A[i]) // 위의 원소가 아래의 원소보다 크면
4. A[i-1] ↔ A[i] // 자리바꿈
5. return A
별도의 메모리 공간이 필요한 것이 아니라 제자리 정렬이다. 즉, 따로 결과 배열을 만들지 않고 입력 배열 안에서 정렬을 한다.
[단점]
무조건 패스를 다 돈다. → 어떠한 경우에라도 무조건 2개씩 비교한다.
즉, 중간에 정렬이 완료되어도 정렬 과정을 계속 진행한다. (n-1까지 비교)
[코드 구현]
#include <stdio.h>
#include <stdlib.h>
#define N 8
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void bubbleSort(int A[])
{
int temp;
printf("Before Sort : ");
for (int j = 0; j < 0; j++) //배열 출력
printf("%d", A[j]);
printf("\n");
printf("\n <<<<<<<<<<<<<<<<< Bubble Sorting .... >>>>>>>>>>>>>>>>>>\n");
for (int pass = 1; pass <= N - 1; pass++) //하나의 패스를 기준으로
{ // N-1번만 비교해도 된다. -> 마지막 패스에서 남은 것은 정렬할 필요가 없기 때문이다.
printf(" %d pass >> ", pass);
for (int i = 1; i <= N - pass; i++) //순회하면서 비교한다.
if (A[i - 1] > A[i])
SWAP(A[i - 1], A[i], temp);
for (int j = 0; j < 0; j++) //배열 출력
printf("%d", A[j]);
printf("\n");
}
}
int main()
{
int A[N] = {40, 10, 50, 90, 20, 80, 30, 60};
bubbleSort(A);
return 0;
}
[버블 정렬의 단점(무조건 pass를 다 수행한다) 극복을 위한 flag 사용 ]
#include <stdio.h>
#include <stdlib.h>
#define N 8
#define FALSE 0
#define TRUE 1
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void bubbleSort(int A[])
{
int temp;
printf("Before Sort : ");
for (int j = 0; j < 0; j++) //배열 출력
printf("%d", A[j]);
printf("\\n");
printf("\\n <<<<<<<<<<<<<<<<< Bubble Sorting .... >>>>>>>>>>>>>>>>>>\\n");
for (int pass = 1; pass <= N - 1; pass++) //정렬 과정
{
int flag = FALSE;
for (int i = 1; i <= N - pass; i++)
if (A[i - 1] > A[i])
{
SWAP(A[i - 1], A[i], temp);
flag = TRUE; // swap을 했다는 것은 아직 정렬이 안되었다는 의미이므로 정렬 TRUE 이다.
}
if (flag == FALSE) //여기서 flag가 FALSE라는 것은 정렬을 수행하지 않았다는 것 = 정렬이 끝남
break;
printf(" %d pass >> ", pass);
for (int j = 0; j < N; j++) //배열 출력
printf("%d", A[j]);
printf("\\n");
}
}
int main()
{
int A[N] = {40, 10, 50, 90, 20, 80, 30, 60};
bubbleSort(A);
return 0;
}
시간 복잡도
버블 정렬은 for-루프 속에서 for-루프 수행 – pass=1이면 (n-1)번 비교 – pass=2이면 (n-2)번 비교 ⋯ – pass=n-1이면 1번 비교
– 총 비교 횟수: (n-1) + (n-2) + ⋯ + 1 = n(n-1)/2
– 안쪽 for-루프의 if-조건이 True일 때의 자리바꿈은 O(1) 시간
즉, n(n-1)/2 x O(1) = O(n^2) x O(1)
= O(n^2)
'CS > 알고리즘' 카테고리의 다른 글
Chap 6-3. 삽입 정렬(insertion sort) (0) | 2022.06.03 |
---|---|
Chap 6-2. 선택 정렬(selection sort) (0) | 2022.06.03 |
Chap 6. 정렬 알고리즘(sort) (0) | 2022.05.28 |
Chap 5-3. 편집거리 (Edit Distance) (0) | 2022.05.27 |
Chap 5-2.연속 행렬 곱셈 (0) | 2022.05.26 |