정렬 알고리즘[2] -- 버블 정렬 알고리즘

버블 정렬 알고리즘이란?

 

한 값을 지정해놓고 이값과 다음값을 비교하며 크다면 이동 작다면 break로 값을 정렬하는 방식입니다!

 

마치 물속의 거품이 위로 올라오듯이 큰값은 비교와 swap을 통해 맨뒤로 이동하게됩니다!

 

만약

1 4 5 3 2 라는 배열이 있다면

 

1 4 3 5 2   --  탐색중... 5, 3 스왑

1 4 3 2 5   --  2, 5 스왑

1 3 4 2 5   --  처음으로 돌아와 탐색..... 3, 4 스왑

1 3 2 4 5   --  2, 4 스왑

1 2 3 4 5   --  처음으로 돌아와 탐색..... 2, 3 스왑

 

이런식으로 정렬하는방식!

 

특징이 있다면 

1. 다음값이 현재값보다 작을때 스왑시킨다.

2. 현재값의 정렬이 끝나면 처음으로 돌아와 다시 진행한다.

 

 

이제 코드!

#include <iostream>
#include <string>

void swap(int (&arr)[5],int i,int j){//함수
    int temp=0;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}

using namespace std;
int main()
{
    int a[5]={1,4,5,3,2};

    for(int i=0;i<4;i++){
        for(int j=0;j<4-i;j++){
            if(a[j]>a[j+1]){
                swap(a,j,j+1);//스왑해주기  
            }
            for(int i=0;i<5;i++){//출력
                cout<<a[i]<<"|";
            }
            cout<<endl;
        }
    }

   return 0;
}

선택정렬보다 더 간단하지만

선택정렬보다 시간복잡도는 더 증가했습니다.

 

물론 현재값>다음값 이 조건에 맞는 부분이 적으면 적어질수록 빨리끝나겠지만

이 조건을 만족하는지 확인하는 부분에서 이중for문을 사용하게되는점이 가장 문제가되는 부분입니다....

 

정렬이 이미 된 상태에서도 버블정렬을 사용하면 모든 부분에서 조건에 맞는지 확인을 하기 때문에 

정렬이 조금이라도 되어있는 배열에서 다른 정렬방식보다 훨씬 시간이 오래걸린다는것이 가장큰 단점입니다....

 

 

장점 : 구현하기 쉽다..?

단점 : 시간복잡도

 

 

 

틀린점이 있다면 댓 달아주세요!