- Practice
- Algorithms
- Sorting
- Big Sorting
- Discussions

# Big Sorting

# Big Sorting

MartyMacGyver + 19 comments This problem bugged me because it's a trivial sort and yet the outcomes were markedly different in Python 3.6, depending on how you approach it.

Some speculate that

`sort()`

is faster than`sorted()`

, but these functions are basically the same except the former is an in-place sort (which shouldn't matter here).Edit:

`sorted()`

is a wrapper for`sort()`

. See also: https://stackoverflow.com/questions/1915376/is-pythons-sorted-function-guaranteed-to-be-stableAnalysis with

`cprofile`

kept reporting that`print()`

was the cause of the slowdown, which made no sense at first.It turned out that

`int -> str`

conversions (whether by print or explicitly converting the values first) are surprisingly costly (probably far more costly with huge integers, as test cases #4, #5, and #6 appear to contain). If you're taking the "convert to int, sort, then print" route, you're actually printing ints, which are converted internally to strings for display. And that's why print becomes slow.First, a typical slow implementation (I originally had a longer form for these - the list comprehension here makes it more compact but not noticeably faster):

for i in sorted([int(s) for s in unsorted]): print(i) # int to str = costly

Adding an

`int -> str`

conversion before print doesn't help - in fact, it gets a little bit slower:for i in sorted([int(s) for s in unsorted]): s = str(i) # This is a costly step print(s)

However, using the

`key=int`

sorting argument performs the necessary conversions internally during the sort process itself, while returning the original string values that are quickly printed. (Note that the argument to`key`

is the name of a function that takes one argument, in this case`int()`

.) I'm going to guess that`str -> int`

is much faster than`int -> str`

A fast (challenge-friendly) in-place

`sort()`

:unsorted.sort(key=int) for s in unsorted: print(s)

`sorted()`

is virtually the same speed, and doesn't modify`unsorted`

:for s in sorted(unsorted, key=int): print(s)

For grins, let's make it slow again (in fact, this becomes slowest of all the attempts!):

for s in sorted(unsorted, key=int): i = int(s) # Forces costly int -> str conversion in print() print(i)

More info:

Spectravideo328 + 6 comments And I (regrettably) built my own merge sort, that still failed 3 tests.....

I am starting to think Python can replace C...in some cases...

MartyMacGyver + 0 comments I've programmed in a variety of languages. C++ (particularly more recent versions) is quite powerful... but it is often an unweildy hammer for what should be quick jobs. Likewise, Python isn't perfect - the GIL is still a necessary tradeoff - but it has a wide variety of use cases and it's more concise as well.

(If you actually meant "C" in particular, that's another story.)

msk1361 + 0 comments Don't worry, you are not alone. I did the same.

gogolaygo + 1 comment Same here! Just implemented merge sort and thought I would pass every case. Nope

stephencafferty + 0 comments Same! Thought it would be quicker with merge sort, almost an hour later and I've came to dicussions for inspiration

aaditya_vyas17 + 0 comments Exactly what i did.. still failing 1 test case.. -_-

ishanpandey + 2 comments Yes I did the same, thought Merge can get it through. But I was wrong. Later I realized it can be done in much cleaner way :

def bigSorting(unsorted): return sorted(unsorted,key=int)

mmcss + 2 comments This is my solution, too. I'm using Python 3.7.5 Result for me is timeout on cases 4, 5, and 6. My original solution, "return sorted(unsorted, key=lambda x: (len(x), int(x)))" times out on cases 3, 4, and 5. My solution does not involve int -> str conversion, but still times out. Any suggestions?

daragunshot + 0 comments Yeah I have the exact same problem, I even coded merge sort directly so i could be finiky with my comparisons. I still time out for case 3, 4, and 5.

troncosomath + 1 comment I did something similar but not quite the same. If you try

return sorted(unsorted, key=lambda x: (len(x),x))

it will work. The problem is converting to a int. However, with this approach you never convert and you are just compering the strings.

least_unknown + 0 comments Just to clarify that

`lambda`

part, in case someone else doesn't understand how exactly string comparison works:`'2' > '1'`

is`True`

, but`'2' > '10'`

is also`True`

, as well as`'2' > '1000'`

. That's why the strings are sorted by length first, because`len('2') < len('10')`

.

ABHIJEET_SD + 0 comments it also failed two test cases .-_-. !!

ABHIJEET_SD + 1 comment my merge sort failed 5 test cases !!!!

diasdenny7 + 0 comments This is what you need to do:

**return sorted(sorted(unsorted), key=len)**

Narta + 0 comments Thanks for this explanation, it's very clear.

ch_christofidis + 1 comment How is this making sense?

'using the key=int sorting argument performs the necessary conversions internally during the sort process itself, while returning the original string values that are quickly printed.'

That would still convert the string -> to integer -> back to string. The amount of conversions is actually exactly the same.

Tzalumen + 0 comments no, the sort process is only converting string to int for the purpose of comparing two strings. the original strings are left unconverted and simply reordered in the list. This is a lot cleaner than my successful hamfisted bucket sort.

Another major speedup can be achieved by creating an output string and only calling print() once, since stdout operations seem to have a high cost compared to string concatenation. Specifically there seems to be a significant delay after writing to stdout.

rrajeshwari30 + 0 comments Thank you for the great explanation. My code was timing out for few test cases, it worked with the key=int technique!

sir_suhrab + 4 comments You don't need to convert str to int and back to str. First you sort the list of strings. Then you sort the sorted list with according to length of the strings. Here is the solution in Python 3.6.

for i in sorted(sorted(arr), key=len): print(i)

iqrar99 + 0 comments wow, that's cool

bisht09sachin + 2 comments Does it guarantees faster computation than using just key=int

mike_buttery + 0 comments We need to sort by

`len`

and then lexigraphically using`lambda x: (len(x), x)`

. Refer also below comments by @spelvin and @agrigorcea.Here is

`len`

vs`int`

using timeit on test case 4import timeit with open(r"~/big_sort_input04.txt") as file: n = int(file.readline().strip()) unsorted = [] for _ in range(n): unsorted.append(file.readline().strip()) def bigSortinglen(unsorted): return sorted(unsorted, key=lambda x: (len(x), x)) def bigSortingint(unsorted): return sorted(unsorted, key=lambda x: int(x)) print( "bigSorting - len:", timeit.timeit("bigSortinglen(unsorted)", globals=globals(), number=1), ) print( "bigSorting - int:", timeit.timeit("bigSortingint(unsorted)", globals=globals(), number=1), )

And the results...

bigSorting - len: 0.007199285000751843 bigSorting - int: 3.989389060998292

**Len is 550 times faster!!!**I had larger timeit numbers but got bored waiting. I'm surprised

`int`

passed all the tests!dslowik500 + 1 comment As Mike Buttery points out, sorting by (len(s), s) is far faster than int as key. But sir_suhrubs' was 2x faster still! even though it's 2 sorts.

mike_buttery + 0 comments True, avoiding the overhead of the

`lambda`

function is what gives the double sort answer it's speed, with string conversion taking it's tollHere's another test I did

sort 0.0027178580000000174 len 0.01436778900000002 int 4.000350254999999

kathrechadev + 0 comments My 100 lines of code, still can't pass all testcases. and this 2 line code passed all.

enigma_0503 + 0 comments Just awsome.

spelvin + 0 comments I ended up working out the following one-line solution in Python 3:

def bigSorting(unsorted): return [s[1] for s in sorted([[len(s),s] for s in unsorted])]

Integers don't sort correctly when viewed as strings because, for example, '2' as a string is less than '15' due to lexicographic ordering, and converting the giant strings to integers seemed to slow things to a crawl. But integers of the same size do sort correctly as strings, so I sorted first by length and then broke "ties" by lexicographic sorting.

Divyesh_Patel + 0 comments thanks for such a nice explaination.

agrigorcea + 1 comment sorted(unsorted, key = lambda x: (len(x), x))

yaroverg + 0 comments used exactly the same line

IronMan_4 + 0 comments Thanks for the awesome tip! I am going to use this from next time onwards whenever I encounter such a situation.

NiceBuddy + 1 comment Nowadays C++ is also cool or getting more cooler...

#include <iostream> #include <vector> #include <algorithm> #include <functional> #include <string> int main() { int n{}; std::string temp{}; std::cin >> n; std::vector<std::string> vec(n); for (std::string& element : vec) std::cin >> element; static const auto compare = [](const std::string & now, const std::string & next) noexcept ->bool { return now.size() == next.size() ? now < next : now.size() < next.size(); }; std::sort(vec.begin(), vec.end(), std::cref(compare)); for (const std::string& element : vec) std::cout << element << '\n'; return 0; }

Vtu14559 + 0 comments tnq

prasanshasureka + 1 comment If str -> int is not very costly, why shouldn't we directly use the map function after the input to convert the list of strings to list of ints and then pass this list of ints to the bigSort function? (Python 3) This way our fuction will already have a list of integers to sort and no concern about the 'key' argument.

manojbhatt101010 + 0 comments [deleted]

constantinescu_3 + 0 comments tried with quicksort and the "str to int" step, makes me fail some of the test

rajeev_sanket + 0 comments Thanks for the great explaination...

sudamkalpage4 + 0 comments Thank you very much it was really helpful.

eggzotic + 1 comment Even with the fastest solution recommended here by Marty, test-cases 3 (7693 items) & 4 (9446 items) fail on Python 3.7 with "Your code did not execute within the time limits".

Just can't see how to streamline it further with Python...? Runtime for case 3 on my laptop is 5s. So HR is being kinda mean calling that too long?

Not so "easy" after all. Is the only solution to go for a faster language? (I've done probably 100+ other problems successfully with Python3, to date).

eggzotic + 0 comments And so reading further, I found the "double sorted on len" solution from sir_suhrab that really is super-fast (easily sorts everything in under 1s). Still find it weird as to what's going on there though, in that "outside" sort. Some implicit string-to-int magic that's faster than actually passing the "int" func as a key to sort?

devopsstr + 3 comments ******Can anyone suggest me. Why is't not clearing the Test case 6?******`static String[] bigSorting(String[] str)`

{ Arrays.sort(str,new Comparator() { @Override public int compare(String s1, String s2) { if(s1.length()==s2.length()) return s1.compareTo(s2); return s1.length()-s2.length(); } });

astha008 + 0 comments Stuck in the same... Please let me know if you find a solution.

vipinmalik941 + 0 comments Same problem here.

shubhampal261 + 1 comment Read input with

BufferedReader reader =

new BufferedReader(new InputStreamReader(System.in));instead of

Scanner scanner = new Scanner(System.in);

dainv91 + 0 comments Thank you. I passed Test case 6

diasdenny7 + 1 comment I written the same code.

**It still timed out in 2 test cases**.can anyone help me in thisdef bigSorting(unsorted):

`return sorted(unsorted,key=int)`

enigma_0503 + 1 comment This is what you need to do:

## return sorted(sorted(unsorted), key=len)

absking786 + 1 comment could you explain how this works..? Please

pekermilas + 0 comments Idea here is to first group elements of list by their sizes (a.k.a string lengths). Next we can go over same size element groups and sort each within corresponding group.

ABHIJEET_SD + 0 comments using 'unsorted.sort(key=int)' this also, it fails for three test cases !!

Is there any way to pass all test cases????

pekermilas + 0 comments A little late but I guess still a follow up comment will be helpful. You are absolutely correct, so for fastest sort here everything needs to stay as string. With that said, one can sort elements (as strings) by the legth first. Then taking same length sub-lists and sorting them (still elements are strings!) will give you the fast enough code for full credit here.

Deepanshu_v23 + 37 comments This particular c++ solution passed all test case.Nothing much to learn except for the comparison to be made inside the function.

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; // Use of comparator //comparing function only sorts if string size is equal and keeps the larger integgers at last. bool myfunction (string i,string j) { int n=i.length(); int m=j.length(); if(n==m) return (i<j); return n<m; } int main() { int n; cin>>n; vector <string> arr(n); for(int i=0;i<n;i++) cin>>arr[i]; sort(arr.begin(),arr.end(),myfunction); for(int i=0;i<n;i++) cout<<arr[i]<<endl; return 0; }

shubhamitankr + 1 comment [deleted]Sadi01 + 0 comments this code is ok when input given,,its give the correct output,,but hackkerrank it gives the wrong ,,where is the problem?

# include

# include

# include

# include

using namespace std;

int main(){ int n; cin >> n; vector unsorted(n); for(int i = 0; i < n; i++){ cin >> unsorted[i]; } vector::iterator it=unsorted.begin(); sort(it,unsorted.end()); for(int i = 0; i < unsorted.size(); i++){ cout << unsorted[i] << " "; } return 0; }

Jaimin_Chaudhari + 0 comments thanks a lot bro! it helped me a lot...

coreyhendrey + 2 comments [deleted]sungmkim80 + 8 comments This is how I implemented a custom comparer for comparing two strings. Everything passed without timeouts.

internal class CustomComparer : IComparer<string> { public int Compare(string x, string y) { // If the length is not the same, we return the difference. // A negative # means, x Length is shorter, 0 means the same (this doesn't occur) and a postive # means Y is bigger if (x.Length != y.Length) return x.Length - y.Length; // Now the length is the same. // Compare the number from the first digit. for (int i = 0; i < x.Length; i++) { char left = x[i]; char right = y[i]; if (left != right) return left - right; } // Default: "0" means both numbers are the same. return 0; } }

davejlin + 1 comment Interestingly, when I apply the same logic in Swift, all but two test cases time out. I guess Swift is not so swifty compared to C# or Java when in comes to string comparison!

ricardorauber + 2 comments Did you get it? I still have timeout with tests 3, 6 and 7:

import Foundation let n = Int(readLine()!)! var arr: [String] = [] for _ in 0..<n { arr.append(readLine()!) } let list = arr.sorted() { a, b in let sizeA = a.characters.count let sizeB = b.characters.count if sizeA == sizeB { return a < b } else { return sizeA < sizeB } } for i in list { print(i) }

davejlin + 0 comments No, I gave up using Swift for this one. Maybe the timing criteria to pass the tests are just too stringent for Swift? C#, Java, and C++ had no problems at all.

alex_vasenin + 1 comment I managed to pass all but one test with essentially the same algorithm, but eventually switched to Java. Unicode compliance comes with a price.

ronen_harati + 0 comments I managed to pass all tests in swift, here is the code

func bigSorting(unsorted: [String]) -> [String] { let strings = unsorted.sorted { (left, right) -> Bool in if left.count > right.count { return false } if left.count < right.count { return true } if let l = Int(left), let r = Int(right) { if l > r { return false } else if l < r { return true } } for i in 0..<left.count { let leftValue = left[left.index(left.startIndex, offsetBy: i)] let rightValue = right[right.index(right.startIndex, offsetBy: i)] if leftValue > rightValue { return false } else if leftValue < rightValue { return true } } return false } return strings }

leech932 + 0 comments Can make it slightly faster in your comparison

for (int i = 0; i < x.Length; i++) { char result = x[i]-y[i]; if (result) return result; }

Just calculate the difference directly and return the difference if it's non-zero.

PolymathNinja + 1 comment I had the same solution except after the length check I was using x.CompareTo(y) (the built in string compare) which gives the same sort order, but times out. Now I'm going to have to go see what the built-in string compare is doing that's so much slower. Probably some culture sensitive stuff.

NoneCares + 1 comment how did you solve it?... I am facing the same problem.

PolymathNinja + 1 comment Use the Array.Sort with the CustomComparer provided by sungmkim80 worked just fine.

NoneCares + 2 comments `static String[] bigSorting(String[] unsorted) { Arrays.sort(unsorted,new Comparator<String>(){ public int compare(String s1, String s2){ if(s1.length()!=s2.length()){ return s1.length()-s2.length(); } for(int i=0;i<s1.length();i++){ if(s1.charAt(i)!=s2.charAt(i)) return s1.charAt(i)-s2.charAt(i); } return 0; } }); return unsorted;`

still failing 6th test caseartemmast + 1 comment You are right. If i send unsorted array straight as result:

`static String[] bigSorting(String[] unsorted) { return unsorted; }`

, i still have !!!Terminated due to timeout!!!, but not Wrong answer. So the problem isn't in a sort method, because my sort method passed all enother tests. And if I'm perfoming my sort method on my laptop with 6-th testcase it works perfectly.

PolymathNinja + 7 comments My solution was in C#. The JVM and .Net VM probably have different performance characteristics. If you're still getting timeout without having any sort at all, then there's probably something going on in the sections where you load.

I did just try it, and Test Case 6 fails with a timeout if you just use the Java template code.

So Java is unable to even LOAD the test case fast enough.

The issue is with Scanner for reading the input. Use Buffered reader instead and NoneCares sort works perfectly fine.

`private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int n = Integer.parseInt(reader.readLine()); String[] unsorted = new String[n]; for (int i = 0; i < n; i++) { String unsortedItem = reader.readLine(); unsorted[i] = unsortedItem; } String[] result = bigSorting(unsorted); for (int i = 0; i < result.length; i++) { bufferedWriter.write(result[i]); if (i != result.length - 1) { bufferedWriter.write("\n"); } } bufferedWriter.newLine(); bufferedWriter.close(); reader.close(); }`

artemmast + 0 comments Thank you with Buffered reader it works perfectly!!!

ankit_vasava + 0 comments Thanks for the BufferedReader hint.

Jiona + 0 comments Thanks!

kelvin_nicholls + 0 comments Cheers, BufferedReader worked for me.

Antenka + 0 comments Worked like a charm on failing 6 out of time test case.

lemanisar23 + 0 comments Thankkkkkkk youuuuuu!!!!!!!!!!

raghunandan2005 + 0 comments Thanks for the buffered reader hint.

sugirthaa0209 + 0 comments s1.length()-s2.length() explain this line in particularly

eellor + 0 comments Thanks, at first I wondered how this CustomComparer could beat my initial lambda expression which was failing at TC #7:

Array.Sort(unsorted, (x, y) => (x.Length == y.Length ? string.Compare(x, y) : x.Length - y.Length));

And soon realized that I should have used

**string.CompareOrdinal()**. Now the lambda expression works for TC #7.ttyl7 + 0 comments [deleted]ttyl7 + 0 comments I borrowed sunggmkim80 logic but it seems like case 6 still failed for me. Is there any other optimization i can apply to the code to get case 6 to pass? https://github.com/MinhThai2/algorithmn/blob/big_sorting/src/Main.java . Thanks.

jason_goemaat1 + 0 comments I guess the default string comparer is too slow...

danielmayorga + 2 comments StringComparison.Ordinal is what you want to do for your string comparisons in C#. When performing a compare with StringComparison.Ordinal the RAW bytes are used to compare strings rather than some weird Culture-Info check remarks

using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] unsorted = new string[n]; for(int unsorted_i = 0; unsorted_i < n; unsorted_i++){ unsorted[unsorted_i] = Console.ReadLine(); } Array.Sort(unsorted,(string a,string b) => { if(a.Length == b.Length) return string.Compare(a,b,StringComparison.Ordinal); return a.Length - b.Length; }); Console.WriteLine(string.Join("\n",unsorted)); } }

selvakumarssk007 + 1 comment can you expalin your array.sort code, i cann't understand that

danielmayorga + 1 comment Array.Sort has many overloads.

This is the one I am using Array.Sort(Array, Comparison)

I'm passing a Delegate as my second parameter in this method.

Delegates are like function pointers in C++.

Comparison is a delegate similar in essence to IComparer.

An easier way to view it is Comparison is an function "reference." I just pass the function and avoid implementing the interface for IComparer.

Comparison, similar to IComparer returns an int. Zero is equal to match. Positive is greater than. Negative is less than.

If you are new to C# and know Java 8: In Java 8 has lambda expressions.

If you are new to C# and know Java 7 and before: It's similar to implementing an anonomous class.

That's an overview of what is happening with the Array.Sort

ddloria + 1 comment `static String[] bigSorting(String[] unsorted) { List<BigInteger> Data = Arrays.stream(unsorted).map(BigInteger::new).collect(Collectors.toList()); Collections.sort(Data); String Result[] = new String[Data.size()]; for (int j = 0; j < Data.size(); j++) Result[j] = Data.get(j).toString(); return Result; }`

This is my solution, it terminates the 4 test cases due to timeout (includes a very very large numbers)

bisarialove + 0 comments you should try using a comparator

Reem_Tariq + 1 comment Could you explain this please " return a.Length - b.Length" ?

danielmayorga + 1 comment if a(type string) has more characters than b(also type string). Then a is the larger number since there are no leading zeros.

For example if

var a = "15548459"; var b = "5478";

then you don't even have to read the string(i.e. do a string comparison). You can strongly say that a is greater than b.

Comparison is similar to IComparer's method called Compare(Object,Object). If the return is positive, then a is greater than b. a.Length-b.Length just means return positive if a is greater, negative if less. (They are never equal in my case since the logic operator beforehand addresses this.)

Reem_Tariq + 0 comments Thank You

Mykaxe + 2 comments [deleted]shubhamitankr + 0 comments [deleted]shubhamitankr + 0 comments

laianbinh + 0 comments That is verry helpful! Thank you (^_^)

Dipak_Prajapati + 0 comments thanks, it's really helpfull to solve problem.

duniya_ke_neta + 3 comments [deleted]wshanshan + 0 comments smart.

magnetik + 2 comments A little bit more concise way to perform this method

from collections import defaultdict n = int(raw_input().strip()) bucket = defaultdict(list) for _ in xrange(n): number = raw_input().strip() bucket[len(number)].append(number) for key in sorted(bucket): for value in sorted(bucket[key]): print(value)

rishravi + 0 comments This was amazing! Loved how you used the properties of defaultdict

chrislucas + 0 comments congratulations. It was a great insight

tanmaysankhe + 0 comments [deleted]

RITIK1996 + 1 comment can you explain me how myfunction() works.. plzz

Sadi01 + 1 comment it return the seqentially series of ascending order,,,but if the length of the two number is same return (i

if you compare two numbers 5000 and 60000

ovbiously length of 5000 is smaller than the others

so it returns the small length

and compare this two numbers

`60000 and 60001 the two number length is same,, but if u return only m<n any of them can be print among them,, but it is not correct.,,thats why u have to return (i<j)that means though the lentgh same but it return greater number,`

abdul_thomso + 0 comments but i and j are strings , not integers. So how are we comparing them using less than operator ?

prerak_mastermi1 + 0 comments [deleted]krauszrobert92 + 0 comments Nice solution. Here is the sorting with a lambda function

sort(begin(numbers), end(numbers), [](string &a, string &b) { return a.size() < b.size() || a.size() == b.size() && a < b; });

kundanctae + 1 comment Hello , Can you explain the comparision function .

sfelde21 + 1 comment he creates his own sorting method and passes it to sort. sort uses this method to compare each string in the vector. since the numbers overflow he takes the length and compares that first. if the length is equal he returns whether or not the first string is greater than the second.

else he returns whichever has a larger length

abdul_thomso + 0 comments But what do you mean by (i

davejlin + 5 comments Very clean and fast (passes all test cases) using Java:

class MyComparator implements Comparator<String> { public int compare(String x, String y) { if (x.length() == y.length()) { return x.compareTo(y); } return x.length() - y.length(); } }

louisjarvis + 3 comments Thanks for sharing. I was able to pass all test cases without timeout by combining this method with a merge sort algorithm

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] unsorted = new String[n]; for(int unsorted_i=0; unsorted_i < n; unsorted_i++){ unsorted[unsorted_i] = in.next(); } MergeSorter ms = new MergeSorter(); ms.sort(unsorted,0, unsorted.length-1); for(String s : unsorted) System.out.println(s); //bigSort(unsorted); } } class MergeSorter{ public void merge(String arr[], int lidx, int midx, int ridx){ int lsize = midx-lidx+1; int rsize = ridx-midx; String[] larr = new String[lsize]; String[] rarr = new String[rsize]; for(int i = 0; i < lsize; i++) larr[i] = arr[lidx+i]; for(int j = 0; j < rsize; j++) rarr[j] = arr[midx+j+1]; int i = 0, j = 0; int k = lidx; StrComparator comp = new StrComparator(); while(i < lsize && j < rsize){ if(comp.compare(larr[i], rarr[j]) < 0){ arr[k] = larr[i]; i++; } else { arr[k] = rarr[j]; j++; } k++; } while(i < lsize){ arr[k] = larr[i]; i++; k++; } while(j < rsize){ arr[k] = rarr[j]; j++; k++; } } public void sort(String arr[], int lidx, int ridx){ if(lidx < ridx){ int midx = (ridx+lidx)/2; sort(arr,lidx,midx); sort(arr,midx+1,ridx); merge(arr,lidx,midx,ridx); } } } class StrComparator implements Comparator<String>{ public int compare(String str1, String str2){ if(str1.length() == str2.length()) return str1.compareTo(str2); else //if return > 0, str1 is the larger number return str1.length() - str2.length(); } }

Muhammad_Tariq + 1 comment @louisjarvis, I think the better and simpler approach is to use Collections.sort(List, Comparator) utility method which will do the work for us. We can implement the Comparator as suggested by @davejlin.

We (programmers) already know the mergesort algorithm so I think utility method its simpler to understand and implement.

I also like your solution.

Regards

PETE_TIAN + 0 comments I concur this. Especially in Java 8, all we need to do is to cover the String[] to ArrayList, and put the new comparator over there when calling sort().

shikhar_rawat31 + 0 comments [deleted]mikelee89 + 0 comments still times out with test case 6. It worked with Fast Reader

Muhammad_Tariq + 0 comments Thanks @davejlin. Your post is very helpful.

krupa5538 + 0 comments can you plz share how have you used this?

kapploneon + 0 comments I hoped for the same, but my Java solution(below) is still timedOut for testcase 6. Can anyone point out the improvement?

`static String[] bigSorting(String[] unsorted) { // Arrays.sort(unsorted); Arrays.sort(unsorted, (x, y) -> { if (x.length() == y.length()) { return x.compareTo(y); } return x.length() - y.length(); }); return unsorted; }`

mikelee89 + 1 comment It still fails test case no. 6. Use fast reader.

vishesh_345 + 0 comments Just try it in c.. it will be interesting

swargam + 1 comment This code will not be worked in the test case where elements containing like 0950 and 999

Hacker rank also didn't check the this type of test case I think.some change in the comparision function is requried.

japkeerat21 + 0 comments It is written in the problem statement that there won't be any leading zeroes. So the test case you are talking about is factually incorrect.

sfelde21 + 0 comments [deleted]amar97 + 1 comment can u explain the arguments inside sort()

_dugy + 0 comments CppReference about sort: http://en.cppreference.com/w/cpp/algorithm/sort

plmuon + 0 comments Using a lambda instead, a little bit shorter:

#include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std; int main(int argc, char** argv) { int n; cin >> n; vector<string> v(n); for (int i = 0; i < n; i++) cin >> v[i]; sort(v.begin(), v.end(), [](const string& a, const string & b) { return a.length() == b.length() ? a < b : a.length() < b.length(); }); copy(v.begin(), v.end(), ostream_iterator<string>(cout, "\n")); return 0; }

sumitupadhye12 + 0 comments can someone explain this logic.

itsmerishabhk + 0 comments can you explain me how would your code respond if there are two string values of equal length? i mean code wise?

malawatharshil + 0 comments When n==m,its fine that we are returning i

yvnm451996 + 0 comments brilliant technique

_dugy + 0 comments You should change arguments in "myfunction" to (const string& i, const string& j). const will be there for compiler(and readers) to know, that you won't change the strings and & because you don't want to(I guess) always copy strings.

But otherwise nice solution.

skgrewal_95 + 1 comment can anyone explain myfunction ??

lavistam + 0 comments Read the "comp" section of this page: http://www.cplusplus.com/reference/algorithm/sort/

Comparison function basically needs to return a non zero value, if first argument is less than second argument.

The function first sorts on length (smaller length == smaller number) and when length ties, is compares the string by ASCII value (i.e. the char '1' < '2'). This means it will compare the first character of one string to the first character of the second string, until they don't match returning wherether the first is smaller than the second (this is how c++ uses the < operator on strings comparing them char by char so that abc < bc)

lavistam + 3 comments I like yours :), for the rest here it is in Java:

static String[] bigSorting(String[] arr) { Arrays.sort(arr, new Comparator<String>() { @Override public int compare(String a, String b) { if(a.length() == b.length()){ return a.compareTo(b); } return a.length() - b.length(); }}); return arr; }

sidajwalia + 2 comments hey, first I converted strings into bigdecimals and then inbuilt sort and then again convert back, but it was timing out for 3-4-6-7 testcase. then i read here that bigdecimal-string conversion is really slow. So i went with ur suggestion, string comaparator, still 6th testcase is timing out. why? can you help me out?

static String[] bigSorting(String[] unsorted) { Arrays.sort(unsorted, new Comparator<String>(){ public int compare(String a, String b){ if(a.length() == b.length()) return a.compareTo(b); return a.length() - b.length(); }}); return unsorted; }

eellor + 1 comment My recommendation is not to use String.compareTo() as it implies a Unicode conversion. Try to compare strings at character level or as byte arrays.

sidajwalia + 1 comment but how it affects time complexity? @eellor

eellor + 0 comments It doesn't affect the time complexity in this bigSorting() method itself but it depends on how Unicode / language culture is handled in String.compareTo(). I don't know the internal details of String.compareTo() but what if it has to convert each character in the string and store it into another place? What if it has to repeatedly search in Unicode / culture table?

In my case using C#, it failed with string.Compare() and succeeded with string.CompareOrdinal(). The former works in the same way with Java's String.compareTo(). The latter is to do a character level comparision without considering Unicode / culture.

kapploneon + 0 comments You don't need to convert to bigdecimal string comparision itself is sufficient to sort.

anks2906 + 1 comment can you please explain this? I'm havinf troube understanding why are we using a seperate logic for the case where a.length is same as b.length or otherwise returning just the difference in number of digits. why cant we just use comareTo ?

eellor + 0 comments This problem requires to sort in ascending order of "integers". With simple string comparison, you'll get

1 10 2 3

while 10 shall go to the last. So the naive solution is to convert all strings into numbers first and to sort the numbers, but it will be much slower and it will require a special number data type to hold big numbers.

krzysztof_kubie2 + 0 comments You have one timeout

sourabhsingh + 1 comment Easy solution, first sort on basis of first value and then on length.

def bigSorting(arr): arr.sort() arr.sort(key=len) return arr

reolander + 1 comment def bigSorting(unsorted): return sorted(unsorted, key=int)

^This is much better.

Sanketpathak64 + 0 comments can u tell me what is significance of key=int in sorted fuction?

elvis_dukaj + 0 comments Good solution, but you're style need to medernize :P

#include <vector> #include <iostream> #include <algorithm> #include <iterator> using namespace std; bool string_less_comparision(const string& s1, const string& s2) { if (s1.length() == s2.length()) return s1 < s2; return s1.length() < s2.length(); } int main() { int sz; cin >> sz; vector<string> a(sz); copy_n(istream_iterator<string>(cin), sz, begin(a)); sort(begin(a), end(a), string_less_comparision); copy(begin(a), end(a), ostream_iterator<string>(cout, "\n")); return 0; }

bhartmittal + 0 comments can you please explain bool myfucntion()?

sanjeevbittu83 + 0 comments can you explane these line

if(n==m) return (i

`return n<m;`

mansurisafwan19 + 0 comments # include

# include

# include

# include

# include

using namespace std;

bool myfuction(string p,string q) { int s,o; s=p.size(); o=q.size(); if(p==q) return p

int main()

{ vectora; int n,i,x; scanf("%d",&n);

for(i=0;i>a[i]; }

sort(a.begin(),a.end(),myfuction);

/*vector:: iterator it;

for(it=a.begin();it!=a.end();it++) { cout<

for(i=0;i

}

`brother what i did wrong here;`

t_2_f + 0 comments can someone explain what is going on inside the function?

atulia292050 + 0 comments Thanks , that worked. I implemented radix sort with len and it got tle because len of max element was too long that it added a factor in my algorithm running time.

emil_lubomirov_1 + 0 comments Nice and clear solution, man! Thank you! :)

vivekshetty + 0 comments Thanks this very clean code helped me a lot

hrishi007 + 0 comments explain myfunction little bit

kris_tobiasson + 1 comment Here's a JS approach:

return unsorted.sort((a,b) => { if(a.length === b.length){ return BigInt(a)-BigInt(b); } else{ return a.length - b.length } });

saxenarajat26 + 1 comment well without the if condition if im returning a-b then time limit is exceeding ..what is with the length return unsorted.sort((a,b) => BigInt(parseInt(a))- BigInt(parseInt(b)))

kris_tobiasson + 0 comments BigInt() will consume more time. If we know that one is longer than the other, we dont need to use BigInt() because the length tells us which is greater, so we only use BigInt() when they are equal in length, because the length won't tell us which is greater in this case. Cheers

saurya9000 + 0 comments why we use comparision function

ryanfehr18 + 8 comments **Here are the key things to think about:**- BigInteger comparisons require converting to integers from strings then comparing as integers which is slow and inefficient.
- You can easily override a String[] comparator to be whatever you like and still get the benefits of Java doing a double pivot quicksort without you having to code it
- If you use a StringBuilder to build your ouput and then only make a single System.out call it will be much faster because I/O is slow

**Java Solution**Here is my solution in Java that passes all cases in O(n log(n)) time with O(n) space.**For more solutions like this check out the HackerRank Github repo here**0xAshish + 0 comments i had that same idea but didn't knew about comparator . in first approach i used String.length()to sort it then i found that i need to compare number too so i got idea to compare number with equal length only as number but then used BigInteger and then got idea to use comparator from your comment and please don't post direct solution .

Purvi_ + 2 comments which sorting algorithm did u use ,coz i m getting time out for four cases even after using quick sort

ryanfehr18 + 2 comments - I used Java's built in Arrays.sort() method along with a custom comparator. Java's sort function is implemented using a dual pivot quicksort that helps to reduce worse case runtimes. If you are determined to implement your own quicksort I suggest you look into how to reduce worst case runtime by changing how you choose your pivot.
- It is also worth noting that if you are coding this in Java you should look into using StringBuilder for you output as often times this can cut unamortized runtime in half or more.

Purvi_ + 1 comment yes i implemented my own quick sort but it could pass only three test cases , so i used comparator and now its working , thanks for your suggestion.

Sivappu_vannam + 1 comment i implemented my quicksort as well. And it doesnt pass one test case. Probably due to overhead of recursive function call.

786lokesh + 0 comments You probably implemented your quick sort using one pivot. Java built in Arrays.sort uses two pivot to sort.

jemmydng12 + 2 comments ur code is not visible. can u post it here.

ryanfehr18 + 0 comments **For more solutions like this check out the HackerRank Github repo here**Sometimes the HackerRank redirect link doesnt work, if that is the case just remove the first part of the redirect url

janusz_k + 1 comment List<String> numbers = new ArrayList<>(); int n = scanner.nextInt(); for (int j = 0; j < n; j++) { numbers.add(scanner.next()); } numbers .stream() .parallel() .sorted((s1, s2) -> { if (s1.length() != s2.length()) { return s1.length() - s2.length(); } else { for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) != s2.charAt(i)) { return s1.charAt(i) - s2.charAt(i); } } } return 0; }) .forEachOrdered(System.out::println);

raghavendramj123 + 0 comments How about this..

`static String[] bigSorting(String arr[]) { Arrays.sort(arr, (left, right) -> { if (left.length() != right.length()) return left.length() - right.length(); return left.compareTo(right); }); return arr; }`

shubhamkr120798 + 1 comment the program will compile even using insertion sort algorithm but the problem is the very big integer that is given..can,t decide data type for this as using long long data type cannot rid with the problem

ryanfehr18 + 1 comment You will want to double check you code, because the limit on number size for this problem is

*2 x (10^5)*for n and*10^6*for digits which should easily fit in an integer which can hold a little over 2 billiondulacpier + 1 comment I think you meant for the limit "10^6 number of digits" which cannot be hold in as an integer (which could only take less than 10 digits, as you said a value a little over 2 billion)

ryanfehr18 + 0 comments Yea what I said is a little jumbled. I was basically trying to say since you use an int to store n, you would have no problems because it can easily fit. Secondly, the only other constraint is that our number has at most 10^6 digits, which we represent as a string, so it is a non-issue. Thanks for asking for clarification.

MichaelTague + 0 comments I appreciate your tip about using StringBuilder to splat out the result.

On that builder part, it might be better to make two append calls rather that use + to put on the "\n". Also, you might just use string compare to compare the case where the strings are of equal length.

Still, fast overall result it looks like.

mdaenekas + 0 comments Thanks, my BigInteger solution failed after test case 3. Comparing the Strings wasnÂ´t difficult and saved lots of time.

786lokesh + 1 comment @ryanfehr18 Will you please tell me how your solution is O(nlog(n)) ?

ryanfehr18 + 1 comment The solution I posted uses the built in sort method that Java has. That built in method runs in

*O(n log(n))*by performing a dual pivot quicksort on the collection. For the comparison used in that sort, I wrote my own string comparison method that runs in worst case the length of one of the strings.*O(n log(n))*is a aproximation the absolute would be*O(SumOfStrings log n)*.786lokesh + 1 comment Is it O(SumofStrings log n) or O(n m log n) where m is the length of strings which are not equal ?

ryanfehr18 + 1 comment If we have strings that are 1 letter difference but all equal length for all inputs then, yes I believe you are right. We would make n comparisons that each take at most m time where m is the length of a string. The good thing about this problem, is that all strings sum to give us a upper bound on length. So there is a way for us to calculate the worst possible input.

786lokesh + 0 comments We should consider worst case complexity the run time complexity will be O(nmlogn) where m is the length which are equal and the last 1 letter are different.

komalagar1996 + 1 comment Hi Ryan Can you please tell me whats wrong with this code? import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] unsorted = new String[n]; String temp; for(int unsorted_i=0; unsorted_i < n; unsorted_i++){ unsorted[unsorted_i] = in.next(); } for (int i = 0; i < n; i++) { for (int j = 1; j < (n - i); j++) { if ((unsorted[j - 1]).length() >(unsorted[j]).length()) { temp = unsorted[j - 1]; unsorted[j - 1] = unsorted[j]; unsorted[j] = temp; } else if((unsorted[j - 1]).length()==unsorted[j].length()) { boolean flag=true; for(int k=0;k<unsorted[j - 1].length();k++) { if(unsorted[j - 1].charAt(k)>unsorted[j].charAt(k)) flag=false; } if (flag==false) { temp = unsorted[j - 1]; unsorted[j - 1] = unsorted[j]; unsorted[j] = temp; } } } } for(int unsorted_i=0; unsorted_i < n; unsorted_i++){ System.out.println(unsorted[unsorted_i]); } }`

}

Shivang_dhuria + 0 comments Your code is correct for small inputs but we need to do it for larger inputs.So implements Comparator in another class and then use that class to sort your values.

yoSingh + 1 comment Sir can u help me with your third point.I am not getting it.

ryanfehr18 + 1 comment The third bullet point has to do with writing using something like System.out or print etc. Those types of operations like reading or writing to a file or input and output (I/O) takes a lot of time for the computer to do. So instead of writing a bunch of different times. You can instead build a string and then just write at the end. Since in the case of this problem, you don't need to print until the very end.

yoSingh + 0 comments Thx sir now i got it.

ysundeep007 + 1 comment I have used the same solution as yours but even then the 6th test case is terminated due to timeout.

rigobrinkman + 2 comments I actually think this is a bug

This code, which is part of the template and

**only**scans the input, also times out on the 6th case on java 8`private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args){ int n = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); String[] unsorted = new String[n]; for (int i = 0; i < n; i++) { String unsortedItem = scanner.nextLine(); unsorted[i] = unsortedItem; } scanner.close(); }`

sangmanla + 0 comments I agree with you. I left a message to admin. There might be answer for this.

PolymathNinja + 3 comments Using BufferredReader instead of scanner works. New template (no spoiler on sort):

`private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int n = Integer.parseInt(reader.readLine()); String[] unsorted = new String[n]; for (int i = 0; i < n; i++) { String unsortedItem = reader.readLine(); unsorted[i] = unsortedItem; } String[] result = bigSorting(unsorted); for (int i = 0; i < result.length; i++) { bufferedWriter.write(result[i]); if (i != result.length - 1) { bufferedWriter.write("\n"); } } bufferedWriter.newLine(); bufferedWriter.close(); reader.close(); }`

osama119786 + 0 comments oh yes it works,thanks.

Htrahdis + 0 comments this alone works for me for the 6th test case.

kanirajeshwari25 + 0 comments This helps me for 6 case thanks a lot

olegcherednik + 4 comments **Test6: Timeout (Java)**When you just return unsorted array to the output:

static String[] bigSorting(String[] unsorted) { return unsorted; }

you still have timeout problem.

To solve this problem just replace

`scanner.nextLine()`

to`scanner.next()`

.for (int i = 0; i < n; i++) { String unsortedItem = scanner.next(); unsorted[i] = unsortedItem; }

Full

**Java**solution is:public class Solution { static String[] bigSorting(String[] unsorted) { Arrays.sort(unsorted, (x, y) -> x.length() == y.length() ? x.compareTo(y) : Integer.compare(x.length(), y.length())); return unsorted; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int n = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); String[] unsorted = new String[n]; for (int i = 0; i < n; i++) { String unsortedItem = scanner.next(); // nextLine() is too long unsorted[i] = unsortedItem; } String[] result = bigSorting(unsorted); for (int i = 0; i < result.length; i++) { System.out.print(result[i]); if (i != result.length - 1) { System.out.println(); } } System.out.println(); scanner.close(); } }

nickopants + 0 comments Thank you! That ended some serious frustration for me!

LOBsTerr + 0 comments Nice catch! I spent few hours optimizing my solution

juancho85 + 0 comments Could you please explain why next() outperforms nextLine()? Reading the javadoc I don't undertand the time difference between "advancing line" vs "getting the next token".

Thanks

m_patrawala + 1 comment thanks that solved my problem. However can u share whats the issue with readLine vs read

vipinmalik941 + 0 comments read() uses the delimiter 'space' to parse the value, so it can't detect the space between the string but readLine() goes through the string so it can detect the in-between the spaces. But Since the readLine() goes through the entire string, it takes more time than the read() which only uses the delimiter. Hope that helps.

einsweniger + 6 comments python3 with bucketsort:

n = int(input().strip()) bucket = {} # read all integers as strings, store them by length in the bucket for _ in range(n): number = input().strip() length = len(number) # create new bucket for length if not length in bucket: bucket[length] = [] bucket[length].append(number) # read from the bucket in ascending order for key in sorted(bucket): for value in sorted(bucket[key]): print(value)

amoghlakkanagavi + 7 comments why cant i do this

#!/bin/python3 import sys n = int(input().strip()) unsorted = [] unsorted_i = 0 for unsorted_i in range(n): unsorted_t = str(input().strip()) unsorted.append(unsorted_t) # your code goes here uc=[] for i in unsorted: uc.append(int(i)) uc.sort() for i in uc: print(i)

nachiketaprasad4 + 0 comments please explain the segment after #your code goes here

[deleted] + 0 comments [deleted]dasein_phil + 1 comment That's more or less what I did, but I'm timing out on three of the test cases:

# your code goes here med = [int(i) for i in unsorted] med.sort() for i in med: print str(i)

MartyMacGyver + 0 comments Same problem I had... and resolved. In short, int->str conversions is costly, especially when large ints are involved (as they are on the test cases that will fail with that logic).

https://www.hackerrank.com/challenges/big-sorting/forum/comments/326995

rospython + 0 comments we can use also unsorted.sort() method in above function to get the result n

bbenkins + 2 comments This works:

# your code goes here unsorted.sort(key=int) for item in unsorted: print(item)

davebrophy + 0 comments More or less what I did, but I just sorted in the print statement:

print('\n'.join(sorted(unsorted,key=int)))

CornellGan + 1 comment All I get when trying this or other solutions from comments is thiss error...

Traceback (most recent call last): File "solution.py", line 28, in <module> result = bigSorting(unsorted[n]) IndexError: list index out of range

help please

Tides + 1 comment There are

*n*items in*unsorted*, so*unsorted[n]*is out of range (remember, lists start at 0!). If you want to pass the last element of the list to*bigSorting*, use*unsorted[n-1]*or*unsorted[-1]*. If you want to pass the full list to*bigSorting*, try*result = bigSorting(unsorted)*. If you need more help, please post your full code :)CornellGan + 0 comments Oh. That's why you don't copy other peoples' code without understanding it first :)

Tzalumen + 0 comments There's a few problems that will cause you to time out.

- copying the entire array is costly
- printing individual values to stdout is costly

I was having a similiar problem, I solved #2 by building the output string up with

`"\n".join(arr)`

then printing it all out at once. The speed difference is dramatic. I was still timing out on a few. after looking up a few things, I realized, I needed to sort in stages. First I sorted by length, using a dictionary, and kept the values as strings, then I sorted those string lists lexically.Came out like this:

di = dict() for i in unsorted: l = len(i) if l in di: di[l].append(i) else: di[l] = [i] outs = '' for i in sorted(di.keys()): di[i].sort() outs += '\n'.join(di[i]) outs += '\n' print(outs)

Which, as I read more comments is apparently a bucket sort?

Tides + 0 comments Could even do it like this:

# your code goes here for i in sorted(sorted(unsorted), key=len): print(i)

oksuzgonulh + 1 comment Thanks for teaching me what bucketsort is, I replicated a scrappy version of yours.

n = int(input().strip()) unsorted = [] lengths = [] for k in range(n): number = str(input().strip()) unsorted.append(number) lengths.append(len(number)) biglist = zip(lengths,unsorted) for i in sorted(biglist): print(i[1])

Slaunger + 0 comments [deleted]

scandium + 1 comment You stored strings in the

**buckets**of your*****. So , how do the strings of a*bucket****bucket**get sorted ?? I mean if they are strings , then how can you sort them ?AndyS_12 + 1 comment In python the sorted() function starts comparing the string from ASCII value of most significant digits. For eg: If you want ro sort "3", "9" and "10".

ie. l=["10", "9", "3"] print sorted(l) Output: ["10","3","9"] let msd=Ascii value of most significant digit The output is correct according to the algorithm that msd(10)<msd(3)<msd(9) But logically it is not.

So, here it can be a problem. But if you first put every element as per their lengths in their respective buckets, then it won't be a problem.

rospython + 2 comments so whats the better way to do that,,, in python if we don't want to use in build function sort,,, any logic not lendy one

AndyS_12 + 0 comments To know how sorted() function works this efficiently you can follow this link sort in python

MartyMacGyver + 0 comments See my comment elsewhere in this discussion:

https://www.hackerrank.com/challenges/big-sorting/forum/comments/326995

LeHarkunwar + 1 comment Lambda works efficiently in this too.

n = int(input()) unsorted = [input() for _ in range(n)] unsorted.sort(key = lambda x: (len(x), x)) print('\n'.join(unsorted))

GStellar_98 + 1 comment what exactly will lambda do in this?

ggorlen + 0 comments Lambda is an anonymous function that acts as a custom comparator for the sort. First, a given element x is compared based on its length, followed by its regular sorted value, effectively performing a bucket sort as seen in the other posts.

dasamy2016 + 0 comments Thank you loads for introducing me to bucket sort technique

mbialov + 0 comments Awesome

Sort 594 Discussions, By:

Please Login in order to post a comment