Problem #2: (a) Given a binary array, implement in Java an algorithm to sort it in linear running time complexity and constant space complexity. Example: Input: [1,0,1,0,0,0,1,0,1,0,0,1] Output: [0,0,0,0,0,0,0,1,1,1,1,1] (b.1) Implement (in Java) the RadixSort algorithm to sort (in increasing order) an array of nonnegative integer keys. public void radixSort(int arr[]) In your implementation you must consider that each key contains only even digits (0, 2, 4, 6, and 8). Your program must detect the case of odd digits in the keys, and, in this case, your program must replace each odd digit by the greater even digit that is less than the odd digit. Examples: 3 --> 2; 9 --> 8; 1 --> 0. Example of the output of the program: Input array 13, 4680, 24062, 51, 86, 642, 51, 426, 888, After preprocessing (convert odd digits into even digits) 2, 4680, 24062, 40, 86, 642, 40, 426, 888, Sorted array 2, 40, 40, 86, 426, 642, 888, 4680, 24062, Note: To storage and process the bucket lists, use an ArrayList structure. (b.2) What is the running time complexity of your radixSort method? Justify.
Midiel/radixSort
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
About
No description, website, or topics provided.
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published