Алгоритмов сортировки, реализованных на языке C++


Реализован Сортировка Пузырьком, Сортировка Вставками, Сортировка Выбором, Быстрая сортировка, сортировка слиянием и Сортировка Радикс

https://code.google.com/p/medicine-cpp/source/browse/trunk/cpp/sorting/SortingAlgorithms.cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void swap(std::vector<int> & data, int i, int j)
{
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}

void print(std::vector<int> const & data)
{
    std::vector<int>::const_iterator iter = data.begin();

    for (; iter != data.end(); ++iter)
    {
        cout << *iter << " ";
    }

    if (data.size() > 0)
    {
        cout << endl;
    }
}

int generateRandom(int low, int high);
void Shuffle(std::vector<int> & data)
{
    int length = data.size();

    for (int i = 0; i < length-1; ++i)
    {
        swap(data, i, generateRandom(i+1, length-1));
    }

    print(data);
}

int generateRandom(int low, int high)
{
    srand(low);
    int gen = 0;
    gen = rand() % (high - low + 1) + low;
    return gen;
}

//useful for small lists, and for large lists where data is
//already sorted
void BubbleSort(std::vector<int> & data)
{
    int length = data.size();

    for (int i = 0; i < length; ++i)
    {
        bool swapped = false;
        for (int j = 0; j < length - (i+1); ++j)
        {
            if (data[j] > data[j+1])
            {
                swap(data, j, j+1);
                swapped = true;
            }
        }

        if (!swapped) break;
    }
}

//useful for small lists and where swapping is expensive
// does at most n swaps
void SelectionSort(std::vector<int> & data)
{
    int length = data.size();

    for (int i = 0; i < length; ++i)
    {
        int min = i;
        for (int j = i+1; j < length; ++j)
        {
            if (data[j] < data[min])
            {
                min = j;
            }
        }

        if (min != i)
        {
            swap(data, i, min);
        }
    }
}

//useful for small and mostly sorted lists
//expensive to move array elements
void InsertionSort(std::vector<int> & data)
{
    int length = data.size();

    for (int i = 1; i < length; ++i)
    {
        bool inplace = true;
        int j = 0;
        for (; j < i; ++j)
        {
            if (data[i] < data[j])
            {
                inplace = false;
                break;
            }
        }

        if (!inplace)
        {
            int save = data[i];
            for (int k = i; k > j; --k)
            {
                data[k] = data[k-1];
            }
            data[j] = save;
        }
    }
}

void Merge(std::vector<int> & data, int lowl, int highl, int lowr, int highr);
void MergeSort(std::vector<int> & data, int low, int high)
{
    if (low >= high)
    {
        return;
    }

    int mid = low + (high-low)/2;

    MergeSort(data, low, mid);

    MergeSort(data, mid+1, high);

    Merge(data, low, mid, mid+1, high);
}

void Merge(std::vector<int> & data, int lowl, int highl, int lowr, int highr)
{
    int tmp_low = lowl;
    std::vector<int> tmp;

    while (lowl <= highl && lowr <= highr)
    {
        if (data[lowl] < data[lowr])
        {
            tmp.push_back(data[lowl++]);
        }
        else if (data[lowr] < data[lowl])
        {
            tmp.push_back(data[lowr++]);
        }
        else
        {
            tmp.push_back(data[lowl++]);
            tmp.push_back(data[lowr++]);
        }
    }

    while (lowl <= highl)
    {
        tmp.push_back(data[lowl++]);
    }

    while (lowr <= highr)
    {
        tmp.push_back(data[lowr++]);
    }

    std::vector<int>::const_iterator iter = tmp.begin();

    for(; iter != tmp.end(); ++iter)
    {
        data[tmp_low++] = *iter;
    }
}

int Partition(std::vector<int> & data, int low, int high);
void QuickSort(std::vector<int> & data, int low, int high)
{
    if (low >= high) return;

    int p = Partition(data, low, high);

    QuickSort(data, low, p-1);
    QuickSort(data, p+1, high);
}

int Partition(std::vector<int> & data, int low, int high)
{
    int p = low;
    for (int i = p+1; i <= high; ++i)
    {
        if (data[i] < data[p])
        {
            swap(data, i, p);
            if (i != p+1)
            {
                swap(data, i, p+1);
            }
            p = p + 1;
        }
    }

    return p;
}

//O(kN) k is max number of digits
int findMaxDigits(std::vector<int> & data);
void PutInQueues(std::queue<int>  q[], int qcount, std::vector<int> & data, int digit);
void GetPartialSorted(std::queue<int>  q[], int qcount, std::vector<int> & data);

void RadixSort(std::vector<int> & data)
{
  std::queue<int> q[10];
  int maxDigits = findMaxDigits(data);

  for (int i = 0; i < maxDigits; ++i)
    {
      PutInQueues(q, 10, data, i+1);
      data.clear();
      GetPartialSorted(q, 10, data);
    }
}

int getDigitAt(int n, int digit);
void PutInQueues(std::queue<int>  q[], int qcount, std::vector<int> & data, int digit)
{
  std::vector<int>::const_iterator iter = data.begin();
  for(; iter != data.end(); ++iter)
    {
      int qpos = getDigitAt(*iter, digit);
      q[qpos].push(*iter);
    }
}

int getDigitAt(int n, int digit)
{
  int dig = 0;
  while (digit--)
    {
      dig = n % 10;
      n = n / 10;
    }
  return dig;
}

void GetPartialSorted(std::queue<int>  q[], int qcount, std::vector<int> & data)
{
  for (int i = 0; i < qcount; ++i)
    {
      if (q[i].size() > 0)
        {
          int length = q[i].size();
          while (length--)
            {
              data.push_back(q[i].front());
              q[i].pop();
            }
        }
    }
}

int numDigits(int n);
int findMaxDigits(std::vector<int> & data)
{
  std::vector<int>::const_iterator iter = data.begin();
  int max = 0;
  for (; iter != data.end(); ++iter)
    {
      int numd = numDigits(*iter);
      if (max < numd)
        {
          max = numd;
        }
    }

  return max;
}

int numDigits(int n)
{
  int count = 0;
  while(n != 0)
    {
      n = n/10;
      ++count;
    }

  return count;
}

int main()
{
    int a[] = {5, 6, 1, 2, 0, 8, -1, -2, 8, 0};
    std::vector<int> data(a, a + sizeof(a)/sizeof(int));

    //Bubble sort
    BubbleSort(data);
    print(data);

    //Selection sort
    Shuffle(data);
    SelectionSort(data);
    print(data);

    //Insertion sort
    Shuffle(data);
    InsertionSort(data);
    print(data);

    //Merge sort
    Shuffle(data);
    MergeSort(data, 0, data.size()-1);
    print(data);

    //Quick sort
    Shuffle(data);
    QuickSort(data, 0, data.size()-1);
    print(data);

    //Radix Sort
    int b[] = {123, 6, 24, 4567, 45, 989834, 98, 23, 8, 0};
    std::vector<int> rdata(b, b + sizeof(b)/sizeof(int));
    RadixSort(rdata);
    print(rdata);

    return 0;
}


41433
7
задан 4 сентября 2011 в 02:09 Источник Поделиться
Комментарии
3 ответа

Начиная с (близко к) верху, большинство печати в основном только несколько калек имитация СТД::копирование с использованием std::ostream_iterator в качестве назначения. Я не волнуюсь о его существовании вообще, но если вы собираетесь иметь его, я бы использовал что-то вроде этого:

void print(std::vector<int> const &data) { 
if (!data.empty())
copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
}

Хотя она редко вызывает большое значение, также обратите внимание, что если вы просто проверка на пустые/непустые, используя х.пустая() , как правило, предпочтительнее х.функция count()!=0.

Добраться до GenerateRandom() и перемешать, @Тукс-D есть что-то, но он заявил, что это неправильно.

Кстати ты использовал srand , кажется, не очень разумно, но в некоторых случаях (вероятно, в том числе и этот) он может/имеет смысл называть это чаще чем один раз в определенной программе. В этом случае, он делает хоть какой-то смысл для начала каждого рода алгоритм с точно такой же входной последовательности. Для этого, однако, вы хотите, чтобы повторно семя генератора случайных чисел один раз перед созданием каждой последовательности (и использовать то же значение каждый раз). Как @Тукс-D также указал (а правильно, в данном случае) вы обычно хотите сделать это с std::random_shuffle. random_shuffle принимает случайных чисел, генерирующий объект в качестве параметра, так что вы обычно хотите написать небольшой класс, который называет srand, а также оператор() , который обеспечивает случайных чисел.

Попадая в пузырь-вроде, есть один момент стоит упомянуть: это версия с ранних испытаний. Это стоит упомянуть, потому что это рискованно: в то время как он улучшает скорость достаточно много, если данные уже отсортированы (или очень близко к отсортированный) он делает то, что уже алгоритм медленнее, даже в почти всех других случаях. Таким образом, это, как правило, чистый убыток, если данные действительно довольно близко к сортировке.

Для выбора сортировки, наверное, стоит отметить, что в стандартной библиотеке уже есть min_element, так что вы можете уменьшить свой выбор вроде как на что-то вроде:

for (size_t i=0; i<length-1; i++) {
size_t least = std::min_element(&data[i], &data[length]);
swap(&data[i], &data[least]);
}

Сортировка вставками также может быть значительно минимизированы. Основная идея довольно проста:

for (size_t i=1; i<length; i++)
int temp = data[i];
size_t j;
for (j=i; j>0 && temp < data[j-1]; j--)
data[j] = data[j-1];
data[j-1] = temp;
}

Добраться до сортировки, я замечаю две вещи: во-первых, мне кажется, это должно быть написано как функция-объект, с слить как частная функция-член (и заметьте, что то же самое применимо и в других случаях, таких как перегородки как отдельный член функции быстрая сортировка функция объекта). Кроме этого, я все-таки оставил почесал голову интересно, как слияния, в итоге почти 40 строк.

std::vector<int> merge(std::vector<int> &a, std::vector<int> &b) {
std::vector<int> result;
size_t i=0, j=0;
while (i<a.size() && j<b.size())
if (a[i] <= b[j])
result.push_back(a[i++]);
else
result.push_back(b[j++]);
// Copy tail. Only one of these loops will execute per invocation
while (i<a.size())
result.push_back(a[i++]);
while (j<b.size())
result.push_back(b[j++]);
return result;
}

Кроме этого, я бы, наверное, начать с базового класса (вроде, или что-то в этом роде):

struct sort { 
virtual void operator()(std::vector<int> &) = 0;
};

и у каждого рода алгоритм вытекают из этого:

struct bubblesort : sort {
void operator()(std::vector<int> &array) {
// ...
}
};

struct insertionsort : sort {
void operator()(std::vector<int> &array) {
// ...
}
};

// etc.

Затем в главном, вы можете иметь что-то вроде:

sort sorts[] = {bubblesort, insertionsort, selectionsort, mergesort, quicksort};

for (int i=0; i<sizeof(sorts)/sizeof(sorts[0]); i++) {
std::vector<int> data = fill_random(size);

sorts[i](data);
}

7
ответ дан 5 сентября 2011 в 03:09 Источник Поделиться

Стандартные функции

Есть уже стандартный своп.
Нет нужды засорять свой код с одного.

void swap(std::vector<int> & data, int i, int j)

template<typename T>
void std::swap(T& lhs, T& rhs) // Implements optimal swap for T

Ок, ваш алгоритм перетасовки в порядке (лучше, чем большинство людей, которых я вижу, это попробовать). Но опять же есть в стандартной

void Shuffle(std::vector<int> & data)

template<typename Iterator>
void random_shuffle (Iterator first, Iterator last ); // shuffle a container.

Случайных чисел

Генерация случайных nmber.
Никогда не звоните srand() более чем один раз в программу.
Звоните на запись на главной и не раз.

Не изобретать колесо:

int numDigits(int n)

Это просто не реализуем

int numDigits(int n) { return int(log10(n) + 1);}

Имена Переменных

Сделать ваши переменные имена уникальные и легко найти.

for (int i = 0; i < length; ++i)

Вот мне это ужасное имя.
Представьте, что код получает уже на протяжении многих лет, и вы должны поддерживать его. Теперь вам нужно найти все вхождения переменной 'i', чтобы проверить, что они используются в правильное время. Подумайте, сколько подвесной срабатываний поиск на Я собираюсь дать вам.

Также он не дает никаких указаний на его использование.
Мне нравится петля лично (но многие думают, что это ужасно, потому что он не выражает намерения (я не согласен с ними)). Альтернативные варианты будут индексировать, outerLoop и т. д.

Да я и Джей были стандартные имена переменных для целого цикла переменных в Фортране и старые преподаватели, которые не могут выйти из старой практики двигаемся вперед в процессе преподавания современных языков. В реальной жизни, где у вас есть хороший последовательный анализ кода это будет не анализ кода и вы сказали бы идти ее менять (особенно на больших базах кода). Попасть в привычку использовать выразительные имена.

Отступ Стиль

Ваш отступ стиль уникален. Это плохо. Выбрать стиль, который все еще использует (или один из больших религиозных групп), но оставаться последовательным (это также помогает, когда инструменты ввязываться имея уникальный стиль означает, что некоторые инструменты могут не работать так же эффективно для вас).

// Style 1
if (max < numd)
{
max = numd;
}
// Style 2
if (max < numd)
{
max = numd;
}
// Style 3
if (max < numd) {
max = numd;
}
// Not a standard style
if (max < numd)
{
max = numd;
}

И это не совпадает с вашими космическом стиле:

int numDigits(int n)
{
}

10
ответ дан 4 сентября 2011 в 04:09 Источник Поделиться

Это может быть пригодны для что-то вроде домашнего задания упражнение в структуры данных класса, но мое самое большое возражение на это вы привязали все к сортировке совокупность СТД::вектор. Одна из сильных сторон в STL итератор подход и то, что вы можете найти в заголовок заключается в том, что можно довольно легко заменить защитную структуру данных. Если вы укажите данные, которые будут отсортированы как "начало" и "конец" итератор, вы получите все это бесплатно:


  • Сортировка совокупность вектор

  • Сортировка всего диапазона вектор

  • Заменив, что вектор с сырьем, массива c. Сортировка же код работает!

  • ... Или некоторые другие структуры данных, которые вы, возможно, не предусмотрено.

  • Самое главное, быть в состоянии сделать все вышесказанное при производстве двоичный код, который сравнится с тем, что вы пишете делает дженерики в обычный C.

Синтаксис c++ итератор выглядит странным и нелогичным для многих... многих людей, пишущих на C++ не очень понимаю преимущества; я сам пишу на C++ уже давно не получаю его. Я думаю, что поворотным моментом для меня стало чтение Страуструпа по HOPL-III с бумаги; как давний (АБ)пользователей для "С-стиль" в части о STL были полезны для меня, чтобы четко объяснить подход, откуда она берется, и преимущества.

4
ответ дан 5 сентября 2011 в 07:09 Источник Поделиться