[정렬 알고리즘] 알고리즘 비교

삽입 정렬 vs 버블 정렬 - 개념상의 차이

: 삽입 정렬은 해당 원소 앞의 정렬된 배열에 정렬되지 않은 원소의 위치를 찾아들어가지만, 버블 정렬은 해당 원소 앞의 정렬되지 않은 배열에서 가장 큰 원소를 빼내서 정렬된 쪽(맨 뒤)로 넣는다.

 

삽입 정렬 vs 버블 정렬 - swap 횟수

삽입 정렬은 최대 한 번, 버블 정렬은 최소 0번에서 최대 n번 이루어진다.

 

삽입 정렬 vs 버블 정렬 - 삽입 정렬과 버블 정렬 중 무엇이 더 빠른가?

: 삽입 정렬이 버블 정렬보다 실제로는 더 빠르다. 시간복잡도가 같아도, 그것은 average case로 측정된 것일 뿐이다. 버블 정렬의 경우 배열을 순회할 때 맨 첫번째부터 어떤 특정 지점까지 무조건 순회해야 한다. 그래야 그 특정 지점 -1 지점까지 순회하는 단계로 넘어갈 수 있다. 반면, 삽입 정렬은 현재 삽입해야 할 원소의 자리를 빨리 찾으면 순회를 멈출 수 있다. 매번 역순의 배열이 들어오지 않는 한, 실제로는 삽입 정렬이 버블 정렬보다 빠르다.

 

선택 정렬 vs 버블 정렬 - swap 횟수

: 버블 정렬은 앞서 말했듯이 많이 스왑을 한다. 그에 비해 선택 정렬은 한 번 돌 때마다 최대 한 번만 스왑한다. 그러니까 실제 일반적인 경우에는 선택 정렬보다 버블 정렬이 느리다.

 

버블정렬을 좀 깐거같은데 맞는말임

 

 

https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort

Quicksort vs heapsort