CODEWITHSUNDEEP
arraysalgorithmsortingdata-structures
user5927605
user5927605

Reputation:

Minimum Time for Partially Sorted Array?

We are given a partially sorted array A, i.e. for i=1, 2, ..., n-k we have: 

A[i]<= A[i+k]

For sorting array completely, we need at least O(n log k) time.

what is the condition and solution that make this axiom is true always?

Upvotes: 2

Views: 200

Answers (1)

Ali Soltani
Ali Soltani

Reputation: 9927

You can use shell sort from this problem.In this algorithm,After each phase and some increment hk, for every i, we have a[ i ] ≤ a [ i + hk ]. all elements spaced hk apart are sorted. This array is said to be hk – sorted. output of shell sort is 1-sorted. if array is k-sorted then shell sort need O(log k) for sort array completely. each phase need O(n) then total order is O(n log k).

Suppose we want to sort this array:

enter image description here

this array is 4-sorted (k=4). for sorting this, Is needed to 2 phases (h2 = 2, h3 = 1) So two phases are needed (lg 4 or lg k). At each phase, there are n/k sub arrays that must be sorted. every sub array sort with insertion sort. Order of sort each sub array is O(n). Finally, Total order O(n*lg k) = O(n log k).

Upvotes: 1

Related Questions