안녕하세요
정렬 알고리즘 중 가장 구현하기 쉬운 버블 정렬 알고리즘에 대해 알아보도록 하겠습니다.
버블 정렬 알고리즘
배열등 리스트에서 인접한 데이터들을 비교하여 정렬하는 알고리즘
구현 방법
오름차순 기준(제일 작은 값이 앞으로, 제일 큰 값이 뒤로 정렬)으로 설명하면,
첫 번째 데이터를 모든 데이터와 비교하면서 첫 번째 데이터가 더 크면 서로 스왑 하고,
다음 두 번째 데이터를 모든 데이터와 비교하면서 두 번째 데이터가 더 크면 서로 스왑 하는 과정을
마지막 데이터-1까지 계속 반복합니다.
예제
배열 arrData에 100, 20, 10, 12, 5 값이 있다면, 이 배열 데이터를 정렬하면 다음과 같이할 수 있습니다.
arrData의 첫번째 값 100을 두 번째 값 20과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 100, 10, 12, 5)
arrData의 두번째 값 100을 세 번째 값 10과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 100, 12, 5)
arrData의 세번째 값 100을 네 번째 값 12과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 12, 100, 5)
arrData의 네번째 값 100을 다섯 번째 값 5과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 12, 5, 100)
arrData의 첫번째 값 20을 두 번째 값 10과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 20, 12, 5, 100)
arrData의 두번째 값 20을 세 번째 값 12과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 12, 20, 5, 100)
arrData의 세번째 값 20을 네 번째 값 5과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 12, 5, 20, 100)
arrData의 첫번째 값 10을 두 번째 값 12과 비교했을 때, 10이 더 작기 때문에 두 값을 스왑 하지 않습니다.(10, 12, 5, 20, 100)
arrData의 두번째 값 12를 세 번째 값 5과 비교했을 때, 12이 더 크기 때문에 두 값을 스왑 합니다.(10, 5, 12, 20, 100)
arrData의 첫번째 값 10을 두 번째 값 5과 비교했을 때, 10이 더 크기 때문에 두 값을 스왑 합니다.(5, 10, 12, 20, 100)
C++로 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
using namespace std;
void main()
{
int arrData[5] = { 100, 20, 10, 12, 5 };
int nTemp;
int nSize = sizeof(arrData) / sizeof(int);
cout << "before : ";
for( int i = 0; i < 5; i++ )
cout << arrData[i] << " ";
cout << endl;
for( int i = 0; i < nSize-1; i++ )
{
for( int j = 0; j < nSize-i-1; j++ )
{
if( arrData[j] > arrData[j+1] )
{
nTemp = arrData[j];
arrData[j] = arrData[j+1];
arrData[j+1] = nTemp;
}
}
}
cout << "after : ";
for( int i = 0; i < 5; i++ )
cout << arrData[i] << " ";
cout << endl;
}
|
cs |
'개발공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 삽입 정렬 알고리즘 (0) | 2020.11.20 |
|---|---|
| [알고리즘] 선택 정렬 알고리즘 (2) | 2020.11.19 |
| [알고리즘] 순차 탐색 알고리즘 (0) | 2020.11.17 |
| [알고리즘] 이진 탐색 알고리즘 (0) | 2020.11.16 |