Sorting integers with restrictions
if we have an array of integers, then how can we determine the minimum steps required to sort them (in ascending order) if the permitted operation at each step is to move elements to extremes? For example, if we have
7 8 9 11 1 10
then in the 1st step you can move 11 to the right end and in the second step you can move 1 to the left end to get 1 7 8 9 10 11. So general steps = 2
Can we use a bubble here? but the worst case will be O (n ^ 2). So how can we act more effectively? Thank you.
source to share
Here is a solution that takes O (n log n) time, O (n) auxiliary space, and exactly n MoveToFront operations.
Given the input array, A, create a second array, B, with index values / pairs like ...
7 8 9 11 1 10 -> (7 0) (8 1) (9 2) (11 3) (1 4) (10 5)
[this step takes O(n) time and O(n) space]
then sort B in descending order of the value of each pair ...
(7 0) (8 1) (9 2) (11 3) (1 4) (10 5) -> (11 3) (10 5) (9 2) (8 1) (7 0) (1 4)
[this step takes O(n log n) time]
prepare a binary search tree, T.
Now for each item from B do the following ...
Let I be the index of this element.
Let V be the sum of I and the number of elements in T that are greater than I.
Do a MoveToFront operation on the Vth element of A.
Add I to T.
[Both of the operations on T take O(log n) time]
Here is this algorithm working on your array of examples
(11 3)
I := 3
V := 3 + 0 = 3
MoveToFront(3): 7 8 9 11 1 10 -> 11 7 8 9 1 10
T: () -> (3)
(10 5)
I := 5
V := 5 + 0 = 5
MoveToFront(5): 11 7 8 9 1 10 -> 10 11 7 8 9 1
T: (3) -> (3 5)
(9 2)
I := 2
V := 2 + 2 = 4
MoveToFront(4): 10 11 7 8 9 1 -> 9 10 11 7 8 1
T: (3 5) -> (2 3 5)
(8 1)
I := 1
V := 1 + 3 = 4
MoveToFront(4): 9 10 11 7 8 1 -> 8 9 10 11 7 1
T: (2 3 5) -> (1 2 3 5)
(7 0)
I := 0
V := 0 + 4 = 4
MoveToFront(4): 8 9 10 11 7 1 -> 7 8 9 10 11 1
T: (1 2 3 5) -> (0 1 2 3 5)
(1 4)
I := 4
V := 4 + 1 = 5
MoveToFront(5): 7 8 9 10 11 1 -> 1 7 8 9 10 11
T: (0 1 2 3 5) -> (0 1 2 3 4 5)
I suppose you can find ways to sort these arrays that use fewer MoveToFront / Back operations, but I don't think you can find them in less than O (n log n) time. However, if these operations are slow, then it might be worth using an algorithm that takes longer to schedule, so you can do fewer of these operations.
source to share
Can you clarify this issue a bit? When you say list, do you mean a linked list, or do you mean an array? If it's not a linked list, I'm a little confused about the limited set of operations. If it's a linked list, you can probably change quicksort, which runs in O (nlgn) average time.
source to share
This doesn't sound like a sorting problem to me. You just need to find how many movements you need to do, but you don't need to sort the array. I bet it can be done faster than O (n log n)
I suggest this solution: just count how many [i]> a [i - 1]. And that will be your result.
Argumentation: If you have [i]> a [i-1], it means that either [i] or [i-1] is not in place. Thus, you can:
1) move [i-1] to the beginning of the array
2) move [i] to the end of the array.
Update. ... You need to determine which of [i] or [i-1] you are moving, as in your example for an array: 7 8 9 11 1 10 you have two comparisons that show what is out of place: 11> 1 and 11 > 10. So this is definitely a dynamic programming challenge . But it's still faster than O (n log n)
source to share