Главная Язык Си (консольные) » Файлы » Выполненные работы » Язык Си (консольные) [ Добавить материал ]

Алгоритм MSD-поразрядной сортировки реализованный на C++ (для строк)

Данный исходный код программы является работающие реализацией алгоритма 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);

template <class Item>
void compexch(Item &A, Item &B);

template <class Item>
void insertion(Item a[], int l, int r);

int _tmain(int argc, _TCHAR* argv[])
{
  // Сортируемый массив строк
  string x[15] = {"aza", "aba", "aab", "aad", "zba", "aac", "abd", "zzg", "zbz", "zze", "aag", "aaf", "abx", "zba", "aac"};

  radixMSD<string>( &x[0], 0, 14, 0 );

  for( int i=0; i < 15; i++ )
  {
    //printf("%s ", x[i]);
    cout << x[i].c_str() << " ";
  }

  getch();
  return 0;
}

static string aux[15];

template <class Item>
void radixMSD(Item a[], int l, int r, int d)
{
  int i, j, count[R + 1];  

  if (d < bytesword)  
  {
    if ( r - l <= 3 )
    {
      insertion(a, l, r);  
    }
    else
    {
      for (j = 0; j < R+1; j++)  
      {
        count[j] = 0;
      }

      for (i = l; i <= r; i++)  
      {
        count[a[i][d] + 1 - 'a']++;
      }

      for (j = 1; j < R; j++)
      {
        count[j] += count[j-1];
      }

      for (i = l; i <= r; i++)
      {
        int tmp = count[a[i][d] - 'a']++;
        aux[tmp] = a[i];
      }

      for (i = l; i <= r; i++)
      {
        a[i] = aux[i-l];
      }
   
      radixMSD(a, l, l+count[0]-1, d+1 );

      for (j = 0; j < R-1; j++)
      {
        radixMSD(a, bin(j), bin(j+1)-1, d+1);
      }
    }
  }
}

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);
}

Вот такой "замечательный" и "понятный" код :) Остальные функции сможете найти в его книге, либо в цифровом приложении к ней (но учтите, что там практически невозможно разобраться без комментариев из книги).

Надеюсь, что помог :)

Добавил: COBA (31.12.2010) | Категория: Язык Си (консольные)
Просмотров: 7555 | Загрузок: 0 | Рейтинг: 4.3/6 |
Комментарии (0)
Имя *:
Email *:
Код *: