Sorting --- in Java • Your task is to design and implement a sorting algorithm t

Question

Sorting --- in Java

• Your task is to design and implement a sorting algorithm that can sort integers that are less than or equal to L and greater than or equal to –L.

• You will have a large array of numbers, of size N e.g. N=10,000, L=30: you have 10,000 numbers to sort, but the numbers are only from [-30...30] range

• You should design an algorithm that works in O(N+L) time, that is, running time grows as a linear function of the array size, as long as L is not changed • Hint: Use one of the Majority Element algorithms for inspiration in your thinking about the algorithm

Input-output formats

• Take integers from standard input (System.in): – Line 1: single integer specifying N, number of elements in array (1<=N<=100,000) – Line 2: single integer specifying L, limit on the absolute value of the integers in the array (1<=L<=100) – Lines 3 to N+2: integers to be sorted, each in range [-L, L].

• Print sorted array to standard output (System.out), with each integer on a separate line • As always, do not print any text or blank lines to standard output except the integers

• As always, do not print any text or blank lines to standard output except the integers

Explanation / Answer

Code:

import java.util.Random;
public class Main {
public static void main(String[] args) {
  
int[] Array = generateArray(-30,30);
System.out.println("Unsorted Array:");
printArray(Array);
sortArray(Array);
System.out.println("Sorted data:");
printArray(Array);

}

private static void sortArray(int[] Array) {
for (int i=0; i<Array.length-1; i++) {
for (int j=i+1; j<Array.length; j++) {
if (Array[i] > Array[j]) {
int temp = Array[i];
Array[i] = Array[j];
Array[j] = temp;
}
}
}
}
private static int[] generateArray(int min,int max) {
Random random = new Random();
int[] Array = new int[100];
for (int i=0; i<Array.length; i++) {
Array[i] = min+random.nextInt(max-min);
}
return Array;
}
private static void printArray(int[] Array) {
for (int i=0; i<Array.length; i++) {
System.out.print(Array[i]);
System.out.print(", ");
}
System.out.println();
}
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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