기본 정렬 알고리즘 - 버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬

버블 정렬은 가장 근접한 두 요소를 비교하며 둘의 순서를 교체하는 정렬 방식이며 이를 오름차순/내림차순으로 정렬될 때까지 반복한다. 정렬은 마지막 요소를 제외하고 계속 반복하며 최악의 경우 n-1 (n은 데이터 개수) 번 반복하는 O(n2)의 시간복잡도를 가진 알고리즘이다. 가장 쉽게 떠올릴 수 있는 알고리즘이지만 가장 비효율적이다.

 

 

선택 정렬

 

 

선택정렬은 loop마다 가장 작은 값을 찾고 swap할 위치에 넣어준다. 선택정렬은 요소를 비교하고 swap하는 버블정렬과 달리 한번 카드를 훑은 다음 swap을 하는 과정을 n-1 (n은 데이터 개수) 번 반복하기 때문에 버블 정렬보다 2배 더 빠르며 어떻게 정렬되어 있든 일관된 n(n-1) 에 비례한다.

 

 

 

삽입 정렬

비교할 전 요소가 없기 때문에 첫번째 요소는 패스하고 다음 두 요소를 비교한 다음 작은 값을 앞쪽으로 삽입한다.