기본 정렬 비교 (1)- 선택 정렬, 버블 정렬, 삽입정렬

기본 정렬에 대해서 설명하려고 한다. 다른 부가 설명이 추가되면 좋겠지만, 직관적으로 설명하기 위해 특징만 쓴다.
소스 코드는 하나하나 다뤄보면서 업로드 할 예정이다.

 

1) 선택 정렬 ( Selection Sort ) 

 - 가장 작은 값 또는 큰 값을 선택해서 차례로 앞에서부터 정렬하는 알고리즘
 - O(N^2)

 

2) 버블 정렬 ( Bubble Sort )

 - 바로 옆에 있는 데이터와 비교해서 정렬하는 알고리즘

 - 그래서 계속 옆과 비교해서 거품같다해서 버블 정렬이라고 하는 것 같음.

 - O(N^2) --> Big-O 표기라서 선택 정렬과 다를 게 없어 보이지만, 진짜 코드를 보면 최악 그 자체

 

3) 삽입 정렬 ( Insertion Sort )

 - 각 숫자를 적절한 위치에 삽입해 정렬하는 알고리즘

 - 필요할 때만 위치를 바꾸는 데 있어 효율적임.
 - O(N^2)

 - 선택, 버블 처럼 O(N^2) 시간 복잡도를 가지고 있는 정렬 알고리즘 중 가장 효율적

 - 거의 정렬되어 있는 경우 굉장히 효율적