[알고리즘] 정렬 알고리즘(선택 정렬, 버블 정렬, 삽입 정렬)

대표적인 정렬의 종류

O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)

• 선택 정렬(Selection Sort)
• 버블 정렬(Bubble Sort)
• 삽입 정렬(Insertion Sort)

O(n log n)의 시간 복잡도

• 병합 정렬(Merge Sort)
• 퀵 정렬(Quick Sort)

---

선택 정렬(Selection Sort)

설명
선택정렬 알고리즘은 정렬되어 있지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해 나아가는 알고리즘이다. 선택정렬은 정렬된 값을 배열의 맨 앞에서부터 하나씩 채워나가게 된다. 따라서 뒤 index로 갈수록 비교범위가 1씩 감소한다는 특성을 갖는다. 입력 배열이 이미 정렬되어 있거나 말거나 상관없이 동일한 연산량을 갖기 떄문에 최적화의 여지가 적어 성능이 떨어지는 편이다.

루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N) 시간을 소모하며, 최솟값을 찾으면 현재 인덱스와 최솟값을 서로 swap 해야 하기 때문에 O(N) 시간을 필요로 하게 된다. 오름차순 정렬 기준으로 최솟값을 찾기 위해 비교는 여러 번 하지만 swap은 딱 한 번만 일어난다. 따라서 선택 정렬은 총 O(n²)의 복잡도를 갖는 정렬 알고리즘이다. 이러한 성능 상의 한계 때문에 실제로는 잘 쓰이지는 않지만 가장 구현이 쉬운 정렬 알고리즘이라는 이유로 알고리즘을 공부하면 한 번은 꼭 접하게 되는 알고리즘이다.

---

버블 정렬(Bubble Sort)

 

설명
거품 정렬은 뒤에서부터 앞으로 정렬을 진행하는 구조를 가지고 있다.
오름차순 정렬 기준으로 배열의 맨 뒷공간에 가장 높은 값을 보내고, 그 앞에 두번째로 큰 값을 보낸다.
이를 위하여 배열 내 값들을 앞뒤로 서로 비교하며 자리를 바꾸는 작업을 반복한다.

큰 값을 뒤로 보내며 원소들끼리 위치를 변경하는 모습이 물방울이 이동하는 것과 같이 보여서 Bubble Sort라고 이름이 명명되었다고 한다. 다음은 정렬이 어떠한 방식으로 진행되는지 예시와 함께 살펴보고자 한다.

 

예시

initial : [5,3,4,1,2] pass1 : [3,4,1,2,5] pass2 : [3,1,2,4,5] pass3 : [1,2,3,4,5]

3번 반복한 결과 정렬이 완성되었다.

결론
1. 거품 정렬은 큰 값들을 뒤에서부터 앞으로 하나씩 쌓아 나가기 때문에 원소가 자리를 잡을 때 마다 정렬의 범위가 하나씩 줄어들게 된다.
2. 제일 작은 값을 찾아 맨 앞에 위치시키는 선택정렬과는 정 반대의 정렬 방향을 갖는다.
3. 타 정렬 알고리즘에 비하여 값의 swap이 빈번하게 일어나게 된다.
시간 복잡도는 루프문을 통해 모든 인덱스에 방문해야 하므로 기본적으로 O(N)의 시간을 소모하며, 하나의 루프에서는 인접한 원소와 대소 비교 및 swap을 위하여 O(N)의 시간을 추가로 필요로 한다. 따라서 거품 정렬은 O(n²)의 복잡도를 갖는 정렬 알고리즘이다.

구현
거품 정렬은 두개의 반복문을 필요로 한다. 
외부 반복문에서는 정렬의 범위를 줄여나가며 내부 반복문에서는 앞뒤 값을 비교해 나아가며 원소의 위치를 조정한다.

def bubble_sort(arr):
   for i in range(len(arr)-1, 0, -1):  #뒤에서부터 정렬
      for j in range(len(i)):          #앞에서부터 조회   
         if arr[j] > arr[j+1]:         #인근 값 대소 비교
            arr[j], arr[j+1] = arr[j+1], arr[j]
   return arr

---

삽입 정렬(Insertion Sort)

삽입 정렬이란 모든 요소를 앞에서부터 정렬 범위를 확장시켜나가며 정렬을 진행한다. 차례대로 이미 정렬된 배열 부분과 확장된 범위 부분을 비교하며, 자신의 위치를 찾아 삽입함으로써 정렬을 완성시키는 알고리즘이다. 앞서 살펴봤던 선택, 거품 정렬과는 달리 정렬이 진행될수록 범위가 넓어진다.

크게 바라보면 outer루프는 순방향, inner루프는 역방향으로 반복을 진행한다.
정렬 알고리즘은 루프문을 통해 정렬 범위를 2개로 시작하여 전체로 확장해 나아가기 때문에 기본적으로 O(N) 시간을 소모하며, 각 회차마다 정렬 범위에 추가된 값과 기존 값들과의 대소 비교 및 swap을 위해 O(N) 시간이 추가적으로 소모된다. 따라서 삽입 정렬은 O(n²)의 시간복잡도를 가지는 정렬 알고리즘이다.

출처:https://duwjdtn11.tistory.com/514