3 edited title

# Sorting an already k-sorting ansorted array

2 corrected writing, formatting, tags.

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

• We say that an array $$A[1...n]$$ is $$k$$-sorted if it can be divided into $$k$$ blocks, each of size $$n/k$$, such that the elements in each block are larger than the elementsin each block are larger than the elements in earlier blocks, and smaller than the elementos in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

a)Describe an algorithm that k-sorts an arbitrary array in time $$O(nlogk)$$.

b) Prove that any comparison-based k-sorting algorithm requires $$\Omega(n log k)$$ comparisons in the worst case.

c) Describe an algorithm that completely sorts an already $$k$$-sorted array in time $$O(n log(n/k))$$.

We say that an array $$A[1...n]$$ is $$k$$-sorted if it can be divided into $$k$$ blocks, each of size $$n/k$$, such that the elements in each block are larger than the elements in earlier blocks, and smaller than the elements in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

a) Describe an algorithm that $$k$$-sorts an arbitrary array in time $$O(n\log k)$$.

b) Prove that any comparison-based $$k$$-sorting algorithm requires $$\Omega(n \log k)$$ comparisons in the worst case.

c) Describe an algorithm that completely sorts an already $$k$$-sorted array in time $$O(n \log(n/k))$$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how can I achieveto solve this.

For a) my teacher said that we need to find the median and then do something like what quicksort does on finding a good pivot.I I was searching over the net and I had the idea to put the k$$k$$ first elements as leafs of a min-heap and then take the min element and then takingwith the next element of the array fillingfill each block with $$n/k$$ elements, but it fails with the input: $$8, 7, 6, 5, 4, 3, 2, 1$$

ForClearly, b) clearly is something like to proveproving that any algorithm based in comparisons takes $$O(nlogn)$$$$O(n\log n)$$. Maybe $$log\ k$$$$\log k$$ is because we only need to sort each block with n/k$$n/k$$ elements, that means for each block we need to do $$O(n/k*log\ k)$$ k$$O(n/k \times\log k)$$ $$k$$ times, so we really need tocould actually do it: in time $$O(k*n/k*log\ k) = O(nlog\ k)$$$$O(k\times n/k \times \log k) = O(n\log k)$$

For c) I'm not prettyreally sure, but I can take all the elements of each block and put itthem as leafs of a min-heap, $$-$$ which gives $$O(log\ n/k)$$and$$O(\log n/k)$$ $$-$$ and then sort them, which I think it would take $$O(n\ log\ n/k)$$$$O(n \log n/k)$$.

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

• We say that an array $$A[1...n]$$ is $$k$$-sorted if it can be divided into $$k$$ blocks, each of size $$n/k$$, such that the elements in each block are larger than the elementsin each block are larger than the elements in earlier blocks, and smaller than the elementos in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

a)Describe an algorithm that k-sorts an arbitrary array in time $$O(nlogk)$$.

b) Prove that any comparison-based k-sorting algorithm requires $$\Omega(n log k)$$ comparisons in the worst case.

c) Describe an algorithm that completely sorts an already $$k$$-sorted array in time $$O(n log(n/k))$$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how can I achieve this.

For a) my teacher said that we need to find the median and then do something like quicksort does on finding a good pivot.I was searching over the net and I had the idea to put the k first elements as leafs of a min-heap and then take the min element and then taking the next element of the array filling each block with $$n/k$$ elements but it fails with the input: $$8, 7, 6, 5, 4, 3, 2, 1$$

For b) clearly is something like to prove that any algorithm based in comparisons takes $$O(nlogn)$$. Maybe $$log\ k$$ is because we only need to sort each block with n/k elements, that means for each block we need to do $$O(n/k*log\ k)$$ k times, so we really need to do it: $$O(k*n/k*log\ k) = O(nlog\ k)$$

For c) I'm not pretty sure, but I can take all the elements of each block and put it as leafs of a min-heap, which gives $$O(log\ n/k)$$and then sort them which I think it would take $$O(n\ log\ n/k)$$.

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

We say that an array $$A[1...n]$$ is $$k$$-sorted if it can be divided into $$k$$ blocks, each of size $$n/k$$, such that the elements in each block are larger than the elements in earlier blocks, and smaller than the elements in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

a) Describe an algorithm that $$k$$-sorts an arbitrary array in time $$O(n\log k)$$.

b) Prove that any comparison-based $$k$$-sorting algorithm requires $$\Omega(n \log k)$$ comparisons in the worst case.

c) Describe an algorithm that completely sorts an already $$k$$-sorted array in time $$O(n \log(n/k))$$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how to solve this.

For a) my teacher said that we need to find the median and then do something like what quicksort does on finding a good pivot. I was searching over the net and I had the idea to put the $$k$$ first elements as leafs of a min-heap and then take the min element and with the next element of the array fill each block with $$n/k$$ elements, but it fails with the input: $$8, 7, 6, 5, 4, 3, 2, 1$$

Clearly, b) is something like proving that any algorithm based in comparisons takes $$O(n\log n)$$. Maybe $$\log k$$ is because we only need to sort each block with $$n/k$$ elements, that means for each block we need to do $$O(n/k \times\log k)$$ $$k$$ times, so we could actually do it in time $$O(k\times n/k \times \log k) = O(n\log k)$$

For c) I'm not really sure, but I can take all the elements of each block and put them as leafs of a min-heap $$-$$ which gives $$O(\log n/k)$$ $$-$$ and then sort them, which I think would take $$O(n \log n/k)$$.

1

# k-sorting an array

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

• We say that an array $$A[1...n]$$ is $$k$$-sorted if it can be divided into $$k$$ blocks, each of size $$n/k$$, such that the elements in each block are larger than the elementsin each block are larger than the elements in earlier blocks, and smaller than the elementos in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

a)Describe an algorithm that k-sorts an arbitrary array in time $$O(nlogk)$$.

b) Prove that any comparison-based k-sorting algorithm requires $$\Omega(n log k)$$ comparisons in the worst case.

c) Describe an algorithm that completely sorts an already $$k$$-sorted array in time $$O(n log(n/k))$$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how can I achieve this.

For a) my teacher said that we need to find the median and then do something like quicksort does on finding a good pivot.I was searching over the net and I had the idea to put the k first elements as leafs of a min-heap and then take the min element and then taking the next element of the array filling each block with $$n/k$$ elements but it fails with the input: $$8, 7, 6, 5, 4, 3, 2, 1$$

For b) clearly is something like to prove that any algorithm based in comparisons takes $$O(nlogn)$$. Maybe $$log\ k$$ is because we only need to sort each block with n/k elements, that means for each block we need to do $$O(n/k*log\ k)$$ k times, so we really need to do it: $$O(k*n/k*log\ k) = O(nlog\ k)$$

For c) I'm not pretty sure, but I can take all the elements of each block and put it as leafs of a min-heap, which gives $$O(log\ n/k)$$and then sort them which I think it would take $$O(n\ log\ n/k)$$.