[자료구조] 정렬
정렬 알고리즘
키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꿔 놓는 작업을 의미한다.
- 숫자 : 사전식 순서 또는 크기를 기준으로 나열
- 문자 : 사전식 순서에 따라 나열
정렬 방법
- 오름차순 (ascending) : 작은 것에서 큰 것
- 내림차순 (descending) : 큰 것에서 작은 것
- 단일 키 (single key) : 하나의 정렬 기준
- 복합 키 (multi key) : 두 개 이상의 정렬 기준
활용
- 파일 처리
- 데이터 베이스
- 전화번호부
정렬 관련 용어
- 집합(set) : 정렬할 데이터 셋 전체
- 원소(element) : 데이터 셋의 datum
- 부분 집합(subset) : 전체 데이터셋을 어떤 기준으로 분할한 일 부분
- 키(key) : 정렬의 기준이 되는 특정 값
- 비교(comparison) : 정렬 = 크기 또는 순서를 비교하는 것
- 이동(move) : 비교의 결과에 따라 위치 재조정
- 교환(swap) : 두 개 원소의 자리를 서로 맞바꿈
- 시간복잡도(time complexity) : 알고리즘 수행에 필요한 연산의 수(CPU Time)
- 공간복잡도(space complexity) : 알고리즘 수행에 필요한 메모리의 크기
- 분할정복(divide&conquer) : 커다란 데이터셋을 MECE 규칙에 따라 작게 분할하여 계산
- 병합(merge) : 두 개 부분집합을 입력 받아 하나의 합집합을 출력하는 연산
- 피벗(pivot) : 회전축, 축, 중심 / 재귀적으로 실행할 때 매 단계의 기준이 되는 원소
- 기수(radix) : 10진수 체계에서는 기수가 10, base라고도 함
- 최선(best case) : 가장 좋은 성능을 보이는 경우
- 최악(worst case) : 가장 좋지 않은 성능을 보이는 경우
- 안정성(stability) : 알고리즘의 실행 결과를 신뢰할 수 있는 정도
선택 정렬
선택 정렬은 전체 숫자들 중에서 가장 작은 숫자를 반복적으로 선택해 앞쪽으로 옮기는 방법. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬와 최대 선택 정렬로 구분 할 수 있다.
- 최소 선택 정렬 : 오름차순
- 최대 선택 정렬 : 내림차순
돌아가는 로직 순서
- 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.
- 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
- 다음 인덱스에서 위 과정을 반복.
선택 정렬 알고리즘은 n-1 , n-2, … 1개씩 비교를 반복한다.
배열이 어떻게 되어있던 전체 비교를 진행하기 때문에 시간 복잡도는 O(n^2)이다.
단순한 만큼 비효율적이다.
삽입 정렬
삽입 정렬은 손 안에 정렬된 카드가 있고, 카드를 추가로 한 장씩 더 받을 때 마다 그 카드를 올바른 자리에 넣는 것과 유사하다. 즉, 정렬이 안 된 부분의 숫자를 정렬된 부분의 적절한 위치에 찾아 삽입하는 과정을 반복한다.
돌아가는 로직 순서
- 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해 주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
- 별도로 저장해 둔 삽일을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
- 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해 주고, 비교 인덱스를 -1 하여 비교를 반복한다.
- 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장.
최악의 경우 즉, 역으로 정렬되어 있을 경우에는 선택 정렬과 마찬가지로 n-1 , n-2, … 1개씩 비교를 반복하여 시간복잡도는 O(n^2)이지만
이미 정렬되어 있는 경우에는 한 번씩만 비교를 하기 때문에 시간 복잡도는 O(n)이다.
하지만 상한을 기준으로 하는 빅오 notation은 최악의 경우를 기준으로 평가하기 때문에 시간 복잡도는 O(n^2)이다.
버블 정렬
버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방법이다. 비교 교환 과정은 리스트 왼쪽 끝에서 오른쪽으로 진행되며 스캔1이 안료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하고 더 이상 교환이 알어나지 않을 때 까지 수행한다. 즉 전체 배열의크기 - 현재까지 순환한 바퀴 수 만큼만 반복해 주면 된다.
돌아가는 로직 순서
- 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 인전의 인덱스 값을 비교한다.
- 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
- 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
- 이를 전체 배열의크기 - 현재까지 순환한 바퀴 수 만큼 반복한다.
선택 정렬과 같이 배열이 어떻게 되었든 간 전체 비교를 진행하기 때문에 시간 복잡도는 O(n^2)이다
병합 정렬
병합 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할될 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 분할 정복 기법에 바탕하여 하나의 문제를 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
즉, 입력으로 하나의 배열을 받고, 연산 중에 두 개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력한다.
돌아가는 로직 순서
- 현재 배열을 반으로 쪼갠다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.
- 이를 쪼갠 배열의 크기가 0이거나 1일 때 까지 반복한다.
합병 과정은 두 배열 A,B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우 O(n1+n2)와 같다. 배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우 N = N1 + N2이므로 O(N)이라고 할 수 있다.
퀵 정렬
퀵 정렬은 분할 정복을 이용하여 정렬을 수행하는 알고리즘이다. pivot potin라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다. 이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것이다. 평균적으로 매우 빠른 수행 속도를 자랑한다.
돌아가는 로직 순서
- pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나 랜덤 값으로 정한다.
- 분할을 진행하기 전에, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장한 rigth 변수를 생성한다.
- right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며, 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다. pivot point 보다 작은 배열 값을 찾으면, 반복을 중지
- 그 다음 left부터 비교를 진행. 비교는 right가 left보다 클 때만 반복하며, 비교한 배열값이 pivot point 보다 작으면 left를 하나 증가시키고 비교를 반복한다. pivot point 보다 큰 배열 값을 찾으면, 반복을 중지
- left 인덱스의 값과 right 인덱스의 값을 바꿔준다.
- 3,4,5 과정을 left < right가 만족 할 때 까지 반복한다.
- 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.
- 맨 왼쪽부터 left - 1 까지, left + 1부터 맨 오른쪽 까지로 나눠 퀵 정렬을 반복한다.
퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이다. 각 정렬은 배열의 크기 N만큼 비교하며, 이를 총 분할 깊이인 logN만큼 진행하므로 총 비교횟수는 NlogN, 즉 시간 복잡도는 O(NlogN)이다.
힙 정렬
힙 정렬은 정렬한 배열의 요소들을 먼저 모두 최소 힙에 삽입 한 후, 하나씩 차례대로 꺼내면 가장 작은 요소부터 나와 오름차순 정렬된다. 우선 순위 큐를 완전 이진 트리로 구현하는 방법이며, 최대값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다.
힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에 순서대로 표현하기 적합하다. 또한 균형을 유지하려는 특징 때문에 힙은 우선순위 큐, 다익스트라, 힙 정렬, 프림 알고리즘에 활용한다.
시간복잡도 O(NlogN)이다.
정렬 알고림즈의 목표
복잡도를 줄이고
- 메모리 사용량(공간복잡도)과 CPU 사용시간(시간복잡도)를 줄이는 것이 목표
- 일정 수준에 다다르자 복잡도를 줄이는 것에 한계 봉착
- 알고리즘의 한계는 하드웨어로 해결(큰 메모리와 싸고 빠른 CPU의 등장..!)
안정성은 높이고
- 알고리즘은 일관된 실행결과를 보장해야함
- 그런데, 일부 알고리즘은 최악의 경우, 최선의 경우에 따라 그 결과가 많이 다름
- 약간의 성능을 포기하더라도 안정적인 정렬 결과를 보장해야함
구현 복잡도와 알고리즘 효율성에 따른 분류
- 단순하지만 비효율적 : 삽입 정렬, 선택 정렬, 버블 정렬 등
- 복잡하지만 효율적 : 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등
Reference