qsort.c (2207B)
1 /* -*-comment-start: "//";comment-end:""-*- 2 * GNU Mes --- Maxwell Equations of Software 3 * Copyright © 2017,2018 Jan (janneke) Nieuwenhuizen <janneke@gnu.org> 4 * Copyright © 2021 Paul Dersey <pdersey@gmail.com> 5 * 6 * This file is part of GNU Mes. 7 * 8 * GNU Mes is free software; you can redistribute it and/or modify it 9 * under the terms of the GNU General Public License as published by 10 * the Free Software Foundation; either version 3 of the License, or (at 11 * your option) any later version. 12 * 13 * GNU Mes is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with GNU Mes. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 22 #include <stdlib.h> 23 #include <string.h> 24 25 void 26 qswap (void *a, void *b, size_t size) 27 { 28 char *pa = a; 29 char *pb = b; 30 do 31 { 32 char tmp = *pa; 33 *pa++ = *pb; 34 *pb++ = tmp; 35 } while (--size > 0); 36 } 37 38 size_t 39 qpart (void *base, size_t count, size_t size, int (*compare) (void const *, void const *)) 40 { 41 void *p = base + count * size; 42 size_t i = 0; 43 for (size_t j = 0; j < count; j++) 44 { 45 int c = compare (base + j * size, p); 46 if (c < 0) 47 { 48 #if 1 //__x86_64__ 49 qswap (base + i * size, base + j * size, size); 50 #else 51 int p1 = base + i * size; 52 int p2 = base + j * size; 53 qswap (p1, p2, size); 54 #endif 55 i++; 56 } 57 else if (c == 0) 58 i++; 59 } 60 if (compare (base + count * size, base + i * size) < 0) 61 qswap (base + i * size, base + count * size, size); 62 return i; 63 } 64 65 void 66 qsort (void *base, size_t count, size_t size, int (*compare) (void const *, void const *)) 67 { 68 if (count > 1) 69 { 70 int p = qpart (base, count - 1, size, compare); 71 qsort (base, p, size, compare); 72 #if 1 //__x86_64__ 73 qsort (base + p * size, count - p, size, compare); 74 #else 75 int p1 = base + p * size; 76 int p2 = count - p; 77 qsort (p1, p2, size, compare); 78 #endif 79 } 80 }