1 /* 2 * Copyright (C) 2001, 2002, and 2003 Roy Keene 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation; either version 2 7 * of the License, or (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 17 * 18 * email: dact@rkeene.org 19 */ 20 21 22 #include "dact.h" 23 #include "sort.h" 24 #ifdef HAVE_STDLIB_H 25 #include <stdlib.h> 26 #endif 27 #ifdef HAVE_STRING_H 28 #include <string.h> 29 #endif 30 #include <stdio.h> 31 32 33 /* 34 Bubble Sort 35 */ 36 void int_sort (uint32_t array[], unsigned int listsize, int mode) { 37 uint32_t *mod_array=NULL; 38 unsigned int temp,i,j; 39 40 mode=(!!mode); 41 42 if (mode) { 43 mod_array=malloc(listsize*sizeof(uint32_t)); 44 for (i=0;i<listsize;i++) mod_array[i]=i; 45 } 46 47 for (i=0;i<(listsize);i++) { 48 for (j=0;j<(listsize-1);j++) { 49 if (array[j] < array[j+1]) { 50 temp = array[j]; 51 array[j] = array[j+1]; 52 array[j+1] = temp; 53 switch (mode) { 54 case 0 : break; 55 case 1 : 56 temp=mod_array[j]; 57 mod_array[j]=mod_array[j+1]; 58 mod_array[j+1]=temp; 59 } 60 } 61 } 62 } 63 64 if (mode) { 65 memcpy(array, mod_array, listsize*sizeof(uint32_t)); 66 free(mod_array); 67 } 68 69 } 70 71 72 /* 73 I have no idea what this sort is called, if it has a name 74 (I just made one that I thought would work well.) 75 */ 76 void int_sort_fast (uint32_t array[], unsigned int elements, int mode) { 77 uint32_t *hold_array; 78 uint32_t *mod_array=NULL; 79 unsigned int i, x, cnt=0; 80 unsigned char sizeint=sizeof(uint32_t); 81 82 83 mode=(!!mode); 84 85 hold_array=calloc((elements+1),sizeint); 86 if (mode) { 87 mod_array=malloc(elements*sizeint); 88 for (i=0;i<elements;i++) mod_array[i]=i; 89 } 90 91 for (i=0;i<elements;i++) { 92 if (array[i]==0) continue; 93 for (x=0;x<cnt+1;x++) { 94 if (array[i] > hold_array[x]) { 95 if (x<cnt) { 96 memmove(hold_array+x+1,hold_array+x,(cnt-x+1)*sizeint); 97 } 98 hold_array[x]=array[i]; 99 switch (mode) { 100 case 0: break; 101 case 1: 102 memmove(mod_array+x+1,mod_array+x,(cnt-x+1)*sizeint); 103 mod_array[x]=i; 104 } 105 break; 106 } 107 } 108 cnt++; 109 } 110 111 if (mode) { 112 memcpy(array,mod_array,elements*sizeint); 113 free(mod_array); 114 } else { 115 memcpy(array,hold_array,elements*sizeint); 116 } 117 free(hold_array); 118 } 119 120 121 /* 122 123 Sort really quickly 124 125 */ 126 void int_sort_really_fast (uint32_t array[], unsigned int elements, int mode) { 127 uint16_t list_items[0x10000]; 128 /* uint16_t list_items[0x10000][0x10001]; */ 129 int i,f=0,m; 130 131 132 memset(list_items,0,sizeof(list_items)); 133 134 for (i=0;i<elements;i++) { 135 list_items[array[i]]++; 136 } 137 138 for (i=0xffff;i;i--) { 139 if (list_items[i]!=0) { 140 for (m=0;m<list_items[i];m++) array[f++]=i; 141 } 142 } 143 144 return; 145 } |