- Practice
- Algorithms
- Sorting
- Big Sorting
- Discussions

# Big Sorting

# Big Sorting

MartyMacGyver + 9 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 + 4 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.

cz772 + 0 comments Same here! Just implemented merge sort and thought I would pass every case. Nope

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

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 + 1 comment 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

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.

Deepanshu_v23 + 31 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 + 5 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 + 0 comments I managed to pass all but one test with essentially the same algorithm, but eventually switched to Java. Unicode compliance comes with a price.

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 + 0 comments 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.

snaran + 0 comments If you compare -5 to 4, we get if (x.Length != y.Length) return x.Length - y.Length if (2 != 1) return 2 - 1; return 1; // implying -5 > 4

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.

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 + 0 comments 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

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 + 0 comments 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,`

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 + 0 comments 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

davejlin + 4 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 + 2 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]

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; }`

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

as361 + 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 + 2 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.

sourabhsingh + 0 comments Easy solution, first sort on basis of first value and then on length.

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

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?

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 + 1 comment 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.

einsweniger + 5 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

leoybkim + 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

jgilly18 + 6 comments JavaScript Solution:

function main() { var n = parseInt(readLine()); var unsorted = []; for(var unsorted_i = 0; unsorted_i < n; unsorted_i++){ unsorted[unsorted_i] = readLine(); } // your code goes here unsorted.sort(function(a,b) { if (a.length > b.length) { return 1; } else if (a.length === b.length) { var aChars = a.split(''); var bChars = b.split(''); for (var iter = 0; iter < a.length && iter < b.length; iter++) { var currentANum = parseInt(aChars[iter]); var currentBNum = parseInt(bChars[iter]); if (currentANum > currentBNum) { return 1; } else if (currentANum < currentBNum) { return -1; } else { // Do nothing so that we fall to the next character position comparison } } return 0; } else { return -1; } }); unsorted.forEach(function(currentItem) { console.log(currentItem); }); }

Basic idea is to do a length comparison first, as the larger string will be a larger number. If they are the same length, then we need to compare their actual values.

Simple doing a comparison between A and B doesn't always work for the really large strings, so instead I iterate through each character in the string to compare their numerical values against each other.

This starts at the beginning of the string, because if this number is bigger than the other, we know the rest of the number is larger too. If both characters are equal, look to the next set of characters to see which is larger.

Iteration stops by the return statement so if we find one is larger than the other, we don't keep looping the entire split arrays.

pajay2507 + 1 comment Hey I am using this solution, Two test cases is getting failed. Can you explain y its failing?.

function main() { var n = parseInt(readLine()); var unsorted = []; for(var unsorted_i = 0; unsorted_i < n; unsorted_i++){ unsorted[unsorted_i] = readLine(); } // your code goes here //console.log(unsorted); unsorted.sort(function(a, b) { return a - b; }); //console.log(unsorted); //var sorted = unsorted.sort(); unsorted.forEach(function(element){ console.log(element); }) }

jgilly18 + 1 comment You need to handle the cases where the unsorted array is really large. If you just do a - b, it will time out on the really big cases.

So you can do some optimizations by doing length comparison instead (if A or B's lengths are bigger then the other, then it will always be a bigger string value). If the lengths are the same, then you need to do a character by character evaluation.

This will improve the run time considerably so you're not doing massive string comparisons.

pajay2507 + 1 comment Cool.. I got it. Thanks.

sebastiangcooper + 0 comments JavaScript has a maximum value of Number types it can process as numbers, see max integer value in JavaScript

If you run the snippet below in your console you will see the result is NaN (not a number) indicating that the subtraction cannot be calculated, thus we have to compare larger integers based on their individual character values:

parseInt(69169555744334818274419023976430344618457850165626213664752217677003953150535166512918750203967357722676268582815611737574493112368939099342641215831991941425936342318448360572459066838021798674483556641910793580567662994288482928421874992068019644253231745544908467646686651014428257668031614237625352222610459805470837809628537835995896039694249263790552250989187451907746272587443898559731329666967855748420397162860992973751590164593525539665770721115378257127108902993309635248536600352007502406059781546310467929223715136275132732020561005626393441397947918820133717415072684122291041690415943682390767682016632719756094957582062932533126276920508195203270143581645201656516045876579) - parseInt(84626207750546491731324105656484839715396860539359173031837567409308821068931533870912409000)

huynhtrankhanh21 + 0 comments Here is my sorting function:

const LESS_THAN = -1; const EQUAL = 0; const GREATER_THAN = 1; function compare(a, b) { if (a === b) { return EQUAL; } if (a.length < b.length) { return LESS_THAN; } if (a.length > b.length) { return GREATER_THAN; } if ([a, b].sort()[0] === a) { return LESS_THAN; } else { return GREATER_THAN; } }

justin_a_mathieu + 0 comments Great solution! Here is my take on it!

function main() { var n = parseInt(readLine()); var unsorted = []; for(var unsorted_i = 0; unsorted_i < n; unsorted_i++){ unsorted[unsorted_i] = readLine(); } console.log(unsorted.sort(function(a,b){ return bigIntSort(a,b); }).join("\n")); } function bigIntSort(a,b){ if(a.length!=b.length){ return a.length>b.length?1:-1; } a_ar = a.split(""); b_ar = b.split(""); for(var i=0; i<a_ar.length; i++){ if(a_ar[i] != b_ar[i]) { return a_ar[i]>b_ar[i]?1:-1; } } return 0; }

luisgrases + 2 comments Check out this high-level solution:

let queue = [] let result = [] const sortedByLength = unsorted.sort((a, b) => a.length - b.length) for(let i = 0; i < sortedByLength.length; i++) { queue.push(sortedByLength[i]); if(i == sortedByLength.length-1) { result = result.concat(queue.sort()) break; } if (queue.length > 0 && sortedByLength[i+1].length > queue[0].length) { result = result.concat(queue.sort()) queue = [] } } result.forEach(v => {console.log(v)})

chadwalt + 1 comment Please explain how this works.

luisgrases + 0 comments It is not possible to convert the strings to integers as javascript wont support integers with large sizes.

What we need to do is compare the strings, but strings are compared char by char so: 123 > 134 but 123 > 1124. It seems the only way to solve this issue is by sorting strings with equal length and progressively add them to the result.

That code basically sorts the entire array by length and starts adding the strings to a queue. When it finds a string with a larger length than the last string added to the queue, it sorts the queue and append it to the result. Then it add that last string found to the queue and repeats the process.

OldShaky + 0 comments I was gonna do the exact same thing, glad to know it'll work :)

yao_gban + 0 comments A bit leaner solution without all of the extra test conditions.

function bigSorting(arr) { const results = arr.sort((a,b) => { if(a.length !== b.length){ return a.length - b.length; } else{ for(let i = 0; i < a.length; i++){ if(parseInt(a[i]) !== parseInt(b[i])){ return parseInt(a[i]) - parseInt(b[i]); } } } }); return results; }

adamxtokyo + 0 comments The problem you're all running into is that there's a limit to how big numbers can be in Javascript. There are several libraries that handle this though, and one is even supported by HackerRank so you can solve problems like this. Check it out here: https://www.hackerrank.com/environment (scroll down to Javascript)

Here's my oneliner solution (minus the library require):

const BigNumber = require('bignumber.js') const bigSorting = arr => arr.sort( (a, b) => new BigNumber(a).comparedTo(new BigNumber(b)) )

olegcherednik + 1 comment **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!

bobbypriambodo + 0 comments Using Java (7 & 8) with Arrays.sort and custom comparator always gave me TLE on 6th test case. Switched to Haskell with the same comparison algo and it passed all cases.

tanaydin + 1 comment Python 3, one liner.

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

wilmer_henao + 0 comments [deleted]

chinski + 1 comment **A 3-liner solution in Python:**unsorted = [input() for _ in range(int(input()))] x=sorted(unsorted,key=lambda x:(len(x),int(x))) print(*x,sep='\n')

The key is to use a proper key for sorting :)

MartyMacGyver + 1 comment The key is unnecessarily complex...

`key=int`

ought to suffice, no?Clever print statement - very compact!

Lehonti + 0 comments No, key=int doesn't suffice. Parsing an integer from a string is a very heavyweight operation. Performing it unnecessarily will cause the python program to time out. We need to use lightweight comparison functions first, and only use the heavyweight ones if there's no alternative. My Python solution, to which I arrived independently, turns out to be very similar to this one, for the reasons mentioned.

numberStrings = ( input().strip() for _ in range( int(input().strip()) ) ) print( * sorted( numberStrings, key = lambda s : ( len(s) , s ) ), sep='\n' )

kevine711 + 1 comment My java solution

static String[] bigSorting(String[] arr) { List<String> list = new ArrayList<String>(Arrays.asList(arr)); Collections.sort(list, new Comparator<String>(){ @Override public int compare(String one, String two){ //lengths not equal if(one.length() != two.length()){ return one.length() - two.length(); } //lengths are equal, compare value from most significant digit for(int i = 0; i < one.length(); i++){ if(one.charAt(i) != two.charAt(i)) return one.charAt(i) - two.charAt(i); } return 0; //equal values } }); return list.toArray(new String[list.size()]); }

hardeep_parmar + 0 comments Fails on test case 6(timeout).

Sort 414 Discussions, By:

Please Login in order to post a comment