#алгоритм #сортировка #cpp
Приведите пример сортировки слиянием на С++.
Ответы
Ответ 1
Еще один пример -- итерационный алгоритм (он же восходящая (bottom-up) сортировка слиянием). Для разнообразия он реализован на Си в template-style (но g++ признает код "своим"). Т.е. программист задает тип данных (и если требуется, функцию сравнения), а препроцессор генерит код для заданного типа данных. Возможно, для начала стоит привести простой пример реализации этого алгоритма для массива int : void merge (int a[], int t[], int i, int l, int n) { int j = i + l, n1 = min(j, n), n2 = min(j + l, n), k = i; while (i < n1 && j < n2) t[k++] = a[i] <= a[j] ? a[i++] : a[j++]; while (i < n1) t[k++] = a[i++]; while (j < n2) t[k++] = a[j++]; } void umsort (int a[], int n) { int *t = (int *)malloc(n * sizeof(int)); int l = 1, i; while (l < n) { for (i = 0; i < n; i += 2 * l) merge(a, t, i, l, n); l *= 2; for (i = 0; i < n; i += 2 * l) merge(t, a, i, l, n); l *= 2; } free(t); } а уже потом показать его же в обобщенном виде. // upmergesort_tmpl.h -- bottom-up merge sort in C at template style #ifndef SORT_NAME #error "Must declare SORT_NAME" #endif #ifndef SORT_TYPE #error "Must declare SORT_TYPE" #endif #ifndef SORT_CMP #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1)) #endif #define SORT_CONCAT(x, y) x ## _ ## y #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y) #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x) // делает имя функции наподобие int_mergesort(), // по которому надо вызывать сортировку #define MERGE_SORT SORT_MAKE_STR(mergesort) #define MERGE SORT_MAKE_STR(merge) #ifdef __cplusplus extern "C" { #endif void MERGE_SORT (SORT_TYPE *dst, const size_t size); #ifdef __cplusplus }; #endif #ifndef SORT_NOCODE_GEN #ifndef MIN #define MIN(x,y) ((x) < (y) ? (x) : (y)) #endif /* Слияние 2-х последовательно расположенных в a[], начиная с индекса start уже упорядоченных массивов, размером size элементов. Результат размещается в tmp[] (тоже с индекса start) n -- размер всего сортируемого массива a[] */ static void MERGE (SORT_TYPE a[], SORT_TYPE tmp[], size_t first, size_t size, size_t n) { size_t second = first + size, // начало второго массива end1 = MIN(second, n), // конец первого массива // (дело тут в том, что второго может и не быть...) end2 = MIN(second + size, n), // конец второго массива i = first; // индекс для текущего элемента результата в tmp[] while (first < end1 && second < end2) tmp[i++] = SORT_CMP(a[first], a[second]) <= 0 ? a[first++] : a[second++]; while (first < end1) // остались элементы первого tmp[i++] = a[first++]; while (second < end2) // или второго tmp[i++] = a[second++]; } void MERGE_SORT (SORT_TYPE *dst, const size_t n) { SORT_TYPE *tmp = (typeof(tmp))malloc(n * sizeof(*tmp)); size_t l = 1, // размер уже упорядоченных подмассивов i; // индекс пары последовательных слияющихся подмассивов // начнем слияние с последовательно расположенных подмассивов // из одного элемента while (l < n) { for (i = 0; i < n; i += 2 * l) MERGE(dst, tmp, i, l, n); // теперь уже отсортированные подмассивы вдвое длинее, но они в tmp[] l *= 2; for (i = 0; i < n; i += 2 * l) MERGE(tmp, dst, i, l, n); // а тут их размер опять удвоился и они уже в нужном месте (в a[]) l *= 2; } free(tmp); } #endif // SORT_NOCODE_GEN #undef SORT_CONCAT #undef SORT_MAKE_STR1 #undef SORT_MAKE_STR А теперь, как этим пользоваться. Предположим, что мы хотим рассортровать аргументы командной строки, рассматривая их как целые и как double числа. Для большего интереса сделаем отдельный файл (единицу компиляции) с функцией сортировки double и функцией real_1000(), которая делает из массива целых массив уменьшенных в 1000 раз double величин (ну, надо же хоть что-то придумать?). Код для сортровки целых (а для полноты картины (или чтобы уж совсем мозг читателю затуманить?)) и код для сортировки Сишных строк сгенерим прямо в main. Тогда получим t.c: #include#define SORT_TYPE double #define SORT_NAME real #include "upmergesort_tmpl.h" // здесь сгененрили код для void real_mergesort(double *, size_t); #ifdef __cplusplus extern "C" { #endif // даже если компилируем g++, то оставим имя по правилам С, // поскольку в main мы предполагаем, что это C код... double *real_1000(int *, int); #ifdef __cplusplus }; #endif double * real_1000 (int a[], int n) { double *d = (typeof(d))malloc(sizeof(*d) * n); int i; for (i = 0; i < n; i++) d[i] = a[i], d[i] /= 1000; return d; } И main (в файле upm_t.c) #include #include #include #define SORT_TYPE int #define SORT_NAME int #include "upmergesort_tmpl.h" // сгенерили код int_mergesort(int *, size_t); #undef SORT_TYPE #undef SORT_NAME #undef SORT_CMP #define SORT_TYPE char * #define SORT_NAME str #define SORT_CMP strcmp #include "upmergesort_tmpl.h" // сгенерили код str_mergesort(char *, size_t) // и задали strcmp() для сравнения элементов #undef SORT_TYPE #undef SORT_NAME #undef SORT_CMP #define SORT_TYPE double #define SORT_NAME real #define SORT_NOCODE_GEN #include "upmergesort_tmpl.h" // сгенерили прототип real_mergesort(double *, size_t) для компилятора #ifdef __cplusplus extern "C" { #endif // предполагаем, что она м.б. откомпилирована gcc -c double *real_1000(int *, int); #ifdef __cplusplus }; #endif int main (int ac, char *av[]) { int a[ac], n = ac - 1, i; for (i = 1; i < ac; i++) a[i - 1] = atoi(av[i]); int_mergesort(a, n); for (i = 0; i < n; i++) printf("%d\n", a[i]); puts("--- sort all argv[] ---"); str_mergesort(av, ac); for (i = 0; i < ac; i++) printf("%s\n", av[i]); puts("-----"); double *d = real_1000(a, n); real_mergesort(d, n); for (i = 0; i < n; i++) printf("%f\n", d[i]); free(d); return puts("End") == EOF; } В результате получим что-то вроде: avp@avp-xub11:hashcode$ g++ -c t1.c avp@avp-xub11:hashcode$ g++ upm_t.c t1.o avp@avp-xub11:hashcode$ ./a.out 1 2 3 iii ./bb aaa -2 -7 -7 -2 0 0 0 1 2 3 --- sort all argv[] --- -2 -7 ./a.out ./bb 1 2 3 aaa iii ----- -0.007000 -0.002000 0.000000 0.000000 0.000000 0.001000 0.002000 0.003000 End avp@avp-xub11:hashcode$ С gcc тоже все ОК. Ответ 2
Сортировка слиянием - это стабильная сортировка, работающая за O(n log n) и использующая O(n) дополнительной памяти. В С++ уже есть стандартный алгоритм std::inplace_merge, который объединяет две сортированные части одной последовательности. При помощи этого алгоритма, нисходящую (top-down) сортировку слиянием можно написать следующим образом: template> void merge_sort(BidirIterator first, BidirIterator last, Compare cmp = {}) { auto n = std::distance(first, last); if (n < 2) return; // Nothing to sort. auto middle = std::next(first, n / 2); merge_sort(first, middle, cmp); merge_sort(middle, last, cmp); std::inplace_merge(first, middle, last, cmp); } Ответ 3
#includetemplate inline void swap( T & arg1, T & arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; }; template inline void merge( std::vector & vArray, std::vector & vTemp, int head, int middle, int tail) { int tmp = 0, lower = head, upper = middle+1; while (lower <= middle && upper <= tail) { if (vArray[lower] < vArray[upper]) { vTemp[tmp++] = vArray[lower++]; } else { vTemp[tmp++] = vArray[upper++]; } } if (lower <= middle) { for(; lower <= middle; vTemp[tmp++] = vArray[lower++]); } else { for(; upper <= tail; vTemp[tmp++] = vArray[upper++]); } int arrayPointer = head; for (tmp = 0; arrayPointer <= tail; vArray[arrayPointer++] = vTemp[tmp++]); } template inline void merge_sort_helper( std::vector & vArray, std::vector & vTemp, int head, int tail) { if(head == tail) { return; } int middle = (head+tail)/2; merge_sort_helper( vArray, vTemp, head, middle); merge_sort_helper( vArray, vTemp, middle+1, tail); merge( vArray, vTemp, head, middle, tail); } template void merge_sort( std::vector & vArray) { std::vector v(vArray.size(), 0); merge_sort_helper( vArray, v, 0, vArray.size()-1); }
Комментариев нет:
Отправить комментарий