Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- // Read in k, which represents the maximum
- // distance between a number's current position
- // and sorted position
- int k = Integer.parseInt(sc.nextLine());
- // Read in the list of numbers
- int[] numbers;
- String input = sc.nextLine();
- if (input.equals("")) {
- numbers = new int[0];
- } else {
- String[] numberStrings = input.split(" ");
- numbers = new int[numberStrings.length];
- for (int i = 0; i < numberStrings.length; i++) {
- numbers[i] = Integer.parseInt(numberStrings[i]);
- }
- }
- // Sort the list
- sort(numbers, k);
- // Print the sorted list
- StringBuilder resultSb = new StringBuilder();
- for (int i = 0; i < numbers.length; i++) {
- resultSb.append(new Integer(numbers[i]).toString());
- if (i < numbers.length - 1) {
- resultSb.append(" ");
- }
- }
- System.out.println(resultSb.toString());
- }
- // Merges two subarrays of arr[].
- // First subarray is arr[l..m]
- // Second subarray is arr[m+1..r]
- public static void merge(int arr[], int l, int m, int r)
- {
- // Find sizes of two subarrays to be merged
- int n1 = m - l + 1;
- int n2 = r - m;
- /* Create temp arrays */
- int L[] = new int [n1];
- int R[] = new int [n2];
- /*Copy data to temp arrays*/
- for (int i=0; i<n1; ++i)
- L[i] = arr[l + i];
- for (int j=0; j<n2; ++j)
- R[j] = arr[m + 1+ j];
- /* Merge the temp arrays */
- // Initial indexes of first and second subarrays
- int i = 0, j = 0;
- // Initial index of merged subarry array
- int k = l;
- while (i < n1 && j < n2)
- {
- if (L[i] <= R[j])
- {
- arr[k] = L[i];
- i++;
- }
- else
- {
- arr[k] = R[j];
- j++;
- }
- k++;
- }
- /* Copy remaining elements of L[] if any */
- while (i < n1)
- {
- arr[k] = L[i];
- i++;
- k++;
- }
- /* Copy remaining elements of R[] if any */
- while (j < n2)
- {
- arr[k] = R[j];
- j++;
- k++;
- }
- }
- // Main function that sorts arr[l..r] using
- // merge()
- // r inclusive
- public static void mergesort(int arr[], int l, int r)
- {
- if (l < r)
- {
- // Find the middle point
- int m = (l+r)/2;
- // Sort first and second halves
- mergesort(arr, l, m);
- mergesort(arr , m+1, r);
- // Merge the sorted halves
- merge(arr, l, m, r);
- }
- }
- static void printArray(int arr[])
- {
- System.out.println("Current Array State\n---------------------\n");
- int n = arr.length;
- for (int i=0; i<n; ++i)
- System.out.print(arr[i] + " ");
- System.out.println();
- }
- public static void sort(int[] numbers, int k) {
- // TODO implement this function
- int start = 0;
- int len = numbers.length;
- if (len <= k) {
- mergesort(numbers, start, len-1);
- return;
- }
- mergesort(numbers,start,k-1);
- printArray(numbers);
- while(start<len) {
- System.out.println(start+" "+k);
- if( (start+k)>=len ) break;
- if( (start+2*k)>=len ) {
- mergesort(numbers, start+k, len-1);
- merge(numbers, start, start+k-1, len-1);
- break;
- }
- mergesort(numbers, start+k, start+2*k);
- merge(numbers, start, start+k-1, start+2*k);
- printArray(numbers);
- start += k+1;
- }
- printArray(numbers);
- //throw new UnsupportedOperationException();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement