using sort in C++ to sort a string starting from 2nd character to last character

Question

I want to sort a string starting from the 2nd character to the last character. Currently I am able to sort the string as per my requirement but I want to utilize sort function in C++ to achieve the same

Sample input:

san test van best

Sample output:

san van test best

My current program

for (int i1 = 0; i1 < n; ++i1) {
    for (int j1 = i1 + 1; j1 < n; ++j1) {
        temp5 = arr[j1].substr(1, arr[j1].length() - 1);
        temp6 = arr[i1].substr(1, arr[i1].length() - 1);
        if (temp6.compare(temp5) > temp5.compare(temp6)) {
            a = arr[i1];
            arr[i1] = arr[j1];
            arr[j1] = a;
        }
    }
}

Judging from your sample I/Os you don't just want to sort a string (which would mean its characters). You want to tokenize it, sort the substrings and concat them back into a new string. — m88, Feb 19 '21 at 08:52
Your code doesn't "sort a string starting from 2 character to last character". It tries to sort an array of strings ignoring the first character, although I think that `if (temp6.compare(temp5) > temp5.compare(temp6))` is wrong. So what do you actually want your code to do? — stefaanv, Feb 19 '21 at 08:53
I'ts a bit unclear to me what you're after, you may want to consider using `std::partial_sort`. — anastaciu, Feb 19 '21 at 08:53
i want to sort the string array ignoring the first character — psaraj12, Feb 19 '21 at 09:03

Arty · Accepted Answer · 2021-02-19T10:11:54.250

4

std::sort(std::begin(arr), std::end(arr),
    [](std::string_view const & l, std::string_view const & r){
        return l.substr(1) < r.substr(1);
    }
);

Full working example:

Try it online!

#include <string_view>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

int main() {
    std::string arr[] = {"san", "test", "van", "best"};
    std::sort(std::begin(arr), std::end(arr),
        [](std::string_view const & l, std::string_view const & r){
            return l.substr(1) < r.substr(1);
        }
    );
    for (auto const & s: arr)
        std::cout << s << " ";
}

Output:

san van test best

edited Feb 19 '21 at 10:11

answered Feb 19 '21 at 08:53

Arty

14,883
6
36
69

`std::string_view` would avoid making copies. – Quimby Feb 19 '21 at 08:55
`auto const&` would not have copied either, but it wouldn't have enabled using `substr()` if sorting a collection of C strings. – underscore_d Feb 19 '21 at 09:00
3

@underscore_d I thought actually by "copying" Quimby meant actually that substr() makes a copy of string. While string_view's substr() doesn't make a copy. – Arty Feb 19 '21 at 09:01
@Arty thanks for the solution but i am getting the below error error: request for member ‘begin’ in ‘arr’, which is of non-class type ‘std::__cxx11::string [n] {aka std::__cxx11::basic_string [n]}’ std::sort(arr.begin(), arr.end(), [](auto const & l, auto const & r) – psaraj12 Feb 19 '21 at 09:02
@psaraj12 Can you please show me how your `arr` is declared? Variable of what type? See my full example in answer, I use std::vector as array. And what use you? – Arty Feb 19 '21 at 09:06
@Arty string arr[n]; – psaraj12 Feb 19 '21 at 09:06
@psaraj12 I corrected my answer to reflect changes needed to work with your kind of array! Please put a look. – Arty Feb 19 '21 at 09:08
@Arty thanks once again for the effort "i am getting array input using cin " i am getting the below error on the latest code error: no matching function for call to ‘begin(std::string [n])’ 67 | std::sort(std::begin(arr), std::end(arr), – psaraj12 Feb 19 '21 at 09:17
@psaraj12 Try doing `#include `, if doesn't work then instead of `std::begin(arr), std::end(arr)` put `&arr[0], &arr[n]` where `n` is number of elements in array. – Arty Feb 19 '21 at 09:19
for n=20000 this solution gave a performance boost of completion within 0.07 seconds compared to 2+ seconds with my solution – psaraj12 Feb 19 '21 at 10:41
@psaraj12 This is small boost, only because you tested on to small data. Your algorithm is bubble sort algorithm which takes `O(N^2)` time, standard std::sort has quick-sort algorithm which is `O(N Log(N))` so much faster. But this speedup will be only on large data. Try generating random strings around 1 million and test, std::sort should be much faster! – Arty Feb 19 '21 at 10:43
@psaraj12 Ah, sorry, you say that std::sort is 0.07 seconds and yours is 2 seconds. So it gives a great boost already! Sorry for mistake. – Arty Feb 19 '21 at 10:43
1

I considered `std::stable_sort`, but the single test case is insufficient to show it's needed. – MSalters Feb 19 '21 at 13:28
@MSalters I thought `std::sort` is stable. It is not? What algorithm does it use? Not Quick-Sort? Isn't quick-sort stable? – Arty Feb 19 '21 at 14:37
@Arty: quicksort definitely is not stable. `std::sort` these days typically is not exactly quicksort, to avoid degenerate performance for almost-sorted data. But these quicksort-like implementations still are not stable. – MSalters Feb 19 '21 at 15:59
@Arty I think the common standard library implementations use [Introsort](https://en.wikipedia.org/wiki/Introsort), an unstable hybrid sorting algorithm. – Blastfurnace Feb 19 '21 at 16:04
@Arty A note about your lambda expressions, `std::string_view` is a **small** object so it's probably not useful to take them by const-reference. You can pass them around by value. – Blastfurnace Feb 19 '21 at 16:10
@Blastfurnace In C++ any const reference is almost always not more expensive than regular object. Reference either is same expensiveness or cheaper. As I saw many times in assembler code of C++ program, usually for compiler there is no difference to have simple type or reference to that type, in both cases same assembler code is generated. But if class has more than one field or non-simple-type fields then reference is always cheaper. And string_view has at least two fields - pointer and size. So using reference should be cheaper or same on average for string_view. – Arty Feb 19 '21 at 16:22
It's debatable but I think the current best practice is to pass view objects by value. There are many discussions about this but here are two examples: https://stackoverflow.com/questions/27256377/c-view-types-pass-by-const-or-by-value and https://abseil.io/tips/1 – Blastfurnace Feb 19 '21 at 16:30

using sort in C++ to sort a string starting from 2nd character to last character

1 Answers1