Selection Sort

Image Recognition/Fundamental 2021. 2. 25. 09:45 

void selection_sort(BYTE data[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int jmin = i;
        for (int j = i + 1; j < n; j++)
            if (data[j] < data[jmin]) jmin = j;
        if (jmin != i) SWAP(data[jmin], data[i]);
    }
}
728x90
저작자표시 비영리 변경금지

'Image Recognition > Fundamental' 카테고리의 다른 글

Grassfire Algorithm  (0) 2021.03.05
Image Sharpness  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Posted by helloktk
,

Bubble Sort

Image Recognition/Fundamental 2021. 2. 24. 22:01 

#define SWAP(a, b) {BYTE tmp = (a); (a) = (b); (b) = tmp;}
void  bubble_sort(BYTE data[], int n) {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (data[j] > data[j + 1]) 
                SWAP(data[j], data[j + 1]);
        }
    }
}
728x90
저작자표시 비영리 변경금지

'Image Recognition > Fundamental' 카테고리의 다른 글

Image Sharpness  (0) 2021.02.25
Selection Sort  (0) 2021.02.25
Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Posted by helloktk
,

Insertion Sort

Image Recognition/Fundamental 2021. 2. 24. 19:09 

void insertion_sort ( BYTE *data, int n ) {
    int j;
    for (int i = 1; i < n; i++ ) {
        BYTE remember = data[(j = i)];
        while ( --j >= 0 && remember < data[j] ) {
            data[j + 1] = data[j];
            data[j] = remember;
        }
    }
}

 

728x90
저작자표시 비영리 변경금지

'Image Recognition > Fundamental' 카테고리의 다른 글

Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Posted by helloktk
,

Optimized Median Search

Image Recognition/Fundamental 2021. 2. 24. 16:40

참고:  ndevilla.free.fr/median/median/src/optmed_bench.c

/*
 * Optimized median search on 9 values
 */
#define PIX_SORT(a,b) { if ((a) > (b)) PIX_SWAP((a), (b)); }
#define PIX_SWAP(a,b) { BYTE temp = (a); (a) = (b); (b) = temp; }
BYTE opt_med9(BYTE p[9]) {
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ; 
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ; 
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ; 
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ; 
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ; 
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ; 
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}
BYTE opt_med25(BYTE p[]) { 
    PIX_SORT(p[0], p[1]) ;   PIX_SORT(p[3], p[4]) ;   PIX_SORT(p[2], p[4]) ;
    PIX_SORT(p[2], p[3]) ;   PIX_SORT(p[6], p[7]) ;   PIX_SORT(p[5], p[7]) ;
    PIX_SORT(p[5], p[6]) ;   PIX_SORT(p[9], p[10]) ;  PIX_SORT(p[8], p[10]) ;
    PIX_SORT(p[8], p[9]) ;   PIX_SORT(p[12], p[13]) ; PIX_SORT(p[11], p[13]) ;
    PIX_SORT(p[11], p[12]) ; PIX_SORT(p[15], p[16]) ; PIX_SORT(p[14], p[16]) ;
    PIX_SORT(p[14], p[15]) ; PIX_SORT(p[18], p[19]) ; PIX_SORT(p[17], p[19]) ;
    PIX_SORT(p[17], p[18]) ; PIX_SORT(p[21], p[22]) ; PIX_SORT(p[20], p[22]) ;
    PIX_SORT(p[20], p[21]) ; PIX_SORT(p[23], p[24]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[3], p[6]) ;   PIX_SORT(p[0], p[6]) ;   PIX_SORT(p[0], p[3]) ;
    PIX_SORT(p[4], p[7]) ;   PIX_SORT(p[1], p[7]) ;   PIX_SORT(p[1], p[4]) ;
    PIX_SORT(p[11], p[14]) ; PIX_SORT(p[8], p[14]) ;  PIX_SORT(p[8], p[11]) ;
    PIX_SORT(p[12], p[15]) ; PIX_SORT(p[9], p[15]) ;  PIX_SORT(p[9], p[12]) ;
    PIX_SORT(p[13], p[16]) ; PIX_SORT(p[10], p[16]) ; PIX_SORT(p[10], p[13]) ;
    PIX_SORT(p[20], p[23]) ; PIX_SORT(p[17], p[23]) ; PIX_SORT(p[17], p[20]) ;
    PIX_SORT(p[21], p[24]) ; PIX_SORT(p[18], p[24]) ; PIX_SORT(p[18], p[21]) ;
    PIX_SORT(p[19], p[22]) ; PIX_SORT(p[8], p[17]) ;  PIX_SORT(p[9], p[18]) ;
    PIX_SORT(p[0], p[18]) ;  PIX_SORT(p[0], p[9]) ;   PIX_SORT(p[10], p[19]) ;
    PIX_SORT(p[1], p[19]) ;  PIX_SORT(p[1], p[10]) ;  PIX_SORT(p[11], p[20]) ;
    PIX_SORT(p[2], p[20]) ;  PIX_SORT(p[2], p[11]) ;  PIX_SORT(p[12], p[21]) ;
    PIX_SORT(p[3], p[21]) ;  PIX_SORT(p[3], p[12]) ;  PIX_SORT(p[13], p[22]) ;
    PIX_SORT(p[4], p[22]) ;  PIX_SORT(p[4], p[13]) ;  PIX_SORT(p[14], p[23]) ;
    PIX_SORT(p[5], p[23]) ;  PIX_SORT(p[5], p[14]) ;  PIX_SORT(p[15], p[24]) ;
    PIX_SORT(p[6], p[24]) ;  PIX_SORT(p[6], p[15]) ;  PIX_SORT(p[7], p[16]) ;
    PIX_SORT(p[7], p[19]) ;  PIX_SORT(p[13], p[21]) ; PIX_SORT(p[15], p[23]) ;
    PIX_SORT(p[7], p[13]) ;  PIX_SORT(p[7], p[15]) ;  PIX_SORT(p[1], p[9]) ;
    PIX_SORT(p[3], p[11]) ;  PIX_SORT(p[5], p[17]) ;  PIX_SORT(p[11], p[17]) ;
    PIX_SORT(p[9], p[17]) ;  PIX_SORT(p[4], p[10]) ;  PIX_SORT(p[6], p[12]) ;
    PIX_SORT(p[7], p[14]) ;  PIX_SORT(p[4], p[6]) ;   PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[12], p[14]) ; PIX_SORT(p[10], p[14]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[10], p[12]) ; PIX_SORT(p[6], p[10]) ;  PIX_SORT(p[6], p[17]) ;
    PIX_SORT(p[12], p[17]) ; PIX_SORT(p[7], p[17]) ;  PIX_SORT(p[7], p[10]) ;
    PIX_SORT(p[12], p[18]) ; PIX_SORT(p[7], p[12]) ;  PIX_SORT(p[10], p[18]) ;
    PIX_SORT(p[12], p[20]) ; PIX_SORT(p[10], p[20]) ; PIX_SORT(p[10], p[12]) ;
    return (p[12]);
}
/*---------------------------------------------------------------------------
   Function :   kth_smallest()
   In       :   array of elements, # of elements in the array, rank k
   Out      :   one element
   Job      :   find the kth smallest element in the array
   Notice   :   use the median() macro defined below to get the median. 
                Reference:
                  Author: Wirth, Niklaus 
                   Title: Algorithms + data structures = programs 
               Publisher: Englewood Cliffs: Prentice-Hall, 1976 
    Physical description: 366 p. 
                  Series: Prentice-Hall Series in Automatic Computation 
 ---------------------------------------------------------------------------*/
#define SWAP(a, b) {BYTE t = (a); (a) = (b); (b) = t; }
BYTE kth_smallest(BYTE a[], int n, int k) {
    int l = 0, m = n - 1 ;
    while (l < m) {
        BYTE x = a[k] ;
        int i = l, j = m ;
        do {
            while (a[i] < x) i++ ;
            while (x < a[j]) j-- ;
            if (i <= j) {
                SWAP(a[i], a[j]) ;
                i++ ; j-- ;
            }
        } while (i <= j) ;
        if (j < k) l = i ;
        if (k < i) m = j ;
    }
    return a[k] ;
}
#define median(a, n) kth_smallest(a, n, (((n) & 1) ? ((n) / 2) : (((n) / 2) - 1)))
728x90
저작자표시 비영리 변경금지

'Image Recognition > Fundamental' 카테고리의 다른 글

Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Flood-Fill and Connected Component Labeling  (2) 2021.02.10
Posted by helloktk
,

3개의 숫자 중에서 가장 큰 것은

Computational Geometry 2012. 1. 17. 18:06

기하 알고리즘을 다루다 보면 삼각형 그중에서도 직각 삼각형을 다루어야 할 경우가 많다. 대부분의 문제에서는 직각이 되는 꼭짓점을 가운데 두고 세 꼭짓점이 반시계 방향으로 정렬되는 형태로 쓰였기를 원한다. 이 경우 먼저 해야 할 일은 직각이 되는 꼭짓점을 찾는 것이다 (수치적으로 정확히 직각이지 않은 데이터도 처리할 수 있도록 구현이 되어야 한다). 여러 가지 방법이 있을 수 있지만, 그중 간단한 방법은 이 꼭짓점의 대변이 가장 길다는 점을 이용하면 된다. 즉, 3 변의 길이를 구하고, 이 중에서 가장 긴 변을 마주 보는 꼭짓점을 찾으면 된다. 따라서 문제는 3개의 숫자 중에서 가장 큰 것의 번호를 찾으면 된다.

 

 


세 숫자를 num [] ={a, b, c} 라 하자, a가 가장 크려면, a > b, a > c이어야 한다. 그렇지 않다면, b나 c 중에 최댓값이 있다. 따라서 b와 c만 비교하면 된다.

if (a > b && a > c) return 0;
else if (b > c) return 1;
else return 2;


큰 숫자 그 자체를 원하면 그냥

return a > b && a > c ? a : b > c ? b : c;


주어진 숫자가 정수면 좀 더 기교를 부릴 수 있을 것이다.

728x90
저작자표시 비영리 변경금지

'Computational Geometry' 카테고리의 다른 글

Douglas-Peucker Algorithm  (0) 2012.05.03
Inside Quadrilateral, Inside Triangle  (0) 2012.01.18
소금 호수에 생긴 보로노이 다이어그램  (1) 2010.11.06
Finding the Convex Hull of Simple Polygon  (0) 2010.07.03
한 점에서 선분까지 거리  (1) 2010.01.16
Posted by helloktk
,

티스토리툴바