[자료구조/알고리즘] 정렬 알고리즘에 대해 알아보자

 

 

선택 정렬(Selection Sort)

• 공간복잡도 O(N) / 시간복잡도 O(N^2)
• 첫 번째 인덱스부터 차례대로 그 뒤 숫자들을 모두 비교해서 가장 작은 값을 찾아 현재 인덱스와 자리를 바꿔준다. 즉, 맨 앞 인덱스부터 작은 수대로 채워 정렬하는 것(최소 선택 정렬), 반대는 최대 선택 정렬이다.

 

삽입 정렬(Insertion Sort)

• 공간복잡도 O(N) / 시간 복잡도  O(N^2), 최선의 경우(이미 정렬돼 있는 경우는 한번 밖에 비교하지 않아서) O(N) 
• 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장, 비교 인덱스를 현재 인덱스 -1로 시작해서 -1씩 해가며 요소를 비교하고 적절한 위치를 찾아 삽입된다.
• 즉, 두 번째 요소는 첫 번째 요소와 비교. 세 번째 -> 두 번째, 첫 번째 순으로 확인. 네 번째 -> 세 번째, 두 번째, 첫 번째 순으로 확인한다. 중간에 삽입된 자리를 찾으면 탐색을 종료한다. (본인 보다 작은 값을 찾은 경우, 그 다음 인덱스에 삽입된다.)

 

버블 정렬(Bubble Sort)

• 공간복잡도 O(N) / 시간복잡도 O(N^2)
• 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하며 정렬 수행, 오름차순 정렬의 경우 비교할 때마다 큰 값이 뒤로 이동
• 두 번째 인덱스부터 시작하며 현재 인덱스 값과 바로 이전의 인덱스 값을 비교하여 순서를 바꿔주거나 넘어간다.
• 이를 전체 배열 크기 - 현재까지 순환한 바퀴 수 만큼 반복한다. n-1, n-2, … , 1개씩 비교한다.

 

병합 정렬(Merge Sort)

• 공간복잡도 O(2N) / 시간복잡도 O(NlogN)
• 합병 정렬은 분할 정복 방식으로 설계된 알고리즘이다.
• 하나의 배열을 입력 받고, 연산 중에 두개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬하여 최후에는 하나의 정렬을 출력한다.

 

퀵 정렬(Quick Sort)

• 공간복잡도 O(2N) / 시간복잡도 O(NlogN), 이미 정렬이 되어 있는 최악의 경우 O(N^2)
• 분할 정복을 이용하는 정렬 알고리즘이다. 가장 빠른 정렬 알고리즘으로 알려져 있으며 일반적으로 많이 사용되고 있다.
• pivot point(피벗)이라고 그룹을 나누는 기준이 되는 값을 하나 설정, 이 값을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 옮기는 방식으로 정렬한다. 이렇게 하나의 그룹을 피벗보다 작은 그룹, 큰 그룹으로 분할한 후 각 그룹 안에서 다시 피벗을 선택하여 동일하게 정렬 작업을 반복한다.

 

힙 정렬(Heap Sort)

• 공간복잡도 O(N) / 시간복잡도 O(NlogN)
• 힙 정렬은 힙에서 최댓값은 항상 루트에 위치한다는 힙의 특징을 이용하여 정렬하는 알고리즘입니다.
• 힙은 부모의 값이 자식의 값보다 항상 크다(또는 항상 작다)는 조건을 만족하는 완전 이진 트리이다.
• 정렬의 과정: 힙에서 최댓값인 루트를 꺼낸다 → 루트 이외의 부분을 힙으로 만든다.
• 파이썬에서는 heapq 모듈을 사용하여 힙 정렬을 간편하게 구현할 수 있다.

 

도수 정렬(Counting Sort)

• 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘이다.
• 도수 정렬 알고리즘은 데이터를 비교, 교환 하는 작업이 필요하지 않아 매우 효율적인 알고리즘이다.
• 정렬 과정: 도수 분포표 만들기 → 누적 도수 분포표 만들기 → 작업용 임시 배열 만들기 → 원래의 배열에 복사하기
• 도수분포표를 만들어 사용하기 때문에 최솟값, 최댓값을 미리 알고 있는 경우에만 적용이 가능하다.

 

 

 

 

 

 

 

[참고]

아래는 정렬 알고리즘이 동작하는 것을 애니메이션으로 확인할 수 있는 사이트이다.

알고리즘이 동작하는 방식을 직관적으로 확인하기 좋다.

 

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations