Revisions to Sort string's characters into alphabetic order

Although counting sort is a degenerate radix sort, they are usually considered distinct. So remove the confusion.

Source Link

edited Jul 16, 2018 at 7:48

88.7k
14
104
327

There is of course a much faster sorting for char, namely counting sort, also known as radix sort. This is only O(n) instead of O(n log n):

#include <array>
#include <string>
#include <climits>
#include <vector>

std::string AlphabetSoup(const std::string& text) {
    std::array<std::size_t, UCHAR_MAX> count{};

    for (unsigned char letter : text) {
        ++count[letter];
    }

    std::vector<char> v;
    v.reserve(text.size());

    char letter { 0 };
    for (int cnt : count) {
        v.insert(v.end(), cnt, letter++);
    }
    return {v.begin(), v.end()};
}

There is of course a much faster sorting for char, namely counting sort, also known as radix sort. This is only O(n) instead of O(n log n):

#include <array>
#include <string>
#include <climits>
#include <vector>

std::string AlphabetSoup(const std::string& text) {
    std::array<std::size_t, UCHAR_MAX> count{};

    for (unsigned char letter : text) {
        ++count[letter];
    }

    std::vector<char> v;
    v.reserve(text.size());

    char letter { 0 };
    for (int cnt : count) {
        v.insert(v.end(), cnt, letter++);
    }
    return {v.begin(), v.end()};
}

There is of course a much faster sorting for char, namely counting sort. This is only O(n) instead of O(n log n):

#include <array>
#include <string>
#include <climits>
#include <vector>

std::string AlphabetSoup(const std::string& text) {
    std::array<std::size_t, UCHAR_MAX> count{};

    for (unsigned char letter : text) {
        ++count[letter];
    }

    std::vector<char> v;
    v.reserve(text.size());

    char letter { 0 };
    for (int cnt : count) {
        v.insert(v.end(), cnt, letter++);
    }
    return {v.begin(), v.end()};
}

Fix the code

Source Link

edited Jul 13, 2018 at 14:44

Toby Speight

88.7k
14
104
327

There is of course a much faster sorting for char, namely counting sortcounting sort, also known as radix sort. This is only O(n) instead of O(n log n).

concept code:

#include <array>
#include <string>
#include <climits>
#include <vector>

std::array<intstring AlphabetSoup(const std::string& text) {
    std::array<std::size_t, 256>UCHAR_MAX> count;count{};

    for (unsigned char letter : text) {
  count[letter]++;      ++count[letter];
    }

    std::vector<char> v;
    v.reserve(text.size());

    char letter { 0 };
    for (int cnt : count) {
        v.insert(v.end(), cnt, letter++);
    }
    return {v.begin(), v.end()};
}

There is of course a much faster sorting for char namely counting sort. This is only O(n) instead of O(n log n).

concept code

std::array<int, 256> count;

for(char letter : text) {
  count[letter]++;
}

std::vector<char> v;
v.reserve(text.size());

char letter { 0 };
for(int cnt : count) {
  v.insert(v.end(), cnt, letter++);
}

There is of course a much faster sorting for char, namely counting sort, also known as radix sort. This is only O(n) instead of O(n log n):

#include <array>
#include <string>
#include <climits>
#include <vector>

std::string AlphabetSoup(const std::string& text) {
    std::array<std::size_t, UCHAR_MAX> count{};

    for (unsigned char letter : text) {
        ++count[letter];
    }

    std::vector<char> v;
    v.reserve(text.size());

    char letter { 0 };
    for (int cnt : count) {
        v.insert(v.end(), cnt, letter++);
    }
    return {v.begin(), v.end()};
}

deleted 9 characters in body

Source Link

edited Jul 13, 2018 at 14:29

Surt

590
4
10

There is of course a much faster sorting for char namely counting sort. This is only O(n) instead of O(n log n).

concept code

std::array<int, 256> count;

for(char letter : text) {
  count[letter]++;
}

std::vector<char> v;
v.reserve(text.size());

for(int cnt :char count)letter {
  0 };
for(charint lettercnt : cntcount) {
    v.emplace_backinsert(letterv.end();
, cnt, }letter++);
}

There is of course a much faster sorting for char namely counting sort. This is only O(n) instead of O(n log n).

concept code

std::array<int, 256> count;

for(char letter : text) {
  count[letter]++;
}

std::vector<char> v;
v.reserve(text.size());

for(int cnt : count) {
   for(char letter : cnt) {
    v.emplace_back(letter);
  }
}

There is of course a much faster sorting for char namely counting sort. This is only O(n) instead of O(n log n).

concept code

std::array<int, 256> count;

for(char letter : text) {
  count[letter]++;
}

std::vector<char> v;
v.reserve(text.size());

char letter { 0 };
for(int cnt : count) {
  v.insert(v.end(), cnt, letter++);
}

Source Link

answered Jul 13, 2018 at 5:06

Surt

590
4
10

Loading

Stack Exchange Network

Return to Answer