[Algorithm] 선택 정렬, 버블 정렬, 삽입 정렬

■ 선택 정렬 (Selection Sort)

정렬되지 않은 여러 데이터들 중에 '가장 작은 값'을 찾아 가장 앞의 데이터와 교환하는 작업을 반복하여 정렬
정렬되지 않은 전체 데이터 중에서 해당 위치에 맞는 데이터를 선택하여 위치를 교환

[구현]

Main 함수 및 콘솔창 상태

 

[시간 복잡도]

1. 선택 정렬의 시간 복잡도는 O(n^2)
2. 입력이 거의 정렬되어 있든지, 역순으로 정렬되어 있든지, 랜덤하게 되어 있든지를 구분하지 않고 항상 일정한 시간 복잡도를 가짐 (입력에 민감하지 않은 알고리즘)
3. 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적음

 

■ 버블 정렬 (Bubble Sort)

첫번째 값부터 시작해서 바로 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법을 사용하는 정렬
수가 정렬되는 모습이 물속의 거품(Bubble)이 올라오는 것 같다고 해서 버블 정렬이라고함

 

[구현]

[시간 복잡도]

경우	특징
최선의 경우	· 데이터가 이미 정렬된 경우 (1회전만 하므로 알고리즘이 종료) * 이때 i번째 원소는 (n-i)번 비교하므로 전체 비교 횟수는 n(n-1)/2 [O(n^2)]이지만, 이미 정렬되어 있기 때문에 자리 교환은 발생하지 않음.  * 따라서 버블 정렬은 기존 배열이 어느 정도 정렬되어 있다면 연산 수가 급격히 줄어듦
최악의 경우	· 데이터가 역순으로 정려되어 있는 경우 * 최악의 경우 비교 횟수는 최선인 경우와 같이 i번째 원소는 (n-i)번 비교하므로 전체 비교 횟수는 n(n-1)/2, 비교할 때마다 자리 교환이 발생하므로 i번째 원소는 (n-i)번 교환하므로 전체 교환 횟수는 n(n-1)/2이 됨. 따라서 평균적인 시간 복잡도는 O(n^2)임

 

* 버블 정렬은 매우 단순하지만 정렬할 데이터가 많은 경우에는 수행 시간이 많이 걸림

 

■ 삽입 정렬 (Insertion Sort)

기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하는 정렬
아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식

 

[특징]

1. 선택된 키값을 앞쪽 데이터들의 키값과 비교하여 자신의 위치를 찾아 삽입하여 정렬
2. 데이터 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입
3. 삽입 정렬에서 처음 키값은 두 번째 데이터부터 시작하며 대상 자료가 일부 정렬되어 있을 때 유리한 정렬 방식이다.

 

[구현]

 

 

[시간 복잡도]

경우	특징
최선의 경우	·입력 데이터가 거의 정렬되어 있을 때 * 이때 n-1번 비교하면 정렬이 끝나므로 시간 복잡도는 O(n)
최악의 경우	·데이터가 역으로 정렬되어 있을 때 * 모든 단계에서 앞에 놓인 데이터들을 전부 이동해야 하므로 정렬 속도가 매우 느려지며, 최악의 경우에는 n(n-1)/2이 되어 시간 복잡도는 O(n^2)이 됨. * 평균적인 시간 복잡도는 최악의 시간 복잡도와 같이 O(n^2)

 

 

 

 

 

[시간 복잡도 요약]

선택, 버블, 삽입 정렬은 보통 O(n^2)의 시간복잡도를 가진다