선택 정렬(기본정렬, 선택정렬의 특징, 선택정렬 예시코드, 수행시간)

자료들을 크기 순서대로(오름차순으로) 나열하는 것을 정렬이라고 합니다.

예를 들어 7, 9, 4, 3, 10, 5, 8 를

3, 4, 5, 7, 8, 9, 10 으로 만드는 것이죠.

 정렬은 여러 응용분야에 사용되는 매우 기본적인 문제입니다.

정렬 알고리즘은 선택 정렬(Selection sort), 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort)와 같은 간단한 정렬과

병합 정렬(Merge sort), 퀵 정렬(Quick sort)과 힙 정렬(Heap sort), 계수 정렬(Counting sort)와 같은 고급 정렬 알고리즘으로 나눌 수 있습니다.

 

1. 선택 정렬 (Selection Sort)

 1. 선택 정렬의 특징

 선택 정렬은 가장 간단한 정렬 알고리즘 중 하나로 입력에 민감하지 않습니다. 또 항상 일정한 시간 복잡도를 가지고 있다는 특징이 있죠.

선택적 정렬은 하나의 원소가 남을 때까지 아래 사항을 반복합니다.

 (1) 최대(최소) 원소를 찾는다.

 (2) 최대(최소) 원소와 마지막 마지막(가장 앞에 있는) 원소를 교환한다.

 (3) 마지막(가장 앞에 있는) 원소를 제외한다.

 최대 원소를 찾고 마지막 원소와 위치를 교환하는 방식을 반복하는 것입니다. 이해가 잘 안되신다면 아래의 예시를 참고하실 수 있습니다.

 2. 선택 정렬 예시

  ① 첫 번째 과정(녹색은 최대 원소, 노란색은 정렬된 위치)

 ② 두번째 과정

 ③ 세번째 과정

 ④ 네번째 과정

 ⑤ 다섯번째 과정

 ⑥ 여섯번째 과정

 

3. 선택 정렬 수행시간

총 횟수가 (n-1)+(n-2)+...+2+1=n(n-1)/2  이기 때문에

 선택 정렬의 수행 시간은 모든 경우 O(n^2) 가 됩니다.

 

 

2. 버블 정렬(Bubble Sort)

 1. 버블 정렬의 특징

  버블 정렬도 선택 정렬과 마찬가지로 가장 큰 값을 오른쪽 끝으로 옮기는 정렬 알고리즘입니다.

버블 정렬 알고리즘은 하나의 원소가 남을 때까지 다음사항을 반복합니다.

 (1) 처음부터 마지막까지 차례대로 인접한 두 원소를 비교해 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교환한다.

 (2) 배열의 끝까지 (n-1)번 비교한 후에 마지막 원소를 정렬대상에서 제외하고 나머지 원소들에 대해 위의 과정을 반복한다.

 

 2. 버블 정렬의 예시

 버블 정렬의 과정은 아래와 같습니다.

 ① 첫번째 과정

 ② 두번째 과정

 

 ③ 세번째 과정 : 세번 째 단계에서 교환이 일어나지 않았다. 이것은 정렬되어 있음을 의미하여 정렬과정이 끝난다.

 

 3. 버블 정렬 수행시간 

 버블 정렬(Bubble Sort)의 시간 복잡도는 O(n^2)입니다.

이는 배열의 크기가 n일 때, 최악의 경우 인접한 모든 요소를 비교하여 정렬을 수행해야 하기 때문입니다. 이 때문에 배열이 클수록 수행 시간이 급격하게 증가하며, 일반적으로 다른 정렬 알고리즘보다 성능이 떨어집니다.

 또한, 버블 정렬은 이미 정렬된 배열을 정렬할