Идет контрольная по матану, почти конец. Сижу с другом, он что то усиленно и сосредоточенно пишет уже минут десять, вдруг схватившись за голову и с криком "ААааАААаАААаАаА!!, Б**", выбегает из аудитории...
Алгоритм MSD-поразрядной сортировки реализованный на C++ (для строк)
[
]
31.12.2010, 01:54
Данный исходный код программы является работающие реализацией алгоритма MSD-поразрядной сортировки. Код, хочется заметить, некачественный, но работающий, притом в ограниченных рамках. А всё потому что Я его только начал делать, и тут же случайным образом оказалось, что он мне не нужен) Мои наработки могут кому-нибудь пригодиться.
Если брать код как есть, то на входе программы должен быть массив строк по три символа в каждой (не меньше, не больше) и только с использование прописных букв латинского алфавита.
Если Вам нужно, то Вам не должно составить труда модифицировать программу так, чтобы она работала для строк произвольной длины и с любыми другими символами или даже просто числами - целыми или дробными (но для этого нужно будет использовать поразрядный сдвиг несколько раз, вместо простого обращения к букве по её индексу в строке).
Собственно сам код работающей программы:
code.cpp - работающий код сортировки
#include "stdafx.h" #include <conio.h>
#include<iostream> using namespace std;
#define bin(A) l + count[A] static int const bytesword = 3; // Количество разрядов в сравниваемых числах (в данном случае длина сравниваемых строк) static int const R = 26; // Сиситема исчисления сравниваемых чисел (для маленьких букв лактинского алфавита - 26) static int const M = 3; // Подмножества сортируемые вставками
template <class Item> void radixMSD(Item a[], int l, int r, int d);
void insertion(string a[], int l, int r) { int i; for (i = r; i > l; i--) { compexch(a[i-1], a[i]); }
for (i = l+2; i <= r; i++) { int j = i; string v = a[i]; while ( strcmp( v.c_str(), a[j-1].c_str()) < 0 ) { a[j] = a[j-1]; j--; }
a[j] = v; } }
void compexch(string &A, string &B) { if ( strcmp( B.c_str(), A.c_str() ) < 0) { string tmp; tmp = A; A = B; B = tmp; } }
За основу этой программы была взята реализация алгоритма поразрядной сортировки Роберта Седжвика. В его книге также представлен рабочий код, но некоторые функции не дописаны.
В его коде использовались шаблоны функций, чтобы можно было приспособить программу к сортировке любых типов чисел и строк с помощью одной функции. Если Вам нужно будет и если Вы умете использовать шаблоны, то без труда всё допишите. Можете также обратиться к книге "Фундаментальные алгоритмы на C++, Роберт Седжвик, DiaSoft, 2001", раздел 10.3. В частности там Вы сможете найти код функции для сдвига, работающей как для строк, так и для чисел, но возможно придётся покопаться.
На самом деле Седжвик в своей книге писал код "с точки зрения математики", поэтому там достаточно сложно разобраться. К примеру вот "родная" реализация его функции radixMSD:
Функция сортировки MSD Седжвика:
#define bin(A) l+count[A] template <class Item> void radixMSD(Item a[], int l, int r, int d) { int i, j, count[R+1]; static Item aux[maxN]; if (d > bytesword) return; if (r-l <= M) { insertion(a, l, r); return; } for (j = 0; j < R; j++) count[j] = 0; for (i = l; i <= r; i++) count[digit(a[i], d) + 1]++; for (j = 1; j < R; j++) count[j] += count[j-1]; for (i = l; i <= r; i++) aux[count[digit(a[i], d)]++] = a[i]; // Вот эта строчка мне особенно нравится!!! for (i = l; i <= r; i++) a[i] = aux[i-l]; radixMSD(a, l, bin(0)-1, d+1); for (j = 0; j < R-1; j++) radixMSD(a, bin(j), bin(j+1)-1, d+1); }
Вот такой "замечательный" и "понятный" код :) Остальные функции сможете найти в его книге, либо в цифровом приложении к ней (но учтите, что там практически невозможно разобраться без комментариев из книги).
