정렬 리스트

시간복잡도, 공간복잡도

시간복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데
연산들이 몇 번 이루어지는지를 숫자로 표기 한다. 
여기서 연산이란 산술, 대입, 비교, 이동을 말한다.
연산의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수가 아니라 입력한 데이터의 개수를 나타내는 n에따라 변하게 된다. 연산의 개수를 입력한 데이터의 개수 n의 함수로 나타낸것을 시간복잡도 라고 말하며, 수식으로 T(n)이라고 표기한다.

공간복잡도는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다.
총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P) = c + Sp(n)으로 표기.

여기서 고정 공간은 입력과 출력의 횟소누 크기에 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.
가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구가 되는 추가 공간을 말한다.
(동적으로 필요한 공간)

시간복잡도는 "얼마나 빠르게 실행되느냐" 이고,
공간복잡도는 "얼마나 많은 자원이 필요한가?" 이다.
좋은 알고리즘이란 시간과 자원의사용의 양이 적어야 하지만,
시간과 공간은 반비례적인 경향이 있기 때문에, 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.

정렬 정리

1. 버블정렬
버블정렬은 서로 인접해있는 요소 간의 대소 비교를 통하여 정렬한다.
버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다.
시간복잡도가 최고, 평균 최악 모두 O(N^2)이며 공간복잡도는 하나의 배열만 사용하므로 O(n)을 가진다.
동작방식은 인접한 두 요소간의 대소 비교를 진행한다.

2. 삽입정렬

삽입 정렬은 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다.
동작 방식은 두 번째 index부터 시작한다. 그 이유는 첫 번째 index는 비교할 원소가 없기 때문이다.
알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 왼쪽 맨 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 
모든 원소가 한 번씩만 비교되므로 O(n)의 시간 복잡도를 가진다. 또한 공간 복잡도는, 하나의 배열에서 정렬이 이루어지므로 O(n)이다.

3. 선택 정렬

선택 정렬은 배열에서 최소값을 반복저으로 찾아 정렬하는 알고리즘이다.
시간복잡도는 최선,평균,최악 모두 O(N^2)에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다.
동작방식 3단계로 구성된다. 첫 번째는 주어진 배열에서 최소 값을 찾은 후, 최소값을 맨 앞에 값과 바꾼다. 바꿔준 값을 제외한 나머지 원소를 앞의 방벙으로 바꿔준다.

4. 퀵 정렬

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다. 파이썬이나 자바 언어 자체에 내장되어 있는 알고리즘도 퀵 정렬을 기반으로 한다.

퀵 정렬에는 피봇이라는 개념이 사용된다. 피봇은 한마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다.
최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫번째 값이나 중앙 값을 선택한다.

5. 병합 정렬

병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다. 하지만 차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면,
병합정렬은 배열을 원소가 하나만 남을때 까지 계속 이분할 한 다음, 대소 관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다.

6. 힙 정렬

힙을 알기전에 이진트리를 알아야하므로, 조금 정리해 보았다.

이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어붙이는 구조를 말한다. 이때 트리 구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗히는데,
이진 트리는 모든 노드의 자식노드가 2개 이하인 노드를 뜻한다.
완전 이진 트리는 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽 자식, 오른쪽 자식노드로 차근차근 뻗어가는 구조이다. 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 가득 찬 구조를 말한다.

힙이란 트리 기반의 자료구조로서, 두 개의 노드를 가진 완전 이진 트리를 의미한다. 따라서 힙 정렬이란 완전 이진 트리를 기반으로 하는 정렬 알고리즘이다.
힙의 분류는 크게 최대 힙과 최소 힙 두 가지로 나뉜다. 최대 힙은 내림차순 정렬, 최소 힙은 오름차순 정렬에 사용한다.

최대힙의 경우 부모 노드가 항상 자식노드 보다 크다는 특징을 가진다. 반대로 최소힙의 경우 부모 노드가 항상 자식노드 보다 작다는 특징을 가진다. 이러한 힙에서 
오해할 수 있는 특징은 힙은 정렬된 구조가 아니다. 부모 자식 간의 대소 관계에서만 나타내며 좌우 관계는 나타내지 않기 때문이다. 예를 들어 최소 힙에서 대부분 
왼쪽 노드가 오른쪽 노드보다 작지만 4의 자식 노드인 7과 5는 왼쪽이 오른쪽보다 크다.

힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙 값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에
순서대로 표현하기 적합하다. 또한 균형을 유지하려는 특징 때문에 힙은 우선순위 큐, 다익스트라, 힙 정렬, 프림 알고리즘에 사용된다. 

7. 셀 정렬
셀 정렬은 삽입 정렬의 단점을 보완하고자 도입되었다. 삽입 정렬은 주어진 정렬 상태가 역순으로 배열되어 있을수록 비교횟수가 늘어나고, 최선의 경우 O(N)이지만 최악의 경우 O(N^2)이므로 성능 차이가 크다.
셀 정렬은 이러한 시간복잡도를 평균적으로 낮추고자 도입된 알고리즘이다. 셀 정렬에 사용되는 핵심 개년은 interval(간격)이다. interval은 비교할 원소 간의 간격을 의미한다. 셀 정렬에서는 비교 횟수를 줄이기 위해 interval은 큰 값에서
낮은 값으로 낮춰간다. 동작 방식은 배열에서 interval만큼 떨어진 원소들을 부분집합으로 구성한 뒤 삽입 정렬을 진행하는 방식으로 진행된다.
초기 interval 값은 배열 전체 길이의 / 2 이며 한번 정렬 시, interval 값을 2로 계속 나누어 준다. 
만약 배열 length 가 8이라면, 첫번째 interval값은 4이고, 한번 정렬 시 2로 나누어 삽입정렬을 진행한다.

8. 기수 정렬
기수 정렬은 non-comparison 알고리즘으로 원소간의 대소 비교를 하지 않고 정려하는 알고리즘이다. 대신 기수 정렬은 정렬하고자 하는 수의 낮은 자리 수를 차례대로 확인하여 정렬하는 방식이다. 정렬을 위해 총 10개의 queue를 사용한다.
첫번째로, 1의 자리 수를 확인하여 각 원소의 1의 자리에 해당하는 queue에 쌓아준다.
두번째로, 10의 자리 수를 확인하여 각 원소의 10의 자리에 해당하는 queue에 쌓아준다.
n번째로, n의 자리수를 확인하여 각 원소의 n의 자리에 해당하는 queue에 쌓아주고,
이후 queue의 0~9를 순회하며 차례대로 가져온다. 

8. 카운팅 정렬
카운팅 정렬은 non-comparison sort 알고리즘에 해당하는 알고리즘으로 comparison sort에 해당하는 버블, 선택, 힙, 병합, 퀵, 삽입이 기껏해야 평균적으로 O(nlogn)이나 O(n^2)의 시간복잡도를 갖기에 이를 O(n) 수준으로 낮추고자 도입된 알고리즘이다.
카운팅 정렬의 동작은 이름 그대로 배열에 존재하는 원소 별 개수를 세어 정렬하는 방식이다.

1)배열의 존재하는 값의 각 원소의 개수를 세어줄 새로운 배열 count를 만든다.
count의 길이는 원소의 최대값까지를 인덱스로 사용할 수 있도록 원소의 최대값 + 1만큼으로 지정해준다 (0을 포함)
count[i]는 숫자 i가 배열에 몇개 존재하는지에 대한 정보를 담는다.
2) count배열의 원소를 누적합으로 갱신해준다. 이 작업은 arr에 담긴 원소를 바로 정렬된 위치로 삽입하기 위한 사전작업이다.
ex) [0, 1, 1, 2, 2, 3] -> [0 , 1, 2, 4, 6, 9]
3) arr의 길이와 같은 result 배열을 만들어준다. 해당 배열에는 arr의 원소를 정렬된 위치에 삽입할 것이다.
4) arr의 각 원소값을 count의 인덱스로 사용해 값을 가져온 후, 해당 값을 다시 result의 인덱스로 사용해 arr의 원소로 저장해준다.
5) 해당 작업을 마친 후 count[arr[i]]의 값을 1 줄여준다.

카운팅 정렬은 정렬하고자 하는 배열의 최대값이 매우 클 때 메모리를 매우 비효율적으로 쓰게된다는 단점이 있다.
배열에 존재하는 원소의 개수를 기록해주기 위해서 최대값은 count배열을 만들어야하는데
만약 정렬해야하는 배열이 [1, 123011] 라면 단 2개의 숫자를 정렬하기위하여 10만이 넘는 길이의 배열을 만들어줘야하는 일이 생긴다.
이는 메모리차원에서 매우 비효율적이고, 또 인덱스를 통하여 숫자를 세어주는 방식이기 때문에, 배열에 음수가 존재한다면 사용이 불가능하다.