medians_1D.c File Reference

#include "medians_1D.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

Include dependency graph for medians_1D.c:

Go to the source code of this file.

Functions
void	swap (pixelvalue *a, pixelvalue *b)
	Function implementing basic pixel swapping algorithm.
pixelvalue	quick_select (pixelvalue a[], int n)
	Function implementing quickselect algorithm.
pixelvalue	kth_smallest (pixelvalue a[], int n, int k)
	Function implementing kth_smallest() for Wirth macro.
pixelvalue	wirth (pixelvalue a[], int n)
	Function wrapper for kth_smallest to get Wirth's median.
pixelvalue	torben (pixelvalue m[], int n)
	Function implementing Torben's algorithm.
Variables
static const char	rcsid []

---

Function Documentation

pixelvalue kth_smallest	(	pixelvalue	a[],
		int	n,
		int	k
	)

Function implementing kth_smallest() for Wirth macro.

Function : kth_smallest()

• In : array of elements, # of elements in the array, rank k
• Out : one element

Definition at line 130 of file medians_1D.c.

References swap().

Referenced by wirth().

                                           {
    register int i,j,l,m ;
    register pixelvalue x ;

    l=0 ; m=n-1 ;
    while (l<m) {
        x=a[k] ;
        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] ;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pixelvalue quick_select	(	pixelvalue	a[],
		int	n
	)

Function implementing quickselect algorithm.

Function : quick_select()

• In : array of elements, # of elements in the array
• Out : one element

Definition at line 70 of file medians_1D.c.

References swap().

Referenced by bench().

                                    {
    int low, high ;
    int median;
    int middle, ll, hh;

    low = 0 ; high = n-1 ; median = (low + high) / 2;
    for (;;) {
        if (high <= low) /* One element only */
            return a[median] ;

        if (high == low + 1) {  /* Two elements only */
            if (a[low] > a[high])
                swap(&a[low], &a[high]) ;
            return a[median] ;
        }

    /* Find median of low, middle and high items; swap into position low */
        middle = (low + high) / 2;
        if (a[middle] > a[high])    swap(&a[middle], &a[high]) ;
        if (a[low] > a[high])       swap(&a[low], &a[high]) ;
        if (a[middle] > a[low])     swap(&a[middle], &a[low]) ;

    /* Swap low item (now in position middle) into position (low+1) */
        swap(&a[middle], &a[low+1]) ;

    /* Nibble from each end towards middle, swapping items when stuck */
        ll = low + 1;
        hh = high;
        for (;;) {
            do ll++; while (a[low] > a[ll]) ;
            do hh--; while (a[hh]  > a[low]) ;

            if (hh < ll)
            break;

            swap(&a[ll], &a[hh]) ;
        }
        
        /* Swap middle item (in position low) back into correct position */
        swap(&a[low], &a[hh]) ;
        
        /* Re-set active partition */
        if (hh <= median)
            low = ll;
        if (hh >= median)
            high = hh - 1;
    }
}   

Here is the call graph for this function:

Here is the caller graph for this function:

void swap	(	pixelvalue *	a,
		pixelvalue *	b
	)

Function implementing basic pixel swapping algorithm.

Macro left-over from initial implementation. Need to change to a real function and let the compiler do the work

Definition at line 53 of file medians_1D.c.

Referenced by kth_smallest(), and quick_select().

                                        {
    register pixelvalue t;
    t=*a; *a=*b; *b=t;
    return;
}

Here is the caller graph for this function:

pixelvalue torben	(	pixelvalue	a[],
		int	n
	)

Function implementing Torben's algorithm.

Function : torben()

• In : array of elements, # of elements in the array
• Out : one element

Definition at line 178 of file medians_1D.c.

Referenced by bench().

                              {
    int         i, less, greater, equal, half;
    pixelvalue  min, max, guess, maxltguess, mingtguess;

    half = (n+1)/2 ;
    min = max = m[0] ;
    for (i=1 ; i<n ; i++) {
        if (m[i]<min) min=m[i];
        if (m[i]>max) max=m[i];
    }

    while (1) {
        guess = (min+max)/2;
        less = 0; greater = 0; equal = 0;
        maxltguess = min ;
        mingtguess = max ;
        for (i=0; i<n; i++) {
            if (m[i]<guess) {
                less++;
                if (m[i]>maxltguess) maxltguess = m[i] ;
            } else if (m[i]>guess) {
                greater++;
                if (m[i]<mingtguess) mingtguess = m[i] ;
            } else equal++;
        }
        if (less <= half && greater <= half) break ;
        else if (less>greater) max = maxltguess ;
        else min = mingtguess; 
    }
    if (less >= half) return maxltguess;
    else if (less+equal >= half) return guess;
    else return mingtguess;
}

Here is the caller graph for this function:

pixelvalue wirth	(	pixelvalue	a[],
		int	n
	)

Function wrapper for kth_smallest to get Wirth's median.

Function : wirth()

• In : array of elements, # of elements in the array
• Out : one element

Definition at line 163 of file medians_1D.c.

References kth_smallest().

Referenced by bench().

                             {
    return kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1)));
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

const char rcsid[] [static]

Initial value:

    "$Id"

Definition at line 38 of file medians_1D.c.

---