1. 정렬
-
오름차순 정렬(ascending order sort)
-
내림차순 정렬(descending order sort)
-
내부 정렬(internal sorting)
: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 -
외부 정렬(external sorting)
: 정렬한 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
2. 버블 정렬
버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬이다.
- 1차 스캔 : 데이터 개수가 n이라 하면 n-1회 옆에 있는 데이터와 비교한다.
- 1차 스캔을 완료하면 가장 큰 값이 맨 뒤로 이동하게 된다.
- 정렬된 맨 뒤의 값을 제외하고 다시 2차 스캔을 시작한다.(n-2회 비교)
- 2차 스캔을 통해 두번째로 큰 값이 정렬된다.
- 이런식으로 n-1번 반복하면 데이터가 정렬된다.
int main()
{
int N = 5; //배열의 길이
int i, j, temp;
int data[] = { 5, 3, 7, 9, 1 };
// Bubble Sort
for (i = 0; i < N; i++) {
for (j = 0; j < N-(i+1); j++) {
if (data[j] > data[j+1]) {
// 자리교환
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
}
}
}
}
뒤에서부터 버블 정렬
/* 버블 정렬 */
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
/*--- 버블 정렬 ---*/
void bubble(int a[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = n - 1; j > i; j--)
if (a[j - 1] > a[j])
swap(int, a[j - 1], a[j]);
}
}
int main(void)
{
int i, nx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("버블 정렬");
printf("요소의 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int)); /* 요소의 개수가 nx인 int형 배열을 생성 */
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
bubble(x, nx); /* 배열 x를 버블 정렬 */
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x); /* 배열 해제 */
return 0;
}시간복잡도 : O(N * N)
-
비교횟수
버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에
(n-1) + (n-2) + ... + 1 = n(n-1)/2 -
자리 교환 횟수
최악의 경우는 데이터가 역순으로 정렬되어있는 경우이다. 이때의 이동횟수는 비교횟수에 3을 곱한다. (swap함수에서 3번의 자리이동이 일어나기 때문이다.)
최선의 경우는 데이터가 모두 정렬되어있는 경우이다.
선택 정렬과 삽입 정렬과 같은 복잡도를 보이나 연산 수가 가장 많아 정렬 알고리즘 중에서 상대적으로 가장 느리고 효율성이 떨어지는 정렬 방식이다.
데이터의 개수가 적은 경우에 사용됨.
2-1. 버블 정렬 개선 1
x번째 패스 이후 요소의 교환이 한번도 이루어지지 않을 경우 계속 비교해볼 필요가 없다.
- 버블 정렬의 3번째 패스 (3회차)
- 버블 정렬의 4번째 패스 (4회차)
- 4번째 패스 이후 요소의 교환이 한번도 이루어지지 않았음
- 이미 정렬을 마친 배열은 더 이상 패스 진행을 하지 않음.
🌀 버블 정렬 개선 1
- 해당 패스에서 시도한 교환횟수를 exchg변수에 저장해놓는다. (교환이 수행되면 exchg++)
- 만약 교환횟수가 0이라면 그 다음 패스를 실행하지 않고 정렬을 끝낸다.
/* 단순 교환 정렬 (제 2 버전 : 교환 횟수에 따른 멈춤) */
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do {type t = x; x = y; y = t;} while (0)
/*--- 단순 교환 정렬 (제 2 버전 : 교환 횟수에 따른 멈춤) ---*/
void bubble(int a[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
int exchg = 0; /* 경로의 교환 횟수 */
for (j = n - 1; j > i; j--)
if (a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]);
exchg++;
}
if (exchg == 0) break; /* 교환이 이루어 않으면 종료 */
}
}
int main(void)
{
int i, nx;
int * x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("단순 교환 정렬");
printf("요솟수: ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int)); /* 요솟수 nx인 int 형 배열을 생성 */
for (i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
bubble(x, nx); /* 배열 x를 단순 교환 정렬 */
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x); /* 배열을 삭제 */
return 0;
}2-2. 버블 정렬 개선 2
-
버블 정렬의 1번째 패스
1번째 패스의 4번째 비교 이후 교환이 한번도 이루어지지 않았다. 따라서 1, 3, 4는 정렬이 되었음을 알 수 있다.
2번째 패스에서는 3까지 비교를 진행하는 것이 아니라 이미 정렬된 1,3,4를 제외한 9까지 비교를 진행하는 것이 더 효율적이다. -
버블 정렬의 2번째 패스
🌀 버블 정렬 개선 2
- 마지막으로 교환을 수행한 위치(k)를 저장해둔다.
- 그 다음 패스에서는 k이후부터만 비교를 진행한다. (k 이전은 이미 정렬되어있기 때문에 또 비교를 할 필요가 없다.)
/* 단순 교환 정렬 (제 3 버전 : 스캔 범위를 제한) */
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do {type t = x; x = y; y = t;} while (0)
/*--- 단순 교환 정렬 (제 3 버전 : 스캔 범위를 제한) ---*/
void bubble(int a[], int n)
{
int k = 0; /* a[k] 보다 앞은 정렬됨. */
while (k < n - 1) {
int j;
int last = n - 1; /* 마지막으로 교환한 위치 */
for (j = n - 1; j > k; j--)
if (a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]);
last = j;
}
k = last;
}
}
int main(void)
{
int i, nx;
int * x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("단순 교환 정렬");
printf("요솟수 :");
scanf("%d", &nx);
x = calloc(nx, sizeof(int)); /* 요솟수 nx인 int 형 배열을 생성 */
for (i = 0; i < nx; i++) {
printf("x[%d] :", i);
scanf("%d", &x[i]);
}
bubble(x, nx); /* 배열 x를 단순 교환 정렬 */
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x); /* 배열을 삭제 */
return 0;
}2-3. 버블 정렬을 개선한 다른 알고리즘
- 양방향 버블 정렬
- 칵테일 정렬
- 쉐이커 정렬
참고)
- (내 손으로 직접 코딩하며 확인한다!) 자료구조와 함께 배우는 알고리즘 입문 - C 언어 편
- 버블정렬 이미지
https://wonjayk.tistory.com/219
일단 할 수 있는걸 하자.