Programming/알고리즘16 기수 정렬 이번에 소개할 기수 정렬(Radix sort)도 지난번에 다룬 카운팅 정렬 처럼 두 요소의 대소관계 파악없이 진행하는 정렬법 입니다. 그리고 제가 기본적으로 소개할 기본적인 정렬방식의 마지막이기도 합니다. 1. 기수 정렬 기수 정렬은 요소의 대소 관계를 파악하지 않고 정렬하는 방식입니다. 기수 정렬의 시간 복잡도는 O(kn)으로 여기서 k는 요소의 최대 자릿수를 의미합니다. 즉, 정렬하려는 요소가 1의 자리라면 O(n)수준의 아주 빠른 시간 복잡도를 가질 것 이고, 1000, 10000의 자리 이런식으로 늘어날수록 시간 소모가 늘어납니다. 2. 기수 정렬의 동작 원리 기수 정렬은 각 요소를 분해해서 한자리 씩 비교합니다. 숫자라면 일의 자리는 일의 자리끼리, 문자열이라면 마지막 글자 끼리 비교합니다. 그.. 2021. 11. 7. 카운팅 정렬 카운팅 정렬은 도수 정렬, 계수 정렬 등 다양한 이름으로 불리우는 방식입니다. 책마다, 사람마다 다른 이름을 사용하고 있지만 모두 같은 정렬을 말하고 있으며 이 블로그에서는 카운팅 정렬이라고 부를 예정입니다. 1. 카운팅 정렬 카운팅 정렬은 정렬 시 대소 관계를 판단하지 않고 정렬하는 정렬법입니다. 카운팅 정렬을 시간복잡도가 O(n)으로 빠른 알고리즘이지만, 정렬하려는 대상에 따라서 시간 복잡도가 매우 커질 수 있습니다. 정확히는 시간 복잡도가 O(n+k)이기 때문입니다. 여기서 k는 컬렉션 내부의 최대 숫자입니다. 그래서 k가 무지막지하게 커질 경우 시간도 오래걸리게 됩니다. 이렇게 되는 이유는 잠시 후 카운팅 정렬의 방식을 공부해보면 알 수 있습니다. 그리고 그동안 배운 몇 가지의 정렬법이 모두 두 .. 2021. 11. 6. 힙 정렬 이번에 소개할 정렬방식은 힙(Heap) 정렬입니다. 힙이란 보통 부모 노드가 자식 노드보다 큰 조건을 가진 완전 이진트리를 의미합니다. 힙에 대한 자세한 설명은 아래 링크를 참조해주세요. 2021.10.02 - [Programming/자료구조] - 힙 Heap 힙 Heap 힙(Heap) 혹은 히프는 완전 이진 트리 종류 중 하나 입니다. 히프는 여태까지 트리를 계속 해서 연결 자료구조로 구현한 것과는 다르게 1차원 배열을 이용해서 구현할 수 있는 자료구조 이기도 합 bamtory29.tistory.com 1. 힙 정렬 힙 정렬은 전체 트리, 서브 트리에서 가장 큰 값이 부모 노드로 위치하는 트리 구조를 이용한 정렬 방식입니다. 힙에서 가장 큰 값을 가진 것이 루트이므로, 이 루트를 꺼내어서 배열에 차례대.. 2021. 11. 5. 병합 정렬 이번에 소개할 정렬 방식은 병합 정렬입니다. 1. 병합 정렬 병합 정렬은 배열을 두개로 나누고 나눈 배열끼리 비교해서 작은 값을 먼저 넣으며 정렬하는 방식입니다. 이 과정에 한 번으로만 쪼개면 제대로된 정렬이 될리 없으므로 재귀를 이용해서 나눈 배열을 또 나누고 나누어 각 요소가 1개일 경우까지 쪼갠다음 비교해서 작은것 부터 순차적으로 넣으면됩니다. 병합 정렬의 시간 복잡도는 O(n log n)입니다. 다음과 같은 배열이 있으면, 두개의 배열로 나눕니다. 두 개의 배열로 나눈 다음에 나눈 배열의 첫 번째 요소끼리 비교해서 작은 요소를 먼저 넣고 인덱스를 1증가시켜 큰 요소를 넣으면 됩니다. 이대로 넣으면 [3, 9, 2, 4, 5, 7, 1, 8]로 정렬이 안되겠죠? 이를 위해 4개로 나눈것에서 다시 오.. 2021. 11. 3. 퀵 정렬 지난 번에 다룬 셸 정렬은 시간 복잡도가 O(n^2)로 아직 아쉬운 시간소모량을 보여줍니다. 그래서 더 빠른 정렬을 위해 고안된 방식이 퀵 정렬입니다. 1. 퀵 정렬 퀵 정렬은 가장 많이 사용되고 있는 가장 빠른 정렬 방식입니다. 정렬 대상을 특정 기준으로 두 개의 그룹을 나누고 다시 나눈 그룹에 대해 또 그룹을 나누고를 반복하여 정렬하는 방식입니다. 이때 특정 기준으로 설정하는 기준점을 피벗(Pivot)이라고 합니다. 퀵 정렬의 시간 복잡도는 O(n log n)입니다. 퀵 정렬 방식을 설명드리겠습니다. 우선 다음과 같은 배열이 있을 때 피벗을 설정합니다. 피벗은 보통 배열의 가운데 부분에 있는 요소에 대해 설정합니다. 피벗은 4로 설정해도 좋겠지만 6으로 설정하겠습니다. 그리고 피벗에 대해 피벗보다 작.. 2021. 10. 31. 셸 정렬 단순 삽입 정렬은 삽입 위치가 현재 위치에서 멀수록 연산이 멀어진다는 단점이 있습니다. 이 단점을 보완한 정렬방식이 셸 정렬입니다. 1. 셸 정렬 셸 정렬은 정렬할 배열의 요소를 몇개의 그룹으로 나누어 각 그룹으로 단순 삽입 정렬을 하고 그룹을 합쳐나가며 정렬을 하는 방식입니다. 그룹으로 나눌 때 h칸 만큼 떨어진 요소끼리 모아 h개의 그룹으로 나누어 정렬방식을 'h-정렬' 이라고 합니다. 셸 정렬의 시간 복잡도는 최선일 경우의 O(n)과 최악일 경우의 O(n^2)의 평균인 O(n^1.5)입니다. 다음과 같은 8개의 요소를 가진 배열을 가지고 셸 정렬을 해보겠습니다. 3 8 1 4 9 6 2 5 우선 4칸씩 떨어진 요소 그룹 4개로 4-정렬을 해보겠습니다. 같은 색으로 묶인 각 그룹에 대해 큰 수는 뒤로.. 2021. 10. 30. 이전 1 2 3 다음 300x250
