본문 바로가기

정렬6

[C] Countsort:: 계수정렬 안녕하세요. 우주신 입니다. 이번 포스팅에서는 계수정렬(Count Sort)에 대해 알아보겠습니다. 앞선 포스팅에서의 삽입, 퀵, 힙 정렬 등의 방법은 정렬할 때 두 값을 비교하며 정렬을 했다.이를 Comparison Sort라고도 부르는데, 이와 반대로 계수정렬은 비교를 하지 않고 정렬을 하기 때문에 Non-Comparison Sort의 방법 중 하나이다. [4 1 3 4 3] 리스트를 정렬하면서 자세히 알아보자. 우선, 두 개의 리스트 B, C를 만들어준다. B는 A 리스트를 정렬하여 결과물을 넣어줄 리스트이다.C(Counting List)의 Index는 곧 A의 요소이고, C의 값은 A의 요소들의 갯수이다.예를 들어 A에 4가 총 몇 개 나온지는 C의 4번째 Index를 보면 알 수 있다. 그러므로.. 2018. 7. 28.
[C] Quicksort:: 퀵정렬 안녕하세요. 우주신 입니다. 오늘은 퀵정렬(Quick Sort)에 대해 포스팅 하겠습니다.퀵정렬은 시간복잡도가 O(nlogn)으로 실제로 매우 효율적인 알고리즘이라 자주 사용된다. 우선, 위키피디아의 퀵정렬 정의를 참고해보자. 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(Pivot)이라고 한다.피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으.. 2018. 6. 24.
[C] Heap Sort:: 힙정렬 안녕하세요. 우주신 입니다. 오늘은 힙 정렬(Heap Sort)에 대해 알아보겠습니다. 힙 정렬(Heap Sort)은 힙(Heap) 성질을 이용하여 정렬(Sort)하는 방식이다. 힙은 최대값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 하는 자료구조이다. 힙은 두 가지가 종류가 있는데, 최대 힙(Max Heaps), 최소 힙(Min Heaps)이다. 최대 힙은 부모가 자식 노드의 값보다 더 큰 노드 값들로 구성된 트리이다.밑의 그림은 최대 힙의 예시이다. [용어 정리]- 노드, 인덱스 = 주소- 노드 값 = 주소 안에 있는 값 그리고 트리는 당연히 배열로 표현할 수 있다. 이 때, 부모 인덱스가 i라면 왼쪽 자식은 2 * i, 오른쪽.. 2018. 6. 23.
[Python] Merge Sort: 병합 정렬 안녕하세요. 우주신 입니다. 오늘은 병합 정렬(Merge Sort)에 대해 포스팅하겠습니다. 병합 정렬은 정렬되지 않은 전체 데이터를 하나의 단위로 분할한 후에 분할한 데이터들을 다시 병합하며 정렬하는 방식 입니다. 즉, Divide: n개의 데이터를 n/2개 데이터로 나누고 2개의 리스트에 넣습니다.Conquer: 2개의 리스트들의 데이터가 하나가 될 때까지 재귀적으로 나눕니다.Combine: 각각의 2개의 리스트를 병합 합니다. 시간 복잡도는 최악의 경우 O(nlogn)로 이전 포스팅에서 소개했던 insertion sort보다 효율적인 알고리즘 입니다. 코드를 통해 자세히 보겠습니다. 우선, 데이터를 리스트로 입력 받겠습니다.입력 받은 데이터를 띄어쓰기 기준으로 구분하여 이를 정수형으로 리스트에 저장.. 2018. 3. 30.
[R] 정렬, 순위 함수 sort(), rank(), order() 비교 안녕하세요. 우주신입니다. 이번 포스팅에서는 정렬, 순위 함수 sort(), rank(), order()를 비교해보겠습니다. 데이터를 처리할 때 활용도가 높은 함수들인데 가끔 혼동될 때가 있죠... 이번 기회에 싹 정리해보겠습니다. 우선, 샘플 데이터 20개를 만든 후, 설명을 위해 마지막에 NA 값을 추가했습니다. 1. sort() 예제를 보면서 이해하는 것이 수월하니 예제부터 바로 보겠습니다.sort(a) 출력 결과, 절대값을 오름차순으로 정렬했습니다.내림차순으로 정렬하고 싶을 때는 decreasing = T 옵션을 추가하면 됩니다. sort()함수는 자동으로 NA 값을 제외 시킨 후 정렬을 하기 때문에, NA 값을 표시하고 싶다면 na.last 옵션을 추가하면 됩니다.na.last = TRUE인 경.. 2017. 4. 5.
[R] 데이터프레임(DataFrame) 변수명 변경, 변수 선택 및 정렬 안녕하세요. 우주신입니다. 이전 포스팅에 이어 오늘은 데이터프레임 변수명 변경, 변수 선택 및 정렬에 대해 정리해보겠습니다. 우선, 매장 번호, 수입, 방문자수, 매니저로 구성된 데이터프레임을 하나 만들어보겠습니다. 1. 데이터프레임 변수명 변경 변수명 변경에는 두 가지 방법이 있습니다. 첫번째는 names( ) 함수를 사용해서 변경.names(dataframe) 이 두 명령어만 입력하면 패키지 안의 함수들을 사용할 수 있습니다. V1, V2, V3, V4 변수명이 다시 바뀐 것을 확인할 수 있죠? 2. 데이터프레임 변수 선택 데이터프레임을 사용하다보면 특정 변수를 선별해야 하는 경우가 많습니다.먼저, index[which( )] 함수에 대해 알아보겠습니다.dataframe[which(조건, 변수선택)].. 2017. 2. 7.