tsort.h

// This software is distributed as part of the Improla library. 
// Improla is a GUI framework for image processing.
// 
// Copyright (c) 2004, B. R. Siva Chandra, India
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// In case you would like to contact the author, use the following e-mail
// address: sivachandra_br@yahoo.com

#ifndef __T_SORT_H__
#define __T_SORT_H__

#include <tnt/tnt_array1d.h>

namespace tutk
{ // Start of namespace brace.

enum Order {ASCENDING, DESCENDING};

template < class T >
void bubbleSort(TNT::Array1D< T > array, Order order)
{
    int n = array.dim();
    
    if (order == ASCENDING)
    {
        for (int i = n-1; i > 0; i--)
        {
            for (int j = 0; j < i; j++)
            {
                if (array[j] > array[j+1])
                {
                    T temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }    
            }    
        }    
    }
    else if (order == DESCENDING)
    {
        for (int i = n-1; i > 0; i--)
        {
            for (int j = 0; j < i; j++)
            {
                if (array[j] < array[j+1])
                {
                    T temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }    
            }    
        }
    }        
    
    return;
}

template < class T >
void mergeSort(TNT::Array1D< T > array, Order order, int first, int last)
{
    if (first >= last)
        return;
    
    int bound1 = (first + last)/2;
    mergeSort(array, order, first, bound1);
    mergeSort(array, order, bound1 + 1, last);
    
    int sortSize = last - first + 1, p = first, q = bound1 + 1, mark = 0;
    TNT::Array1D< T > subArray(sortSize);
    
    while (mark < sortSize && order == ASCENDING)
    {
        if (array[p] < array[q] && p <= bound1 && q <= last)
        {
            subArray[mark] = array[p];
            p++;
        }    
        else if (array[q] <= array[p] && p <= bound1 && q <= last)
        {
            subArray[mark] = array[q];
            q++;
        }   
        else if (p > bound1)
        {
            subArray[mark] = array[q]; 
            q++;
        }
        else if (q > last)
        {
            subArray[mark] = array[p];
            p++;    
        }    
        
        mark++;
    }
    
    while (mark < sortSize && order == DESCENDING)
    {
        if (array[p] > array[q] && p <= bound1 && q <= last)
        {
            subArray[mark] = array[p];
            p++;
        }    
        else if (array[q] >= array[p] && p <= bound1 && q <= last)
        {
            subArray[mark] = array[q];
            q++;
        }   
        else if (p > bound1)
        {
            subArray[mark] = array[q]; 
            q++;
        }
        else if (q > last)
        {
            subArray[mark] = array[p];
            p++;    
        }    
        
        mark++;
    }
    
    for (int i = first; i <= last; i++)
        array[i] = subArray[i - first];
        
        
    return;
}    

} // End if namespace brace.

#endif // __T_SORT_H__

---