CareerCup

To sort it way you have to build a heap and maintain its size to be always = x
1- start by adding x elements to the queue
2- Each time you encounter a new element remove the head of the heap (Min element) and append it to the result(This element must be the smallest element in the stream)
3- Add the new element and continue

Assuming ascending sort criterion, how about we create a heap of x elements and insert the first x list elements. Since the list sorting is off by x elements, the smallest should be in the heap. Then keep adding one additional element to the heap and extract the next min element.

We can consider x sorted lists, and do a merge to combine these x lists to find the final sorted list L.

Merge K sort. Use heap.

First we add 2*x elements to priority queue and take first x elements - these are first x sorted elements. Then we add next block of x elements and do the same till the end of the list

1. Find the minimum element starting from 1 to x elements of list and swap it with first element of the list
2. Find the minimum element starting from 2 to x +1 and swap it with 2nd element of the list and continue the similar process until (n - step) times, where n is length of list.

def my_min_index(part_list):
    min_index = 0
    n = len(part_list)
    i = 1
    print(part_list, n)
    while i < n:
        if part_list[i] < part_list[min_index]:
            min_index = i
        i += 1
    return min_index


def x_sorted(input_list, step):
    print("Unsorted list : {0}".format(input_list))
    i = 0
    n = len(input_list)
    while i <= ((n - step) + 1):
        cur_min_index = i + my_min_index(input_list[i:i+step])
        print(cur_min_index, input_list[cur_min_index])
        input_list[i], input_list[cur_min_index] = input_list[cur_min_index], input_list[i]
        i += 1
        print(input_list)
    print("Sorted list : {0}".format(input_list))
    return input_list


x = [2,3,1,7,8,4,5,9,6]
x_sorted(x, 3)

@Naz20 - Yep, totally agreed. This is basically right in the middle of a merge-sort operation. At the base of the recursion of merge sorts, you have L.length lists of size 1, and as they merge, somewhere up the recursion tree you have x sorted lists of size L.length / x. When x == 1 (top of recursion tree), you have L fully sorted.

hi

Hello,
I appreciate ur solution but I think this wouldn't work, inf act it is not supporting the presorted condition in the problem. The input which you have taken is not presorted by x terms. See the below example Input..

Input List: 5 1 10 15 2 11 20...so on...and x=3
see the sorted sublists are: 5 15 20 and 1 2 and 10 11...

Thanks

Use a min-heap. add first x elements to the heap. then,

1. pick out smallest element, find it's index i by parsing elements in L from 0..x-1
2. if (i+x) < len(L) add L[i+x] to the min heap. go to step 1
3. else do nothing, go back to step 1.

Use min heap, with x+1 elements,
1. add x+1 elements into heap
2. remove element from heap, and add the next element from input array, if available
3. repeat the process of step 2 till heap has more elements.
4. Complexity is O(xlogx)

Two approaches are proposed. The basic idea is similar as merging sorted list. Here we have X sorted list.
Details: cpluspluslearning-petert.blogspot.co.uk/2016/04/merge-x-way-sorted-list.html
Test

void Test_LL()
{
    {
        LinkedList<int> input;
        LinkedList<int> result;
        input.PushBack(1);
        MergeXwaySortedLL(input, 1, result);
        LinkedListElement<int> *head = *(result.Release());
        LinkedListElement<int> *tail = *(result.ReleaseTail());
        assert(head->data == 1);
        assert(tail->data == 1);
    }

    {
        LinkedList<int> input;
        LinkedList<int> result;
        const std::array<int, 16> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
        for (auto iter = data.begin(); iter != data.end(); ++iter) {
            input.PushBack(*iter);
        }

        MergeXwaySortedLL(input, 4, result);
        LinkedListElement<int> *curNode = *(result.Release());
        unsigned int count = 0;
        while (curNode) {
            assert(curNode->data == count);
            curNode = curNode->next;
            ++count;
        }

        assert(count == 16);
    }
}

void Test_Arr()
{
    {
        const std::vector<int> data = { 1, 3, 2, 4 };
        std::vector<int> result = MergeXwaySortedArr(data, 5);
        assert(result.empty() == true);
        result = MergeXwaySortedArr(data, 2);
        assert(result == std::vector<int>({ 1, 2, 3, 4 }));
    }

    {
        const std::vector<int> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
        std::vector<int> result = MergeXwaySortedArr(data, 17);
        assert(result.empty() == true);
        result = MergeXwaySortedArr(data, 4);
        assert(result == std::vector<int>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}));
    }
}

Insertion sort gives O(nk) running time.

Hello,
I appreciate ur solution but I think this wouldn't work, inf act it is not supporting the presorted condition in the problem. The input which you have taken is not presorted by x terms. See the below example Input..

Input List: 5 1 10 15 2 11 20...so on...and x=3
see the sorted sublists are: 5 15 20 and 1 2 and 10 11...

Thanks