알고리즘(Algorithm)/정렬(Sorting) (10) 썸네일형 리스트형 정렬(Sorting)이란? 정렬(sort) 알고리즘이란 주어진 데이터가 있을 때 특정 규칙을 준수하도록 나열하는 문제이다. 특정 규칙을 준수하도록 나열한다는 의미는 특정 문제를 풀기위해 원하는(희망하는) 순서대로 다시 나열 한다는 것이다. 예를들어 주어진 데이터 A = { 4, 2, 1, 3 } 정수형으로 되어 있다고 가정해보자. 우리가 원하는 것은 A의 원소를 숫자가 커지는대로 또는 숫자가 작아지는대로 나열하고 싶다고 한다면 숫자가 커지는대로 정렬을 하면 A = { 1, 2, 3, 4} 로 나열되고 숫자가 작아지는대로 정렬을 하면 A = { 4, 3, 2, 1}로 나열되는 것이다. 정렬에서는 숫자가 증가하는 순을 오름차순정렬(Ascending Order Sorting) 이라고 하고 숫자가 작아지는 순서대로 정렬하는 것을 내림차순.. 계수정렬(Counting Sort) 선택정렬(Selection sort), 삽입정렬(Insertion sort), 거품정렬(Bubble sort)는 평균 시간 복잡도가 O(N^2) 이고 빠른정렬(Qick sort), 합병정렬(Merge osrt), 힙정렬(Heap sort) 은 O( n log n )이였다. 반면 계수정렬(Counting Sort)는 다른 정렬 알고리즘보다 좀 더 빠른 O(n)의 성능을 보여준다. 그럼 다른 정렬알고리즘 보다 빠르다고하니 계수정렬만 사용하면 되는거 아닌가 ? 라고 생각할 수 있는데 계수정렬은 특정 상황에서만 사용해야하는 제약이 따른다. 계수정렬 알고리즘을 살펴보자. 계수정렬은 기본적으로 원소들의 빈도를 카운트하여 정렬하는 방법이다. 빈도를 카운트하여 정렬한다는게 이해하기 어려울수 있으니 그림을 보면서 이해하.. 퀵정렬(Quick Sort) 퀵정렬은 매우 효율적인 정렬 알고리즘이며 데이터 배열을 특정 규칙에 의해 분할 하면서 정렬을 하는 분할정복(Divide & Conquer) 에 기반한다. 분할단계에서는 배열은 다음과 같은 조건이 만족되도록 2개의 부분으로 나누는데 그 중 하나는 지정된 값보다 작은 값들로 다른 하나는 지정된 값보다 큰 값들로 이루어지도록 분할한다. 여기서 지정된 값을 보통 피벗(pivot)이라고 불린다. 즉, 분할되기전 배열에서 임의의 기준값이 될 피벗을 하나 선택한다. 피벗을 배열중에 어떤 놈을 선택할지는 나중에 설명하겠다. 지금은 그냥 배열에 아무값이나 선택한다고 생각하면 된다. 지금은 일단 배열의 맨 끝에 있는 놈을 피벗으로 선택한다. 다음 그림에서 ①번은 아직 정렬되지 않은 배열데이터를 나타내고 ②번은 맨 끝에 있.. 버킷정렬(Bucket Sort) 버킷 정렬(bucket sort) or bin sort 은 입력 값이 일정한 범위에 걸쳐 분포(uniformly distributed)되어있을 때 주로 유용하다. 예를들어 0.0에서 1.0 범위의 부동 소수점 숫자 집합을 정렬해야 하고 싶다고 할때 선택할수 있는 정렬의 방법은 여러가지이다. 간단한 방법은 비교 기반 알고리즘(comparision based sort alogrithm)을 적용하면 된다. 비교 기반 알고리즘 중 그래도 시간복잡도가 좀 빠른 병합 정렬(merge sort), 힙 정렬(heap sort), 빠른 정렬(quick sort)은 O(nLogn) 이다. 즉 O(nLogn)보다 좋을수는 없다. 선형 시간(linear time)으로 배열을 정렬할 방법은 없을까? 카운팅 정렬(counting.. 기수정렬((Radix Sort) 기수 정렬(radix sort)은 counting sort 처럼 비교연산(comparision operation)을 하지 않고 입력된 원소들간의 순서가 보장되는 stable 한 정렬 알고리즘이다. (comparision, stable 에 대해서는 여기 참고) 기수 정렬은 정렬 방법의 특수성(counting sort를 사용함) 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용(bucket sort가 부동소수점을 정렬할때 유용하다)할 수 없지만 정수와 같은 자료를 정렬할때 선형시간(lienar time)으로 정렬하기 때문에 시간복잡도가 O(dn)로 매우 빠른 정렬알고리즘이다. 그럼 정수 정렬시 counting sort도 선형시간으로 정렬이 가능한 정렬알고리즘이라고 하였고 radix so.. 힙정렬(Heap Sort) 힙정렬(Heap Sort)는 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 따라서 힙(Heap) 자료구조를 잘 이해하고 있어야 하기 때문에 반드시 관련 POST를 읽고 이 글을 읽어야 한다. 알고리즘은 힙에 자료를 추가하고 최대값 또는 최소값을 하나씩 삭제하는 것과 동일한데 Note - 힙정렬 알고리즘 1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 2. 최대힙(내림차순정렬이 필요한경우) 인경우 루트노드가 자식노드보다 항상 크도록하고 최소힙(오름차순 정렬이 필요한경우)인경우 로트노드가 자식노드보다 항상 작도.. 합병정렬(Merge Sort) 지난 강좌에서는 버블정렬(Bubble Sort), 선택정렬(Selection Sort), 삽입정렬(Insertion Sort)와 같이 비교적 간단하고 이해하기 쉬우나 큰 데이터 셋에는 효율적이라고 할 수 없는 기본적인 정렬 알고리즘에 대해서 알아 봤었다. 이번 시간에는 분할정복 알고리즘을 통해 정렬이 이루어지는 합병정렬(Merge Sort)에 대해서 설명하겠다. 분할정복 알고리즘 개념이 필요하니 분할정복(Divide & Conquer) 알고리즘 을 반드시 읽어 봐야 한다. 합병정렬을 하기위해 예를들어 아래와 같은 데이터가 있다고 하자. 합병정렬은 먼저 데이터 크기가 1개가 될때 까지 반복하여 같은 반으로 나누는 분할 단계를 거친다. 여기서는 8 개 항목의 배열을 크기가 4인 배열로 분할한다. 크기가 4개.. 삽입정렬(Insertion Sort) 삽입 정렬( insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘인데 버블정렬(Bubble Sort)와 선택정렬(Selection Sort)와 마찬가지로 단순하고 이해하기 쉽지만 성능상으로는 느린 정렬 알고리즘 중 하나이다. 어떤 식으로 동작하는지 살펴보자. 위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다. 삽입정렬은 처음 2개의 원소들을 비교한다. 14와 33 2개의 원소를 비교하면 이미 오른차순으로 정렬되어 있고 정렬 서브리스트(sorted sub-list) 14를 가지게 된다. 이제 앞으로 이동하여 33과 27을 비교한다. 33.. 이전 1 2 다음
