Ask a CPP algorithm for mixed sorting of numbers and characters.

ask for an algorithm for mixed sorting of numbers and characters in CPP.

input is a string array, all elements are essentially string, such as [2, Banana, 1, Apple, 3, Pear] . Now sort it, requiring that the sorted output be [1, Apple, 2, Banana, 3, Pear] . In short, it is the sorting of numbers and numbers, the sorting of characters and characters, it turns out that the position of string is the position of string, and the position of integer is integer (in other words, all elements are essentially string, but some of them are in digital form).

I think it is necessary to determine whether a string is a number or not. CPP should be able to use:: isdigit directly, right? But excuse me, how should I implement where string is originally string and integer where integer is ?

maybe you can use heap sorting to implement this algorithm. So ask another question about the definition of the minimum heap priority_queue. 

struct cmp
    {
    bool operator () (int a, int b)
        { return a>b; }
    };
void heaping1()
    {
    priority_queue<int, vector<int>, cmp> pq;

the definition of priority_queue in this way can be compiled. However, if you change to the following definition: 

void heaping2()
    {
    priority_queue<pair<int, char>, cmp> pq;

in this way, the definition of priority_queue cannot be compiled! Of course, if you delete the cmp and change it to the maximum heap, then everything will be fine. So, how should the minimum heap in the above function be defined? where should I put the cmp? Thank you first!

Heap sort cPP
Mar.02,2021

my idea is to first use an array to mark whether the corresponding position is a number or a string, for example, for [2, Banana, 1, Apple, 3, Pear], there are [0 Banana, 1], then sort the numbers and strings into two arrays nums and strings, and then put the appropriate elements according to the representation array.

the main idea of this question is to use the original address sort, such as fast row,

  • at the same time, all your operations on iterators / or pointers have to be overloaded, for example, when the pointer is sorted, the meaning of the pointer plus one becomes the pointer to find the next number.
  • sorts twice, the first number and the second string.

I have implemented a custom iterator here, and then sort it with std::sort . You can also implement fast scheduling yourself, which may be easier, of course, but be careful with the boundaries. 

-sharpinclude <iterator>
-sharpinclude <iostream>
-sharpinclude <cctype>
-sharpinclude <algorithm>

bool sortNum = true;
bool isNum(const char* num)
{
    while (*num)
    {
        if (!std::isdigit(*num))
            return false;
        PPnum;
    }
    return true;
}

class Myiter :public std::iterator<std::random_access_iterator_tag,const char *>
{
    
    const char** ptrStr_= nullptr;
    const char** end_ = nullptr;
    const char** begin_ = nullptr;
public:
    explicit Myiter(const char** ptr=nullptr):ptrStr_(ptr) {}
    Myiter(const Myiter& that) :ptrStr_(that.ptrStr_),end_(that.end_) {}
    Myiter& setEnd(const char** end) { end_ = end; return *this; }
    Myiter& setBegin(const char** begin) { begin_ = begin; return *this; }

    Myiter& operatorPP()
    {
        PPptrStr_;
        while ( ptrStr_!= end_)
        {
            auto str = *ptrStr_;
            if (sortNum)
            {
                if (isNum(*ptrStr_))
                    return *this;
            }
            else
            {
                if (!isNum(*ptrStr_))
                    return *this;
            }
            PPptrStr_;
        }
        return *this;
    }

    Myiter operatorPP(int)
    {
        Myiter tmp(*this);
        PPtmp;
        return tmp;
    }

    Myiter& operator+=(difference_type n)
    {
        while (--n != 0)
            PP*this;
        return *this;
    }

    Myiter operator+(difference_type n)
    {
        Myiter tmp(*this);
        tmp += n;
        return tmp;
    }

    Myiter& operator--()
    {
        while (--ptrStr_!=begin_)
        {
            auto str = *ptrStr_;
            if (sortNum)
            {
                if (isNum(*ptrStr_))
                    return *this;
            }
            else
            {
                if (!isNum(*ptrStr_))
                    return *this;
            }
        }
        return *this;
    }

    Myiter operator--(int)
    {
        Myiter tmp(*this);
        --tmp;
        return tmp;
    }

    Myiter& operator-=(difference_type n)
    {
        while (--n != 0)
            --*this;
        return *this;
    }

    Myiter operator-(difference_type n)
    {
        Myiter tmp(*this);
        tmp -= n;
        return tmp;
    }

    reference operator*() const { return *ptrStr_; }
    bool operator!=(const Myiter& that) { return ptrStr_ != that.ptrStr_; }
    bool operator==(const Myiter& that) { return ptrStr_ == that.ptrStr_; }
    bool operator<(const Myiter& that) { return ptrStr_ < that.ptrStr_; }
    bool operator>(const Myiter& that) { return ptrStr_ > that.ptrStr_; }
    bool operator<=(const Myiter& that) { return ptrStr_ <= that.ptrStr_; }
    bool operator>=(const Myiter& that) { return ptrStr_ >= that.ptrStr_; }
    difference_type operator-(const Myiter& that)
    {
        Myiter tmp(that);
        difference_type n = 0;
        while ((*this)!= tmp)
        {
            PPn;
            PPtmp;
        }
        return n;
    }
};

template<size_t N>
void sortAndPrint(const char* (&test)[N] )
{
    std::cout << "Before sort:\n";
    for (auto i : test)
    {
        std::cout << i << " ";
    }
    std::cout << "\n";
    auto size = N;
    auto end = test + size;
    auto begin = test;
    auto startNum = test;
    auto startStr = test;
    bool gotStartNum = false;
    bool gotStartStr = false;
    for (; begin != end; PPbegin)
    {
        if (gotStartNum&&gotStartStr) break;

        if (isNum(*begin))
        {
            if (gotStartNum) continue;
            startNum = begin;
            gotStartNum = true;
        }
        else
        {
            if (gotStartStr) continue;
            startStr = begin;
            gotStartStr = true;
        }
    }
    sortNum = true;
    std::sort(Myiter(startNum).setBegin(startNum).setEnd(end), Myiter(end).setBegin(startNum).setEnd(end), [](const char* a, const char *b)
    {
        auto aNum = atoi(a);
        auto bNum = atoi(b);
        return aNum < bNum;
    });
    sortNum = false;
    std::sort(Myiter(startStr).setBegin(startStr).setEnd(end), Myiter(end).setBegin(startStr).setEnd(end), [](const char* a, const char *b)
    {
        return strcmp(a, b) < 0;
    });
    std::cout << "After sort:\n";
    for (auto i : test)
    {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

int main()
{
    const char * test[] = { "3","1","Charlie","Alpha","Bravo" };
    const char * test2[] = { "2", "Banana", "1", "Apple", "3", "Pear" };
    sortAndPrint(test);
    sortAndPrint(test2);
    system("PAUSE");
}

sort

it's too easy to use inplace (sort directly into two arrays and then merge). If you want inplace, you can actually write a wrapper of reference without handwriting iterator, (and then directly call any regular inplace sorting algorithm): 

-sharpinclude <iostream>
-sharpinclude <sstream>
-sharpinclude <algorithm>
-sharpinclude <string>
-sharpinclude <vector>

using namespace std;

template <typename T>
class Ref {
  T & t;

public:

  Ref(T & t) : t(t) {
  }

  Ref(Ref & o) : t(o.t) {
  }

  Ref(Ref && o) : t(o.t) {
  }

  Ref & operator = (Ref & o) {
    t = o.t;
    return *this;
  }

  Ref & operator = (Ref && o) {
    t = move(o.t);
    return *this;
  }

  bool operator < (Ref const & o) const {
    return t < o.t;
  }

  friend void swap(Ref & a, Ref & b) {
    using std::swap;
    swap(a.t, b.t);
  }
};

void solution(vector<string> & ret) {
  vector<Ref<string>> a;
  vector<Ref<string>> b;

  for (auto & c : ret) {
    bool numeric = true;
    for (auto const & d : c) {
      if (!isdigit(d)) numeric = false;
    }
    if (numeric) a.emplace_back(c); else b.emplace_back(c);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  vector<string> v;

  string l;
  getline(cin, l);

  stringstream ss;
  ss << l;

  string s;
  while (ss >> s) {
    v.emplace_back(move(s));
  }

  solution(v);

  bool first = true;
  for (auto const & c : v) {
    if (first) first = false; else cout.put(' ');
    cout << c;
  }
  cout << '\n';
}

Test:

enter

2 Banana 1 Apple 3 Pear

output

1 Apple 2 Banana 3 Pear

Previous: Router's problem Cannot read property 'location' of undefined

Next: Android bottom navigation bar, highlight the button shadow part how to deal with

css mysql arrays josn react html typescript webpack npm sass R objective-c .net sql-server jquery python-3.x angularjs django angular excel regex iphone ajax linux xml pandas vba spring database wordpress string wpf xcode windows bash postgresql oracle multithreading eclipse list firebase algorithm macos forms image scala visual-studio azure bootstrap spring-boot react-native python-2.7 docker performance function winforms matlab powershell apache dataframe api sqlite numpy rest shell selenium flutter dart maven loops qt swing android-studio csv express file class tensorflow sorting codeigniter perl
© 2021 CodesHelper
Advertising Contact us About us
Menu