이전 게시물.. ( 버블정렬의 개념!!)
[알고리즘] 버블정렬(bubble Sort)
알고리즘을 공부를 시작해보려고 한다..! 평소에 조금씩이라도 해야할것 같다는 생각이 들었다. 버블정렬을 알아보니 평소에 생각없이 쓰던 정렬 방법이였다는것을 알았다..! 이제는 무엇이든
jihoon2723.tistory.com
버블정렬에 대해 공부하다가..
구현하기 쉬워서 사용하긴 했었는데
공부하다보니 그렇게 효율적인 방법은 아니라는 생각이 들었다..
그래도.. 버블정렬을 필요한 시점이 있지않을까? 싶어서
언제 어떤 상황에서 버블정렬을 적용시키고 언제는 사용하면 안좋은지.. 이런 내용을 좀 알아보도록 하자!
그리고 버블정렬의 문제를 개선한 개선된 버블정렬도 있는데
교환을 수행할 패스의 범위를 제한하는 방법, 양방향 버블정렬 등 있다는 것을 확인 했다!
내가 따로 정리해도 좋을것 같긴 하지만
[알고리즘] 버블정렬 개선하기
버블정렬에 관한 포스팅에 이어 작성함다음과 같은 배열이 있다.1 3 6 4 7 8 9이전에 작성한 버블정렬로 위 배열을 정렬하다가 세번째 패스에 도달하였다고 생각해보자세번째 pass를 진행할것이므
velog.io
이분의 블로그에 아주 잘 정리가 된 것 같아서 링크만 가져왔다 ㅎ
몇번 더 읽어봐야지....
다시 본론으로..
언제 버블정렬을 사용할까?
- (최적화된 버블정렬 사용시) 데이터중에서 교환이 필요한 원소가 매우 적을때, 최적의 시간 복잡도로 O(n)으로 처리될 수 있다고 한다!
- 데이터가 적을때!
- 추가적인 메모리공간이 없을때 ( 버블정렬은 추가적인 메모리 공간이 필요하지 않고 안정적인 정렬을 제공함 )
그럼 언제 사용하면 안돼?!
- 데이터가 많을때! 버블정렬은 최악의 경우 시간복잡도가 O(n^2)로 다른 정렬 알고리즘들에 비해 처리속도가 상대적으로 매우 느려짐!!
- 정렬된 원소가 거의 없는경우!! -> 이 경우는 최적화된 버블정렬을 사용해도 일반 버블정렬을 수행한 것과 별반 다를게 없어서!!
대략적으로 이렇다!!
버블정렬은 일반적으로 다른 정렬 알고리즘에 비해 효율이 좋지 못하기 떄문에 실무에서 거의 사용되지 않는다!
그러나 테스트나, 교육목적으로 사용하기 좋고
안정성이 있기때문에 다른 정렬알고리즘과 비교하기 위한 베이스라인으로 사용되기도 한다!
좀 더 효율적인 정렬 알고리즘들도 알아보자~!!
