USING JAVA There are at least two types of nearly sorted arr

USING JAVA:

There are at least two types of \"nearly sorted\" arrays: k-exchanges and k-distance, where k is an integer. An array is called a k-exchanges array if the array becomes sorted by performing at most k exchanges. For example, sorting.java uses 100-exchanges for nearly sorted arrays. An array is called a k-distance array if, for each element, the distance from its initial position to its position in the sorted array is no more than k. A k-distance array can be created from a sorted array by randomly shuffling each subarray of size k. www.sorting-algorithms.com uses 1-distance for nearly sorted arrays.compare the performances of quicksort (choosing the best quicksort you have), heapsort, mergesort, natural mergesort, and insertion sort on k-exchanges and k-distances arrays for various k values. Create a method called task4, which takes k = 10, 20, 30, ..., until quicksort becomes a clear winner, create 100 k-distance arrays of size 10,000,000, run in turn the chosen sorting methods on each array, and collect running times. Then for k = 100, 200, 300, ..., until quicksort becomes a clear winner, create 100 k-exchange arrays of size 10,000,000, run in turn the chosen sorting methods on each array, and collect running times.

I have the code for all the algorithms done correctly, so just call them by quicksort(), heapsort(), mergesort(), naturalmergesort(), insertionsort(). I can figure out how to deal with differing sizes but what I don\'t understand is how to create k-distance and k-exchanges nearly sorted arrays.

Solution

void insertionSort(int A[], int size)
{
int i, key, j;
for (i = 1; i < size; i++)
{
key = A[i];
j = i-1;

/* Move elements of A[0..i-1], that are greater than key, to one
position ahead of their current position.
This loop will run at most k times */
while (j >= 0 && A[j] > key)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = key;
}
}

he inner loop will run at most k times. To move every element to its correct place, at most k elements need to be moved. So overall complexity will be O(nk)

We can sort such arrays more efficiently with the help of Heap data structure. Following is the detailed process that uses Heap.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.

Removing an element and adding a new element to min heap will take Logk time. So overall complexity will be O(k) + O((n-k)*logK)

#include<iostream>
using namespace std;

// Prototype of a utility function to swap two integers
void swap(int *x, int *y);

// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int heap_size; // size of min heap
public:
// Constructor
MinHeap(int a[], int size);

// to heapify a subtree with root at given index
void MinHeapify(int );

// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }

// to remove min (or root), add a new value x, and return old root
int replaceMin(int x);

// to extract the root which is the minimum element
int extractMin();
};

// Given an array of size n, where every element is k away from its target
// position, sorts the array in O(nLogk) time.
int sortK(int arr[], int n, int k)
{
// Create a Min Heap of first (k+1) elements from
// input array
int *harr = new int[k+1];
for (int i = 0; i<=k && i<n; i++) // i < n condition is needed when k > n
harr[i] = arr[i];
MinHeap hp(harr, k+1);

// i is index for remaining elements in arr[] and ti
// is target index of for cuurent minimum element in
// Min Heapm \'hp\'.
for(int i = k+1, ti = 0; ti < n; i++, ti++)
{
// If there are remaining elements, then place
// root of heap at target index and add arr[i]
// to Min Heap
if (i < n)
arr[ti] = hp.replaceMin(arr[i]);

// Otherwise place root at its target index and
// reduce heap size
else
arr[ti] = hp.extractMin();
}
}

MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}

// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
int root = harr[0];
if (heap_size > 1)
{
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);
}
return root;
}

// Method to change root with given value x, and return the old root
int MinHeap::replaceMin(int x)
{
int root = harr[0];
harr[0] = x;
if (root < x)
MinHeapify(0);
return root;
}

// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}

// A utility function to swap two elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}

// A utility function to print array elements
void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
cout << arr[i] << \" \";
cout << endl;
}

// Driver program to test above functions
int main()
{
int k = 3;
int arr[] = {2, 6, 3, 12, 56, 8};
int n = sizeof(arr)/sizeof(arr[0]);
sortK(arr, n, k);

cout << \"Following is sorted array\ \";
printArray (arr, n);

return 0;
}