[자료구조] 단순 정렬 알고리즘 (버블, 삽입, 선택)

[자료구조] 단순 정렬 알고리즘

1. 버블 정렬

2. 삽입 정렬

3. 선택 정렬

정렬 알고리즘을 자료구조로 보기는 힘들지만

자료구조의 구성에 있어 꼭 필요한 부분이기 때문에

정렬 알고리즘에 대해 간략하게 알아보는 시간을 가지겠다.

그 중에서도 단순 정렬 알고리즘

1. 버블 정렬

가장 널리 알려진 정렬방법이 아닌가 한다.

대학교수님이 굉장히 강조를 하셔서 아직 기억에 남아있다.

하지만 n^2 이라는 어마어마한 시간복잡도를 보이기 때문에

정렬 대상이 소규모일 경우에만 사용하도록 한다.

정렬 알고리즘은 개인적인 생각으론 그림으로

이해하는 것이 가장 좋다고 생각하는데, 그림을

그릴 시간이 없는 관계로 ㅜㅜ 

잘 정리해놓은 포스팅을 소개하도록 하겠다.

http://prosto.tistory.com/161

2. 삽입 정렬

선택 정렬과 엄청 유사하다.

키(key)값을 가지고 비교를 해나가며

정렬을 하는 것이 특징이다.

이 또한 밑의 포스팅을 보면 이해가 갈 것이다.

http://prosto.tistory.com/163

3. 선택 정렬

처음부터 마지막까지 해당 자리에

적절한 값을 잡아가는 것이 특징이다.

무척 단순하다. 따라서 구현을 하는 것이

상당히 쉽다. 하지만 단순 정렬 알고리즘은

모두 n^2의 시간복잡도를 보인다는 것.

http://prosto.tistory.com/159

Prosto님의 힘을 빌려 단순 정렬 알고리즘인

버블 정렬, 삽입 정렬, 선택 정렬에 대해 알아보았다.

구현이 간편하다는 장점말고는 딱히 다른 장점을

찾아볼 수가 없다. 때문에 STL의 sort 알고리즘을 보면

위의 단순 정렬 알고리즘이 아닌퀵 소트로 구현이 되어

있다는 것을 볼 수 있다. 퀵 소트는 상당이 복잡한 알고리즘인데

 그 만큼 성능상의 이점이 있기 때문이다.