달력

0

« 2025/4 »

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

'알고리즘'에 해당되는 글 2건

  1. 2017.04.29 병합정렬(Merge Sort)
  2. 2017.02.19 SegmentTree(구간트리)
2017. 4. 29. 22:07

병합정렬(Merge Sort) 알고리즘-자료구조2017. 4. 29. 22:07

#include <stdio.h>
void merge(int *arr, int *sorted, int left, int mid, int right){
int L1 = left;
int L2 = mid+1;
int idx= left;
while(L1 <= mid && L2 <= right){
if(arr[L1] <= arr[L2]) sorted[idx++]=arr[L1++];
else sorted[idx++]=arr[L2++];
}
if(L1 > mid){
L1 = L2;
mid = right;
}
while(L1 <= mid){
sorted[idx++] = arr[L1++];
}
while(left <= right){
arr[left] = sorted[left++];
}
}
void divide(int *arr, int *sorted, int left, int right){
if(left >= right) return;
int mid = (left + right) / 2;
divide(arr, sorted, left, mid);
divide(arr, sorted, mid+1, right);
merge(arr, sorted, left, mid, right);
}
void MergeSort(int *arr, int left, int right){
int sorted[right+1];
divide(arr, sorted, left, right);
}
int main (){
int arr[] = {1, 9, 2, 6, 4, 0, 9};
MergeSort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
for(int i=0; i<sizeof(arr)/sizeof(arr[0]); i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
view raw MergeSort.cpp hosted with ❤ by GitHub

정렬 중 O(nlogn)의 시간복잡도를 가진 방법으로, 개인적으로는 퀵소트나 힙정렬 보다는 구현이 간단하다. 

정렬해야하는 원소가 적다면(정확한 것은 모르겠지만 5개 이하) 삽입정렬이 더 낫다고도 한다.

스택오버플로우를 보면 퀵 정렬이 최악의 경우 O(n^2)임에도 여러가지 이유로 

병합 정렬보다 나은 성능을 보인다고 하는데, 확인해보아야 할 듯 싶다.

C++ std library에는 퀵 정렬과 힙 정렬을 적당히(?) 활용한 Intro sort라는 게 쓰이는 듯 하다.

(http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort)


https://gist.github.com/woo972/0924604b96188cb78b9cf8b1a34fbd19

저작자표시 비영리

'알고리즘-자료구조' 카테고리의 다른 글

SegmentTree(구간트리)  (0) 2017.02.19
:
Posted by SK
2017. 2. 19. 13:01

SegmentTree(구간트리) 알고리즘-자료구조2017. 2. 19. 13:01

#include <iostream>
#include <vector>
using namespace std;
struct SegmentTree{
int n;
vector<int> range;
void build(vector<int> &arr){
n = arr.size();
int pow2=1;
while(n > pow2){
pow2*=2;
}
range.resize(n * pow2 * 2);
init(arr, 0, n-1, 1);
}
int init(vector<int> &arr, int Left, int Right, int node){
if(Left == Right) return range[node] = arr[Left];
int mid = (Left + Right) / 2;
return range[node] = init(arr, Left, mid, node * 2)
+ init(arr, mid + 1, Right, node * 2 + 1);
}
void update(int index, int newVal){
update(index, newVal, 0, n-1, 1);
}
int update(int index, int newVal, int Left, int Right, int node){
if(index < Left || Right < index) return range[node];
if(Left == Right) return range[node] = newVal;
int mid = (Left + Right) / 2;
return range[node] = update(index, newVal, Left, mid, node * 2)
+ update(index, newVal, mid + 1, Right, node * 2 + 1);
}
int getSum(int queryLeft, int queryRight){
return getSum(queryLeft, queryRight, 0, n-1, 1);
}
int getSum(int queryLeft, int queryRight, int Left, int Right, int node){
if(Right < queryLeft || queryRight < Left) return 0;
if(queryLeft <= Left && Right <= queryRight) return range[node];
int mid = (Left + Right) / 2;
return getSum(queryLeft, queryRight, Left, mid, node * 2)
+ getSum(queryLeft, queryRight, mid + 1, Right, node * 2 + 1);
}
};
int main(){
vector<int> arr;
arr.push_back(1);
arr.push_back(4);
arr.push_back(5);
arr.push_back(2);
arr.push_back(3);
arr.push_back(3);
SegmentTree st;
st.build(arr);
printf("get sum; before update\n");
printf("%d\n", st.getSum(0, 3));
printf("%d\n", st.getSum(2, 6));
printf("%d\n", st.getSum(0, 6));
st.update(3, 1);
st.update(5, 7);
printf("get sum; after update \n");
printf("%d\n", st.getSum(0, 3));
printf("%d\n", st.getSum(2, 6));
printf("%d\n", st.getSum(0, 6));
return 0;
}
view raw SegmentTree.cpp hosted with ❤ by GitHub

어떤 수의 배열이 주어지고, ex) 1, 4, 5, 3, 2  이 중에서 3번째부터 5번째 수까지의 중 최소값을 구하라는 문제가 있다면, 

일반적인 방법으로는 주어진 구간을 순회하면서 최소값을 찾는 과정을 거쳐야 할 것이다. 

한 두번정도라면 문제가 되지 않겠지만, 기본적으로 시간이 O(n)이 걸리기 때문에 질의가 여러번 들어온다면 시간이 많이 소요된다. 

그에 반해 세그먼트 트리를 구현하면 각 질의에 대해서 O(log N)의 시간안에 답을 구할 수 있다.

구현 방법에 따라, 최소값 만이 아니라 최대값이나 구간의 합 등 다양한 응용이 가능하다. 


https://gist.github.com/woo972/aa4934738624c7f0c1eb708c725a39d4


저작자표시 비영리

'알고리즘-자료구조' 카테고리의 다른 글

병합정렬(Merge Sort)  (0) 2017.04.29
:
Posted by SK

티스토리툴바