// Exercise 19.7 Solution: Bucketsort.java / sort an array\'s values into ascend

Question

// Exercise 19.7 Solution: Bucketsort.java / sort an array's values into ascending order using bucket sort import java.util.Random / determine the divisor used to get specific digit (Hint: use Math.pow.) for (int element : data) public class BucketSort // bucket Number example for hundreds digit: // (1234 1000) / 100 --> 2 int bucketNumber = (element ? divisor) / (divisor / 10); / You are provided with these declarations private int[] data; / array of values private static Random generator new Random(); // retrieve value in pail[bucketNumber]10] to // determine which element of the row to store clil / create a constructor with an array and fill with random integers public Bucketsort(int size) / end for end method distributeElements // return elements to original array public void collectElements(int pails[][]) /I perform the bucket sort algorithm on array public void sort) / initialize location in data // store maximum number of digits in numbers to sort / loop over "buckets // loop over elements in each bucket (column) I add element to array // bucket array where numbers will be placed II loop through all digit places and sort each number II according to digit place value for (int pass 1; passtotalDigits pass) et all buckets to zero public void emptyBucket (int paila[1) // set size of bucket to 0 / distribution pasB / gathering pass // reset original array // method to output values in array public String tostring) /I determine number of digits in the largest nunber public int numberofDigits() ) end class Bucketsort // set largest to first element / loop over elements to find largest II calculate and return the number of digits in largest value *(C) Copyright 1992-2015 by Deitel& Associates, Inc. and *Pearson Education, Inc. All Rights Reserved * DISCLAIMER: The authors and publisher of this book have used their *best efforts in preparing * development, research, and testing of the theories and programs * to determine their effectiveness. The authors and publisher make * no warranty of any kind, expressed or implied, with regard to these* * programs or to the documentation contained in these books. The authors * the book. These efforts include the / distribute elements into buckets based on specified digit public void distributeElenents(int pail[l], int digit) /1 determine the divisor used to get specific digit (Hint: use Math.pow.and publisher shall not be liable in any event for incidental or ntial damages in connection with, or arising out of, the *conseque

Explanation / Answer

/**
* BucketSort: mainly sort an array with elements uniformly distributed over a range.
*
* Worst Case Time Complexity: O(n^2).
* Best and Average Case Time Complexity: O(n + k).
* Space Complexity: O(n * k).
*
*/

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class BucketSort {

private static final int DEFAULT_BUCKET_SIZE = 5;

public static void sort(int[] arr) { // 1) Create n empty buckets
  
bucketSort(arr, DEFAULT_BUCKET_SIZE);
}

public static void bucketSort(int arr[], int size) {
if (arr.length == 0) return;

Integer minValue = arr[0];
Integer maxValue = arr[0];
for (int i = 1; i < arr.length; i++) { //minimum value in array
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) { //maximum array in array
maxValue = arr[i];
}
}

int bucketCount = (maxValue - minValue) / size + 1;
List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<Integer>());
}

for (int i = 0; i < arr.length; i++) {
buckets.get((arr[i] - minValue) / size).add(arr[i]);
}

int currentIndex = 0;
for (int i = 0; i < buckets.size(); i++) { // Put array elements in different buckets
Integer[] bucketArray = new Integer[buckets.get(i).size()]; // Index in bucket
bucketArray = buckets.get(i).toArray(bucketArray);
InsertionSort.sort1(bucketArray); // Sort individual buckets
for (int j = 0; j < bucketArray.length; j++) { // Concatenate all buckets into arr[]
arr[currentIndex++] = bucketArray[j];
}
}
}

public static void main(String[] args) {
int[] arr1 = {10, 3, 7, 5, 1, 15, 20};
BucketSort.sort(arr1);
System.out.println(Arrays.toString(arr1));

int[] arr2 = {};
BucketSort.sort(arr2);
System.out.println(Arrays.toString(arr2));

int[] arr3 = {10};
BucketSort.sort(arr3);
System.out.println(Arrays.toString(arr3));
}

}
class InsertionSort {
public static void sort1(int[] arr) {
for (int i=1; i < arr.length; i++) {
int curr = arr[i];
int j = i-1;

while (j >= 0 && arr[j] > curr) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}

public static void sort1(Integer[] arr) {
for (int i=1; i < arr.length; i++) {
int curr = arr[i];
int j = i-1;

while (j >= 0 && arr[j] > curr) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
}

The output of the program in NetBeans:

run:
[1, 3, 5, 7, 10, 15, 20]
[]
[10]
BUILD SUCCESSFUL (total time: 2 seconds)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.