버블정렬, 선택정렬, 삽입정렬

정렬 문제는 알고리즘의 효율성 차이를 극명하게 보여준다.

 

선택정렬 selection sort

 - 전체적으로 훑어보며 가장 작은 값을 골라 앞으로 보내는 방식

 - 최솟값과 그 주소를 저장해둘 변수가 필요함

 - 선택의 범위가 앞에서부터 점점 줄어듦 (= 왼쪽 끝부터 고정됨)

 

버블정렬 bubble sort

 - 바로 옆 값과 비교해 자리를 바꿔주는 방식

 - 선택의 범위가 뒤에서부터 점점 줄어듦

   (= 한 바퀴 돌고 나면 가장 큰 값이 오른쪽 끝에 가 있음 ➜ 오른쪽 끝부터 고정됨)

 - 한바퀴 == 패스스루 passthrough

 - 가장 쉽지만, 그만큼 오래 걸리기 때문에 효율성이 떨어짐

 

삽입정렬 insertion sort

 - 각 숫자를 적절한 위치에 삽입하는 방식

 - 앞의 원소들이 '이미 정렬되어 있다'고 가정 ➜ 멈춰야할 포인트를 알 수 있음

 - 반복할 때마다 원소가 적당한 위치에 들어가기 때문에 추가적으로 전체를 정렬할 필요가 없음

 - 거의 정렬이 되어 있는 상태일 때 사용하면 매우 빠름

 

공통점

 - O(N*N)

• but 실제 속도 ➜ 버블정렬 < 선택정렬 < 삽입정렬

 

차이점

 - 선택정렬, 버블정렬 : 무조건 위치 바꿈

• 정렬되어 있더라도 반드시 반복 수행

 - 삽입정렬 : 필요시에만 위치 바꿈

 

 

---

다음 게시글 - 퀵 정렬