Given a Integer list, sort by unit digits.
Input : test_list = [76, 434, 23, 22342]
Output : [22342, 23, 434, 76]
Explanation : 2 < 3 < 4 < 6, sorted by unit digits.Input : test_list = [76, 4349, 23, 22342]
Output : [22342, 23, 76, 4349]
Explanation : 2 < 3 < 6 < 9, sorted by unit digits.
Method #1 : Using sort() + str()
In this, we perform sort using sort() and str() is used to convert integers to string, and then sort by last digit.
Python3
# Python3 code to demonstrate working of# Sort by Units Digit in List# Using sort() + str()# helpr_fnc to sortdef unit_sort(ele): # get last element return str(ele)[-1]# initializing liststest_list = [76, 434, 23, 22342]# printing original listsprint("The original list is : " + str(test_list))# inplace sort by unit digitstest_list.sort(key=unit_sort)# printing resultprint("The unit sorted list : " + str(test_list)) |
Output:
The original list is : [76, 434, 23, 22342] The unit sorted list : [22342, 23, 434, 76]
Method #2 : Using sorted() + lambda + str()
In this, we perform task of sorting using sorted() and lambda function is used to avoid external function call.
Python3
# Python3 code to demonstrate working of# Sort by Units Digit in List# Using sorted() + lambda + str()# initializing liststest_list = [76, 434, 23, 22342]# printing original listsprint("The original list is : " + str(test_list))# inplace sort by unit digitsres = sorted(test_list, key=lambda sub: str(sub)[-1])# printing resultprint("The unit sorted list : " + str(res)) |
Output:
The original list is : [76, 434, 23, 22342] The unit sorted list : [22342, 23, 434, 76]
Method 3: Using the heapq.nsmallest() function
This approach involves using a heap data structure to extract the smallest elements based on a key function that returns the last digit of a number
Python3
# Python3 code to demonstrate working of# Sort by Units Digit in List# Using heapq.nsmallest() and lambda functionimport heapq# initializing liststest_list = [76, 434, 23, 22342]# printing original listprint("The original list is : " + str(test_list))# sort by unit digits using heapq.nsmallest() and lambda functiontest_list = heapq.nsmallest(len(test_list), test_list, key=lambda x: str(x)[-1])# printing resultprint("The unit sorted list : " + str(test_list)) |
The original list is : [76, 434, 23, 22342] The unit sorted list : [22342, 23, 434, 76]
Time complexity: O(n log n)
Auxiliary space: O(1)
Method 4: Using list comprehension and the sorted() function:
Algorithm:
1.Define a list of integers called test_list.
2.Use the sorted() function to sort the list by the units digit of each element.
3.Create a new list comprehension called sorted_list to store the sorted list.
4.Print the original and sorted lists to the console.
Python3
# Define a list comprehension to sort a list by its units digittest_list = [76, 434, 23, 22342]sorted_list = [x for x in sorted(test_list, key=lambda x: x % 10)]# Print the original and sorted listsprint("Original list:", test_list)print("Sorted list:", sorted_list)#This code is contributed by Jyothi pinjala. |
Original list: [76, 434, 23, 22342] Sorted list: [22342, 23, 434, 76]
Time complexity:
Sorting the list using the sorted() function takes O(n log n) time in the worst case.
Creating a new list using a list comprehension takes O(n) time in the worst case.
Therefore, the overall time complexity of this algorithm is O(n log n).
Auxiliary Space:
The space required to store the original list and the sorted list is O(n).
The space required for the lambda function used by sorted() is constant.
Therefore, the overall space complexity of this algorithm is O(n).
Method 5: Using a custom function and the sorted() function:
This method defines a custom function sort_by_units_digit() that sorts the list based on the last digit of each element. The sorted() function is then used to sort the list using the custom function.
Python3
def sort_by_units_digit(lst): return sorted(lst, key=lambda x: str(x)[-1])# initializing liststest_list = [76, 434, 23, 22342]# printing original listprint("The original list is : " + str(test_list))# sort by unit digits using custom function and sorted() functiontest_list = sort_by_units_digit(test_list)# printing resultprint("The unit sorted list : " + str(test_list)) |
The original list is : [76, 434, 23, 22342] The unit sorted list : [22342, 23, 434, 76]
Time complexity: O(nlogn) because it uses the built-in sorted() function, which has a worst-case time complexity of O(nlogn). The lambda function used to extract the last digit has a time complexity of O(1).
Auxiliary space: O(n) because it creates a new list to store the sorted elements
Method 6 : Using the bucket sort algorithm.
steps to implement this approach:
Create ten empty buckets, one for each possible unit digit (0 to 9).
Traverse the input list and put each number in its corresponding bucket based on its unit digit.
Sort each bucket using any sorting algorithm (such as insertion sort or quicksort).
Concatenate the sorted buckets to form the sorted list.
Python3
def sort_by_units_digit(nums): # Step 1: Create ten empty buckets buckets = [[] for _ in range(10)] # Step 2: Put each number in its corresponding bucket for num in nums: digit = num % 10 buckets[digit].append(num) # Step 3: Sort each bucket for i in range(10): buckets[i].sort() # Step 4: Concatenate the sorted buckets sorted_nums = [] for i in range(10): sorted_nums += buckets[i] return sorted_nums# Example usagetest_list = [76, 434, 23, 22342]sorted_list = sort_by_units_digit(test_list)# Print the original and sorted listsprint("Original list:", test_list)print("Sorted list:", sorted_list) |
Original list: [76, 434, 23, 22342] Sorted list: [22342, 23, 434, 76]
Time complexity: O(n + 10k log k), where n is the length of the input list and k is the average number of elements in each bucket. Since k <= n/10, the time complexity can be simplified to O(n log n).
Auxiliary space: O(n), for the buckets and the output list.
Method 7 : Using counting sort algorithm.
Find the maximum number in the input list nums.
Create a count array of size 10, initialized with zeros. This count array will be used to store the count of each units digit.
Iterate through each number in the input list nums. For each number, calculate its units digit by taking the modulo 10. Increment the count of that units digit in the count array.
Compute the cumulative sum of the count array. Starting from index 1, add the value at the current index with the value at the previous index. This step helps determine the correct positions of elements in the sorted list.
Create an output array of the same size as the input list nums, initialized with zeros. This output array will store the sorted list.
Traverse the input list nums in reverse order (from right to left). For each number, calculate its units digit using modulo 10. Use the count array to determine the position of the current number in the output array.
Decrement the count of the units digit in the count array.
Copy the current number to the determined position in the output array.
Return the sorted list stored in the output array.
Python3
def sort_by_units_digit(nums): # Step 1: Find the maximum number in the list max_num = max(nums) # Step 2: Create a count array of size 10 count = [0] * 10 # Step 3: Increment the count of each units digit for num in nums: digit = num % 10 count[digit] += 1 # Step 4: Compute the cumulative sum of the count array for i in range(1, 10): count[i] += count[i - 1] # Step 5: Create an output array output = [0] * len(nums) # Step 6: Traverse the input list from right to left for num in reversed(nums): digit = num % 10 position = count[digit] - 1 # Step 7: Decrement the count of the units digit count[digit] -= 1 # Step 8: Copy the element to the output array output[position] = num # Step 9: Return the sorted list return output# Example usagetest_list = [76, 434, 23, 22342]sorted_list = sort_by_units_digit(test_list)# Print the original and sorted listsprint("Original list:", test_list)print("Sorted list:", sorted_list) |
Original list: [76, 434, 23, 22342] Sorted list: [22342, 23, 434, 76]
Time complexity: O(n)
Auxiliary space complexity: O(n)
