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
Polyline Simplication  (0) 2010.01.17
Posted by helloktk
,

티스토리툴바