Say I have a string a.
a = "12 I have car 8 200 a" I need to sort this string in such a way that the output should be
8 a car have 12 200 I ie, Sort the string in such a way that all words are in alphabetical order and all integers are in numerical order. Furthermore, if the nth element in the string is an integer it must remain an integer, and if it is a word it must remain a word.
This is what I tried.
a = "12 I have car 8 200 a" def is_digit(element_): """ Function to check the item is a number. We can make using of default isdigit function but it will not work with negative numbers. :param element_: :return: is_digit_ """ try: int(element_) is_digit_ = True except ValueError: is_digit_ = False return is_digit_ space_separated = a.split() integers = [int(i) for i in space_separated if is_digit(i)] strings = [i for i in space_separated if i.isalpha()] # sort list in place integers.sort() strings.sort(key=str.lower) # This conversion to iter is to make use of next method. int_iter = iter(integers) st_iter = iter(strings) final = [next(int_iter) if is_digit(element) else next(st_iter) if element.isalpha() else element for element in space_separated] print " ".join(map(str, final)) # 8 a car have 12 200 I I am getting the right output. But I am using two separate sorting function for sorting integers and the words(which I think is expensive).
Is it possible to do the entire sorting using a single sort function?.
6 Answers
Answers 1
numpy allows to write it more concisely, though doesn't eliminate the need for two separate sorts:
$ python3 Python 3.5.2 (default, Nov 23 2017, 16:37:01) [GCC 5.4.0 20160609] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import numpy as np >>> from numpy.core.defchararray import isdecimal, lower >>> >>> s = "12 I have car 8 200 a" >>> >>> a = np.array(s.split()) >>> >>> integer_mask = isdecimal(a) >>> string_mask = ~integer_mask >>> strings = a[string_mask] >>> >>> a[integer_mask] = np.sort(np.int_(a[integer_mask])) >>> a[string_mask] = strings[np.argsort(lower(strings))] >>> >>> ' '.join(a) '8 a car have 12 200 I' Answers 2
Is it possible to do the entire sorting using a single sort function?.
No, not really.
Why not? It turns out the answer is already in your code.
integers.sort() strings.sort(key=str.lower) Notice how you need to sort by two different functions here. The first is an integer sort, the second is a lowercase string sort. We could try something like this:
def get_sort_order(element): try: value = int(element) except ValueError: value = element.lower() return value a.sort(key=get_sort_order) But that doesn't work either; it just gives us the result
['8', '12', '200', 'a', 'car', 'have', 'I'] You could probably force this into a solution, but it isn't going to be pretty.
However, there is another point I'd like to address:
But I am using two separate sorting function for sorting integers and the words (which I think is expensive).
Sorting two distinct lists is basically always going to be faster anyway. To find out why, just look at the time complexity of the two tasks:
Assuming a list of length 1000, exactly half integer and half strings, and a sorting algorithm of O(nlog(n)):
One single sort: 1000 * log(1000) = 3000
Two separate sorts: 2 * (500 * log(500) = ~2699
So sorting the list in a single run is both more difficult to implement and slower!
Answers 3
It is possible in one sort, by applying a custom function within the 'sorted' method as a User described above. I have tried a simplified version for the same. The default 'sorted' method does the wonder with a little tweak. Hope it resolves your query.
import re input = "12 I have car 8 200 a" splitted = input.split() s_lst=sorted(splitted, key=lambda a:int(a) if a.isdigit() else a.lower()) count_nos = re.findall(r'\d+',' '.join(s_lst)) str_index = len(count_nos) no_index = 0 result=[] for i in range(0,len(splitted)): if splitted[i].isdigit(): result.append(s_lst[no_index]) no_index+=1 else: result.append(s_lst[str_index]) str_index+=1 print ' '.join(result) Answers 4
You could do in one sort provided you write a custom function for comparision. The idea is to sort the words in ascending order and integer in descending order in the same list . Incase of word and integer is compared then treat the word as smaller compared to word.
And then for printing the final result increment the index for word if a word is found , decrement the index for integer if digit is found.
The below code works in python2:
a = "12 I have car 8 200 a" def custom_compare(x,y): if x.isdigit() and y.isdigit(): return int(y) - int(x) #do a descending order if x.isdigit() and y.isdigit() == False: return 1 if x.isdigit() == False and y.isdigit(): return -1 if x.isdigit() == False and y.isdigit() == False: # do ascending order if x.lower() == y.lower(): return 0 elif x.lower() < y.lower(): return -1 else: return 1 original_list = a.split(" ") sorted_list = sorted(original_list, cmp=custom_compare) result = [] integer_index = -1 string_index = 0 for word in original_list: if word.isdigit(): result.append(sorted_list[integer_index]) integer_index = integer_index - 1 else: result.append(sorted_list[string_index]) string_index = string_index + 1 result ['8', 'a', 'car', 'have', '12', '200', 'I'] Python 3: import functools
a = "12 I have car 8 200 a" def custom_compare(x,y): if x.isdigit() and y.isdigit(): return int(y) - int(x) #do a descending order if x.isdigit() and y.isdigit() == False: return 1 if x.isdigit() == False and y.isdigit(): return -1 if x.isdigit() == False and y.isdigit() == False: # do ascending order if x.lower() == y.lower(): return 0 elif x.lower() < y.lower(): return -1 else: return 1 original_list = a.split(" ") sorted_list = sorted(original_list, key=functools.cmp_to_key(custom_compare)) result = [] integer_index = -1 string_index = 0 for word in original_list: if word.isdigit(): result.append(sorted_list[integer_index]) integer_index = integer_index - 1 else: result.append(sorted_list[string_index]) string_index = string_index + 1 result PS:The word comparison could be efficiently written. I am from C background and I am not sure of the pythonic way of comparison.
Answers 5
s = "2 is a A -3 car 11 I 0 a" def magick(s): s = s.split() def reverse(tuples): return [(a, b) for (b, a) in tuples] def do_sort(tuples): firsts = [a for a, _ in tuples] seconds = [a for _, a in tuples] return list(zip(sorted(firsts), seconds)) def str_is_int(x): try: int(x) return True except: return False indexed = list(enumerate(s)) ints = do_sort([(int(x), ix) for (ix, x) in indexed if str_is_int(x)]) strs = do_sort([( x , ix) for (ix, x) in indexed if not str_is_int(x)]) return ' '.join([str(b) for _, b in sorted(reverse(ints+strs))]) print(magick(s)) Answers 6
This solution utilizes a single custom sorting algorithm, after grouping the original input into integers and strings:
def gt(a, b): return a > b if isinstance(a, int) and isinstance(b, int) else a[0].lower() > b[0].lower() def type_sort(d): '''similar to bubble sort, but does not swap elements of different types. For instance, type_sort([5, 3, 'b', 'a']) => [3, 5, 'a', 'b'] ''' for _ in d: for i in range(len(d)-1): _c = d[i] _t = d[i+1] if isinstance(_c, type(_t)): if gt(_c, _t): d[i+1] = _c d[i] = _t return d def get_type(x): return int(x) if x.isdigit() else x def sort_in_place(s:str): _s = list(map(get_type, s.split())) new_s = type_sort([i for i in _s if isinstance(i, int)]+[i for i in _s if isinstance(i, str)]) ints = iter(i for i in new_s if isinstance(i, int)) strings = iter(i for i in new_s if isinstance(i, str)) return ' '.join(map(str, [next(ints) if isinstance(i, int) else next(strings) for i in _s])) print(sort_in_place(a)) Output:
'8 a car have 12 200 I' 
0 comments:
Post a Comment