정렬

정렬이란 이름, 학번, 학점 등의 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 이렇게 데이터를 정렬하면 더 쉽게 검색할 수 있는 장점이 생긴다.

 

이 데이터들의 정렬 순서에 따라 2가지로 나뉠 수 있는데, 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순 정렬이라고 하고, 그 반대를 내림차순 정렬이라고 한다.

 

그리고 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.

그렇다면 안정적인 알고리즘은 무엇일까? 안정적인 알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지되는 것을 말한다.

 

또한 내부 정렬과 외부 정렬 2가지로도 나눌 수 있는데, 내부 정렬이란 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘을 뜻하며, 외부 정렬이란 정렬할 모든 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘이다. 이 외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 별도로 작업용 파일이 필요하고 알고리즘도 복잡하다. 즉, 우리가 배우는 왠만한 알고리즘은 모두 내부 정렬이다.

 

 

파이썬의 내장함수는 어떤 알고리즘을 적용할까?

파이썬의 sorted() 함수는 Timsort 알고리즘을 이용한다.

 

Timsort란 2002년 소프트웨어 엔지니어 Tim Peters에 의하여 만들어진 알고리즘으로, 앞에서 언급했던 Insert sort와 Merge sort를 결합하여 만든 Hybrid stable sorting 알고리즘이다.

 

이 알고리즘은 미리 어느 정도 정렬된 부분이 존재하는 실생활 데이터의 특성을 고려하여 더 빠르게 작동하도록 고안된 알고리즘으로, 최선의 시간복잡도는 O(n), 평균은 O(nlogn), 최악은 O(nlogn)의 시간복잡도를 보여준다.

 

Timsort는 안정적인 두 정렬방법을 결합했기에 안정적이며, 추가메모리를 사용하긴 하지만 Mergesort에 비해 적은 추가 매모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.

 

버블 정렬

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬이라고도 한다. 그리고 여기서 사용하는 일련의 비교, 교환 과정을 패스(pass)라고 한다.

 

또한 버블 정렬의 특징으로 효율 개선을 위해 다음과 같이 단계적으로 개선해 나갈 수 있다.

1. 전체 수행
2. 교환 횟수에 따라 중단 방식을 적용하여 개선. 즉, 어떤 패스의 원소 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이므로 그 이후의 패스는 불필요하다고 판단하여 정렬을 중단한다.
3. 이미 정렬된 원소를 제외한 나머지만 비교, 교환하도록 스캔 범위를 제한하는 방법으로 개선

 

단순 선택 정렬

단순 선택 정렬은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. 즉, 교환 과정은 다음과 같다.

 

1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 min(a)를 선택한다.
2. min(a)와 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.

 

단, 이 알고리즘은 서로 이웃하지 않은 떨어져있는 원소를 교환하므로 안정적이지 않아, 값이 같은 두 원소의 순서가 정렬 뒤에 뒤바뀔 수 있다.

 

단순 삽입 정렬

단순 삽입 정렬은 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘이고, 알맞은 위치에 삽입하는 작업을 n-1번 반복한다. 단순 선택 정렬과 비슷해 보이지만, 값이 가장 작은 원소를 선택하지 않는다는 점이 다르다.

 

여기까지 시간복잡도는 O(N^2)이다.

 

퀵 정렬

선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가진다. 그렇기 때문에 더욱 빠른 알고리즘이 사용될 필요가 있는데, 그 대표적인 빠른 알고리즘이 퀵 정렬이다. 퀵 정렬은 대표적인 분할 정복 알고리즘으로 평균 속도가 O(NlogN)이다.

 

이때, 2^10 = 1,000이고, 2^20 = 1,000,000이다. 따라서 N이 1,000,000일 때, logN은 20이다. 즉, 매우 빠르다.

 

그렇다면 퀵 정렬이 빠른 비밀은 무엇에 있을까?

비밀은 바로 분할 정복 알고리즘에 있다.

예를 들어, 1 2 3 4 5 6 7 8 9 10 이 있다. 이를 선택 정렬 등으로 정렬하면 10*10해서 100가지 경우의 수가 나온다.

 

그럼 한번 분할 정복을 써보자.

방법은 1 2 3 4 5와 6 7 8 9 10으로 나눠서 둘 중에서 찾아보자는 것이다. 그러면 5*5 + 5*5해서 50가지의 경우의 수가 나온다.

즉, 분할 정복이란 각각 쪼개서 정렬하고 나중에 합치게 되면 결과적으로 훨씬 적은 숫자만큼 연산을 하게 된다는 것이다.

 

다만, 퀵 정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

 

병합 정렬

하지만 병합 정렬은 편향되게 분할될 가능성이 없다. 왜냐하며느 정확하게 반씩 쪼개서 들어가기 때문이다. 따라서 최악의 경우에도 O(NlogN)을 보장한다

 

즉, 병합 정렬은 일단 반으로 나누고 나중에 합쳐서 정렬하는 알고리즘이다. 따라서 병합 정렬은 퀵 정렬과 다르게 피벗 값이 없고, 항상 반으로 나눈다는 특징이 있다. 

 

다만 퀵 정렬보다 평균적으로 딱히 빠르지는 않다. 하지만 보장한다는 점이 강력한 무기가 될 수 있다.

 

힙 정렬

힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법이다. 즉, 정렬의 기초 아이디어는 힙을 이용해 데이터를 정렬하면 어떨까? 에서부터 시작되었다.

 

힙을 알기 전에는 이진 트리에 대해서 알고있을 필요가 있다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때, 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어붙이는 구조를 말한다. 이때 트리 구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗힌다. 단, 이진 트리의 모든 노드는 자식 노드가 2개 이하이어야 한다.

 

여기서 완전 이진 트리가 나오는데 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리이다. 즉, 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 가득 찬 구조이다.

 

그렇다면 드디어 이번 단락의 주제인 힙에 대해 알아보자.

힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 이때 ,힙에는 최대 힙과 최소 힙이 존재하는데, 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있다.

 

다만 트리안에서 특정 노드때문에 최대 힙이 붕괴되는 경우가 있다. 이럴 때는 그 자식 중에서 더 큰 값과 부모를 바꿔주면 된다. 이 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm)을 사용하면 된다.

 

여기서 힙 생성 알고리즘을 정의하면 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이라고 할 수 있다. 그리고 이 힙 생성 알고리즘은 전체 트리를 힙 구조를 가지도록 만든다는 점에서 중요한 알고리즘이다.

 

그렇다면 힙 생성 알고리즘의 시간 복잡도는 몇 일까? -> O(NlogN) 이때, N이 전체 원소의 개수이고, logN이 트리의 높이이다.

 

그리고 힙 정렬은 선택 정렬을 응용한 알고리즘이다. 단순 선택 정렬에서 최대값인 원소를 선택하는 시간 복잡도는 O(N)이지만, 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(logN)이다. 

따라서 단순 선택 정렬의 시간 복잡도는 O(n^2)이지만, 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는데 걸리는 시간 복잡도는 O(NlogN)으로 크게 줄어든다.

 

정렬의 안정성

정렬의 안정성이란 키-값 쌍을 가진 객체들 중에서 같은 키를 가진 객체들의 순서가 정렬 이후에도 유지되는 것을 말한다.

 

정렬의 안정성은 키-값 쌍으로 이루어진 요소들을 정렬할 때 고려되어야 한다.

불안정 정렬을 사용하면 정렬 이전의 순서는 보장되지 않기때문에 정렬 이후에 그 순서가 깨져버린다. 

 

버블 정렬, 삽입 정렬, 병합 정렬은 안정적인 정렬이나, 선택 정렬, 퀵 정렬, 힙 정렬은 기본적으로 불안정적인 정렬이다.

 

정렬의 최소 시간복잡도

요약하면 정렬의 하한 시간복잡도는 O(N*logN)이고, 이가 적용된 정렬 알고리즘은 병합 정렬, 퀵 정렬, 힙 정렬이 있다.

 

퀵 정렬을 더 많이 사용하는 이유

퀵 정렬(Quick Sort)와 병합 정렬(Merge Sort)은 모두 O(nlogn)의 평균 시간 복잡도를 가진 알고리즘입니다. 그럼에도 불구하고, 실제로 많은 상황에서 퀵 정렬이 병합 정렬보다 더 빠르게 동작하는 이유는 여러 가지입니다:

1. 상수 시간의 차이: Big-O 표기법은 알고리즘의 상한을 나타냅니다. 이는 실제 연산 횟수나 상수 시간의 차이를 무시합니다. 퀵 정렬은 실제 연산에서 상수 시간이 병합 정렬보다 작습니다.

2. 캐시 효율성: 퀵 정렬은 인접한 데이터에 대해 작동하기 때문에 현대의 컴퓨터 아키텍처에서 캐시 메모리를 효율적으로 활용합니다. 반면 병합 정렬은 메모리를 추가로 사용하며, 비교적 캐시 불효율적인 방식으로 메모리에 액세스합니다.

3. 메모리 사용: 병합 정렬은 원본 배열과 같은 크기의 추가 메모리를 필요로 합니다. 퀵 정렬은 재귀 호출에 대한 스택 메모리만 필요로 하며, 이는 보통 병합 정렬에 필요한 메모리보다 훨씬 작습니다.

4. 최악의 경우: 퀵 정렬의 최악의 경우 시간 복잡도는O(n^2)입니다. 그러나 이 최악의 경우는 피벗 선택 전략에 따라 발생 빈도가 크게 달라집니다. 좋은 피벗 선택 전략 (예: 랜덤 피벗 또는 median-of-three)을 사용하면 실제로는 거의 발생하지 않습니다.

5. 유연성: 퀵 정렬은 배열에서도, 연결 리스트에서도 잘 동작하며, 다양한 데이터 구조와 호환성이 좋습니다.

6. 인라인화 가능: 퀵 정렬은 종종 기계 코드로 인라인화될 수 있어, 추가적인 성능 향상이 가능합니다.

그러나 퀵 정렬과 병합 정렬 간의 선택은 실제 사용 사례에 따라 달라질 수 있습니다. 안정적인 정렬이 필요한 경우나 메모리 사용에 제한이 있는 경우 병합 정렬이 더 좋은 선택일 수 있습니다.

 

인용

https://www.youtube.com/@dongbinna

동빈나

https://velog.io/@toezilla/1D1Q-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-sort-%EB%82%B4%EC%9E%A5%ED%95%A8%EC%88%98%EB%8A%94-%EC%96%B4%EB%96%A4-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%A0%EA%B9%8C

Python은 어떤 정렬 알고리즘을 이용할까?