Mixing
Minimum number of operations to sort a list.
$begingroup$
The only operations you can do is take the number in the front and insert it anywhere else in the list. I figured out that you can always do the sorting in less than or equal to n-1 moves. But I need a constructive proof, the process which will produce the optimal result.
combinatorics algorithms
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
$endgroup$
add a comment |
$begingroup$
The only operations you can do is take the number in the front and insert it anywhere else in the list. I figured out that you can always do the sorting in less than or equal to n-1 moves. But I need a constructive proof, the process which will produce the optimal result.
combinatorics algorithms
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
$endgroup$
$begingroup$
I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way?
$endgroup$
– Ingix
Jan 20 at 16:23
$begingroup$
Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:24
$begingroup$
@saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:26
$begingroup$
@ShafinAhmed Okay, I see what you mean now.
$endgroup$
– saulspatz
Jan 20 at 16:32
$begingroup$
It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient.
$endgroup$
– poetasis
Jan 20 at 16:54
add a comment |
$begingroup$
The only operations you can do is take the number in the front and insert it anywhere else in the list. I figured out that you can always do the sorting in less than or equal to n-1 moves. But I need a constructive proof, the process which will produce the optimal result.
combinatorics algorithms
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
$endgroup$
The only operations you can do is take the number in the front and insert it anywhere else in the list. I figured out that you can always do the sorting in less than or equal to n-1 moves. But I need a constructive proof, the process which will produce the optimal result.
combinatorics algorithms
combinatorics algorithms
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
asked Jan 20 at 16:18
Shafin AhmedShafin Ahmed
707
707
$begingroup$
I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way?
$endgroup$
– Ingix
Jan 20 at 16:23
$begingroup$
Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:24
$begingroup$
@saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:26
$begingroup$
@ShafinAhmed Okay, I see what you mean now.
$endgroup$
– saulspatz
Jan 20 at 16:32
$begingroup$
It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient.
$endgroup$
– poetasis
Jan 20 at 16:54
add a comment |
$begingroup$
I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way?
$endgroup$
– Ingix
Jan 20 at 16:23
$begingroup$
Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:24
$begingroup$
@saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:26
$begingroup$
@ShafinAhmed Okay, I see what you mean now.
$endgroup$
– saulspatz
Jan 20 at 16:32
$begingroup$
It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient.
$endgroup$
– poetasis
Jan 20 at 16:54
$begingroup$
I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way?
$endgroup$
– Ingix
Jan 20 at 16:23
$begingroup$
I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way?
$endgroup$
– Ingix
Jan 20 at 16:23
$begingroup$
Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:24
$begingroup$
Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:24
$begingroup$
@saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:26
$begingroup$
@saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:26
$begingroup$
@ShafinAhmed Okay, I see what you mean now.
$endgroup$
– saulspatz
Jan 20 at 16:32
$begingroup$
@ShafinAhmed Okay, I see what you mean now.
$endgroup$
– saulspatz
Jan 20 at 16:32
$begingroup$
It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient.
$endgroup$
– poetasis
Jan 20 at 16:54
$begingroup$
It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient.
$endgroup$
– poetasis
Jan 20 at 16:54
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let the original list be $a_1,a_2,ldots,a_n$. Let $1 le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.
Then the minimum number of operations you need to order that list is $k$.
Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.
Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.
Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.
OTOH, it can be done in $k$ moves:
Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.
An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially
$L_0=[3,2|1,4]$.
We send the $3$ to the position it should have with regards to $1$ and $4$:
$L_1=[2|1,3,4]$
Finally, we send $2$ to the correct place:
$L_2=[|1,2,3,4]$
and the list is completely ordered!
answered Jan 20 at 17:06
IngixIngix
4,672159
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080772%2fminimum-number-of-operations-to-sort-a-list%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let the original list be $a_1,a_2,ldots,a_n$. Let $1 le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.
Then the minimum number of operations you need to order that list is $k$.
Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.
Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.
Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.
OTOH, it can be done in $k$ moves:
Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.
An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially
$L_0=[3,2|1,4]$.
We send the $3$ to the position it should have with regards to $1$ and $4$:
$L_1=[2|1,3,4]$
Finally, we send $2$ to the correct place:
$L_2=[|1,2,3,4]$
and the list is completely ordered!
answered Jan 20 at 17:06
IngixIngix
4,672159
$endgroup$
add a comment |
$begingroup$
Let the original list be $a_1,a_2,ldots,a_n$. Let $1 le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.
Then the minimum number of operations you need to order that list is $k$.
Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.
Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.
Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.
OTOH, it can be done in $k$ moves:
Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.
An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially
$L_0=[3,2|1,4]$.
We send the $3$ to the position it should have with regards to $1$ and $4$:
$L_1=[2|1,3,4]$
Finally, we send $2$ to the correct place:
$L_2=[|1,2,3,4]$
and the list is completely ordered!
answered Jan 20 at 17:06
IngixIngix
4,672159
$endgroup$
add a comment |
$begingroup$
Let the original list be $a_1,a_2,ldots,a_n$. Let $1 le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.
Then the minimum number of operations you need to order that list is $k$.
Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.
Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.
Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.
OTOH, it can be done in $k$ moves:
Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.
An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially
$L_0=[3,2|1,4]$.
We send the $3$ to the position it should have with regards to $1$ and $4$:
$L_1=[2|1,3,4]$
Finally, we send $2$ to the correct place:
$L_2=[|1,2,3,4]$
and the list is completely ordered!
answered Jan 20 at 17:06
IngixIngix
4,672159
$endgroup$
Let the original list be $a_1,a_2,ldots,a_n$. Let $1 le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.
Then the minimum number of operations you need to order that list is $k$.
Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.
Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.
Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.
OTOH, it can be done in $k$ moves:
Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.
An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially
$L_0=[3,2|1,4]$.
We send the $3$ to the position it should have with regards to $1$ and $4$:
$L_1=[2|1,3,4]$
Finally, we send $2$ to the correct place:
$L_2=[|1,2,3,4]$
and the list is completely ordered!
answered Jan 20 at 17:06
IngixIngix
4,672159
answered Jan 20 at 17:06
IngixIngix
4,672159
answered Jan 20 at 17:06
IngixIngix
4,672159
answered Jan 20 at 17:06
IngixIngix
4,672159
4,672159
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080772%2fminimum-number-of-operations-to-sort-a-list%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way?
$endgroup$
– Ingix
Jan 20 at 16:23
$begingroup$
Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:24
$begingroup$
@saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1.
$endgroup$
– Shafin Ahmed
Jan 20 at 16:26
$begingroup$
@ShafinAhmed Okay, I see what you mean now.
$endgroup$
– saulspatz
Jan 20 at 16:32
$begingroup$
It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient.
$endgroup$
– poetasis
Jan 20 at 16:54