[알고리즘 설명]
- 어떤 알고리즘인가?
그동안 탐색 알고리즘을 먼저 작성하였었는데 탐색 알고리즘과 함께 같이 많이 이용되는 것이 정렬 알고리즘입니다.
이분 탐색 알고리즘을 이용할 때 리스트가 미리 정렬되어 있어야 한다고 적어뒀었는데 이때 정렬을 수행하는 알고리즘들을
정렬 알고리즘이라고 합니다.
그중에서 알고리즘을 처음 접하시는 분들도 이해하기 쉬운 버블 정렬입니다.
버블 정렬은 리스트가 정렬이 될 때 모습이 거품이 수면 위로 올라오는 거 같다고 해서 붙여진 이름이라고 합니다
인접한 두 원소의 크기를 비교하여 서로의 자리를 교환할지, 유지할지를 반복 수행하는 비교적 간단한
동작을 수행하기 때문에 구현하기 쉽고 직관적인 알고리즘이라고 생각합니다.
이번에 자료를 찾아보고 정리하면서 기존의 알고 있던 버블 정렬과 개선된 버블 정렬이 있다고 합니다.
기존의 버블 정렬의 경우 정렬이 모두 끝났음에도 지속적인 연산이 수행되는 방면
개선된 버블 정렬의 경우 플래그(상태) 확인용 변수를 추가함으로써 정렬이 모두 완료돠면 종료됩니다.
정렬을 해야 할 자료가 많지 않아 버블 정렬을 채택할 경우
개선된 버블 정렬을 사용하는 것이 아무래도 낫다고 생각이 듭니다.
- 시간 복잡도
최고의 경우 (Best Case) : 개선된 버블 정렬 O(N), 기존 버블 정렬 O(N^2)
최악의 경우 (Worst Case) : O(N^2)
[기존 버블 정렬 / 개선된 버블 정렬 비교]
그렇다면 주어진 값의 대한 기존 버블 정렬과 개선된 버블 정렬의 차이를 한번 확인해 보는 게 좋겠죠?
배열의 길이: 7 / 입력 값 : 1 3 5 7 2 4 6
기존 버블 정렬은 6회 연산을 수행한 반면, 개선된 버블 정렬은 4회 연산을 수행한 것을 확인할 수 있습니다.
그렇다면 기존 버블 정렬의 문제점인 이미 정렬이 완료된 배열을 각각 비교해보겠습니다.
배열의 길이 : 7 / 입력 값 : 1 2 3 4 5 6 7
확실히 이미 정렬이 된 배열의 결과 같은 경우는 개선이 많이 된 모습이 보이는 거 같습니다.
코드 구현이 간단하여 기존의 버블 정렬에서 벗어나지 못한 경향이 있었는데 간단한 코드 추가로
버블 정렬을 개선시킬 수 있다니 조금만 생각해보고 시도했으면 스스로 개선시킬 수도 있었는데
이렇게 알게 되었네요 간단한 알고리즘이라도 개선시킬 수 있는 방법이 있는지 찾아보는 것도
재밌는 경험이 될 수도 있을 거 같다는 생각이 듭니다.
[예제 코드 구현]
기존 버블 정렬
void BubbleSort(int list[], int len)
{
// 길이가 10이라면 9회 반복 수행
for(int i = 0; i < len -1 ; i++)
{
// 길이가 10이라면 8회 반복 수행
for(int j = 0; j< len - i - 1; j++)
{
// 코드 이해를 위해 left right변수에 값을 대입
int left = list[j];
int right = list[j+1];
// left가 right 보다 크다면 교환 진행 (정석적인 Swap코드)
if(left > right)
{
// Ex)
// {} = tmp
// list[J] = 5
// list[J+1] = 2
// 처음상태 => {tmp} | [5][2]
int tmp = list[j]; // 현재 상태 {tmp(5)} | [5][2]
list[j] = list[j+1]; // 현재 상태 {5} | [5(2)][2]
list[j+1] = tmp; // 최종 상태 {5} | [2][5]
}
}
}
}
개선된 버블 정렬
void ImpBubbleSort(int list[], int len)
{
// 길이가 10이라면 9회 반복 수행
for(int i = 0; i < len -1 ; i++)
{
// 플래그(교환 상태 확인용) 변수 추가
bool change = false;
// 길이가 10이라면 8회 반복 수행
for(int j = 0; j< len - i - 1; j++)
{
// 코드 이해를 위해 left right변수에 값을 대입
int left = list[j];
int right = list[j+1];
// left가 right 보다 크다면 교환 진행 (정석적인 Swap코드)
if(left > right)
{
// Ex)
// {} = tmp
// list[J] = 5
// list[J+1] = 2
// 처음상태 => {tmp} | [5][2]
int tmp = list[j]; // 현재 상태 {tmp(5)} | [5][2]
list[j] = list[j+1]; // 현재 상태 {5} | [5(2)][2]
list[j+1] = tmp; // 최종 상태 {5} | [2][5]
// 교환이 이루어 졌으므로 true 변경
change = true;
}
}
// change변수가 false(교환이 없었다면) 반복문 탈출
if(!change)
{
cout << "Sort Complete !!" <<endl;
break;
}
}
}
전체 코드
#include <iostream>
using namespace std;
void BubbleSort(int list[], int len);
void ImpBubbleSort(int list[], int len);
int main()
{
int len;
// 배열(리스트)의 길이 입력
cout << "Enter the size of the list : ";
cin >> len;
// 입력 받은 길이의 배열(리스트) 생성
int list[len];
// 배열(리스트)의 값을 길이 만큼 입력
cout << "Fill in the list values : ";
for(int i = 0 ; i < len; i++)
{
cin >> list[i];
}
// 버블 정렬 실행
BubbleSort(list,len);
// ImpBubbleSort(list,len);
// 결과
cout << "===== Result =====" << endl;
for(int i = 0 ; i< len ; i++)
{
cout << list[i] << " ";
}
return 0;
}
void BubbleSort(int list[], int len)
{
// 길이가 10이라면 9회 반복 수행
for(int i = 0; i < len -1 ; i++)
{
// 길이가 10이라면 8회 반복 수행
for(int j = 0; j< len - i - 1; j++)
{
// 코드 이해를 위해 left right변수에 값을 대입
int left = list[j];
int right = list[j+1];
// left가 right 보다 크다면 교환 진행 (정석적인 Swap코드)
if(left > right)
{
// Ex)
// {} = tmp
// list[J] = 5
// list[J+1] = 2
// 처음상태 => {tmp} | [5][2]
int tmp = list[j]; // 현재 상태 {tmp(5)} | [5][2]
list[j] = list[j+1]; // 현재 상태 {5} | [5(2)][2]
list[j+1] = tmp; // 최종 상태 {5} | [2][5]
}
}
}
}
void ImpBubbleSort(int list[], int len)
{
// 길이가 10이라면 9회 반복 수행
for(int i = 0; i < len -1 ; i++)
{
// 플래그(교환 상태 확인용) 변수 추가
bool change = false;
// 길이가 10이라면 8회 반복 수행
for(int j = 0; j< len - i - 1; j++)
{
// 코드 이해를 위해 left right변수에 값을 대입
int left = list[j];
int right = list[j+1];
// left가 right 보다 크다면 교환 진행 (정석적인 Swap코드)
if(left > right)
{
// Ex)
// {} = tmp
// list[J] = 5
// list[J+1] = 2
// 처음상태 => {tmp} | [5][2]
int tmp = list[j]; // 현재 상태 {tmp(5)} | [5][2]
list[j] = list[j+1]; // 현재 상태 {5} | [5(2)][2]
list[j+1] = tmp; // 최종 상태 {5} | [2][5]
// 교환이 이루어 졌으므로 true 변경
change = true;
}
}
// change변수가 false(교환이 없었다면) 반복문 탈출
if(!change)
{
cout << "Sort Complete !!" <<endl;
break;
}
}
}
참고 자료:
https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC
https://blackon29.tistory.com/3
https://jae-jae.tistory.com/528
https://butter-shower.tistory.com/9
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=blacknaech&logNo=30148931661