Possibly bubble sort algorithmHow can I speed up my shell sort?Stable Sort in C#Bubble sort a list of integers for a number of iterationsMerge Sort algorithmExact sort - sorting with few move operationsBubble Sort in Objective-CRobust Bubble Sort in VBAMeasuring the time for the bubble sort algorithmCustom sorting algo / optimized bubble sortBubble and Cocktail sort
Can I make popcorn with any corn?
whey we use polarized capacitor?
Draw simple lines in Inkscape
What typically incentivizes a professor to change jobs to a lower ranking university?
Is it possible to make sharp wind that can cut stuff from afar?
How to report a triplet of septets in NMR tabulation?
How to make payment on the internet without leaving a money trail?
Why is an old chain unsafe?
"You are your self first supporter", a more proper way to say it
What is the logic behind how bash tests for true/false?
Chess with symmetric move-square
Is it possible to do 50 km distance without any previous training?
How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)
Could a US political party gain complete control over the government by removing checks & balances?
Simulate Bitwise Cyclic Tag
Shell script can be run only with sh command
How is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?
Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?
What are these boxed doors outside store fronts in New York?
How do you conduct xenoanthropology after first contact?
What defenses are there against being summoned by the Gate spell?
How is it possible to have an ability score that is less than 3?
Why are only specific transaction types accepted into the mempool?
Why is "Reports" in sentence down without "The"
Possibly bubble sort algorithm
How can I speed up my shell sort?Stable Sort in C#Bubble sort a list of integers for a number of iterationsMerge Sort algorithmExact sort - sorting with few move operationsBubble Sort in Objective-CRobust Bubble Sort in VBAMeasuring the time for the bubble sort algorithmCustom sorting algo / optimized bubble sortBubble and Cocktail sort
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I'm trying to figure out what to call this sorting algorithm:
function sort(array)
array = array.slice();
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]
return array;
console.log(sort([8, 4, 5, 2, 3, 7]));
I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(
javascript algorithm sorting
New contributor
$endgroup$
add a comment |
$begingroup$
I'm trying to figure out what to call this sorting algorithm:
function sort(array)
array = array.slice();
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]
return array;
console.log(sort([8, 4, 5, 2, 3, 7]));
I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(
javascript algorithm sorting
New contributor
$endgroup$
add a comment |
$begingroup$
I'm trying to figure out what to call this sorting algorithm:
function sort(array)
array = array.slice();
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]
return array;
console.log(sort([8, 4, 5, 2, 3, 7]));
I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(
javascript algorithm sorting
New contributor
$endgroup$
I'm trying to figure out what to call this sorting algorithm:
function sort(array)
array = array.slice();
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]
return array;
console.log(sort([8, 4, 5, 2, 3, 7]));
I wrote it while trying to figure out bubble sort which is a lot different. Tho will have slightly the same running time as the actual bubble sort. I might be wrong :(
function sort(array)
array = array.slice();
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]
return array;
console.log(sort([8, 4, 5, 2, 3, 7]));
function sort(array)
array = array.slice();
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
//swap
[array[i], array[j]] = [array[j], array[i]]
return array;
console.log(sort([8, 4, 5, 2, 3, 7]));
javascript algorithm sorting
javascript algorithm sorting
New contributor
New contributor
edited 9 hours ago
200_success
131k17157422
131k17157422
New contributor
asked 10 hours ago
Ademola AdegbuyiAdemola Adegbuyi
1185
1185
New contributor
New contributor
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1
elements.
Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i]
with array[j] > array[j+1]
, you will get Bubblesort.
This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if
).
A small improvement would be to add a flag in the i
loop which records if any swapping happened at all - the outer for
loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)
$endgroup$
1
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
1
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
add a comment |
$begingroup$
It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.
The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i
will be sorted correctly:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
In particular, this invariant will obviously be true at the end of the first iteration, when i == 0
. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i
now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1
, the whole array will be correctly sorted.
Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1
; the iteration with i == j
obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i
with a larger one from the tail end of the array, which will still leave array[i]
greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i
:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < i; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
With this optimization, your algorithm can be recognized as a form of insertion sort.
It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i]
into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:
for (let i = 1; i < array.length; i++)
let j = i, temp = array[i];
while (j > 0 && array[j - 1] > temp)
array[j] = array[j - 1];
j--;
if (j < i) array[j] = temp;
// Invariant: here array[0] to array[i] will be correctly sorted!
By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.
The if (j < i)
part of the code above is not really necessary, since if j == i
, assigning temp
back to array[i]
would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1
instead of let i = 0
; the iteration with i == 0
does nothing anyway, so we can safely skip it!
$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.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcodereview.stackexchange.com%2fquestions%2f217017%2fpossibly-bubble-sort-algorithm%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1
elements.
Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i]
with array[j] > array[j+1]
, you will get Bubblesort.
This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if
).
A small improvement would be to add a flag in the i
loop which records if any swapping happened at all - the outer for
loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)
$endgroup$
1
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
1
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
add a comment |
$begingroup$
To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1
elements.
Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i]
with array[j] > array[j+1]
, you will get Bubblesort.
This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if
).
A small improvement would be to add a flag in the i
loop which records if any swapping happened at all - the outer for
loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)
$endgroup$
1
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
1
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
add a comment |
$begingroup$
To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1
elements.
Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i]
with array[j] > array[j+1]
, you will get Bubblesort.
This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if
).
A small improvement would be to add a flag in the i
loop which records if any swapping happened at all - the outer for
loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)
$endgroup$
To me, that's exactly Bubblesort: it takes care the largest element moves to the end of the array, and then operates on length-1
elements.
Edit: this does look quite similar to Bubblesort, but - as a diligent reader noticed - is not quite Bubblesort, as the algorithm does not compare (and swap) adjacent elements (which indeed is the main characteristic of Bubblesort). If you replace array[j] > array[i]
with array[j] > array[j+1]
, you will get Bubblesort.
This implementation will fail if less than two input elements are given (0 or 1) - hint: the array is already sorted in these cases (just add an if
).
A small improvement would be to add a flag in the i
loop which records if any swapping happened at all - the outer for
loop may terminate if the inner loop didn't perform any swaps. (Time) performance of Bubblesort is considered to be awful in comparison to other algorithms, but it must be noted it's the fastest algorithm on an already sorted array - if you add that flag ;)
edited 7 hours ago
answered 9 hours ago
jvbjvb
879210
879210
1
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
1
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
add a comment |
1
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
1
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
1
1
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
$begingroup$
So, I visualized the execution on pythontutor.com. One should "never" use this. It's worse than the unoptimized version of bubble sort. I goes forth and back, which takes more time. Thanks!
$endgroup$
– Ademola Adegbuyi
9 hours ago
1
1
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
No. One of the defining characteristics of Bubble sort is that it swaps adjacent elements — which is not the case with this code.
$endgroup$
– 200_success
9 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success you are absolutely right - about to edit my answer :)
$endgroup$
– jvb
8 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
$begingroup$
@200_success: The OP's code is actually a (rather inefficient) variant of insertion sort, with some mostly useless extra shuffling of the tail end of the array thrown in.
$endgroup$
– Ilmari Karonen
2 hours ago
add a comment |
$begingroup$
It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.
The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i
will be sorted correctly:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
In particular, this invariant will obviously be true at the end of the first iteration, when i == 0
. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i
now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1
, the whole array will be correctly sorted.
Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1
; the iteration with i == j
obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i
with a larger one from the tail end of the array, which will still leave array[i]
greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i
:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < i; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
With this optimization, your algorithm can be recognized as a form of insertion sort.
It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i]
into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:
for (let i = 1; i < array.length; i++)
let j = i, temp = array[i];
while (j > 0 && array[j - 1] > temp)
array[j] = array[j - 1];
j--;
if (j < i) array[j] = temp;
// Invariant: here array[0] to array[i] will be correctly sorted!
By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.
The if (j < i)
part of the code above is not really necessary, since if j == i
, assigning temp
back to array[i]
would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1
instead of let i = 0
; the iteration with i == 0
does nothing anyway, so we can safely skip it!
$endgroup$
add a comment |
$begingroup$
It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.
The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i
will be sorted correctly:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
In particular, this invariant will obviously be true at the end of the first iteration, when i == 0
. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i
now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1
, the whole array will be correctly sorted.
Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1
; the iteration with i == j
obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i
with a larger one from the tail end of the array, which will still leave array[i]
greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i
:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < i; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
With this optimization, your algorithm can be recognized as a form of insertion sort.
It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i]
into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:
for (let i = 1; i < array.length; i++)
let j = i, temp = array[i];
while (j > 0 && array[j - 1] > temp)
array[j] = array[j - 1];
j--;
if (j < i) array[j] = temp;
// Invariant: here array[0] to array[i] will be correctly sorted!
By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.
The if (j < i)
part of the code above is not really necessary, since if j == i
, assigning temp
back to array[i]
would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1
instead of let i = 0
; the iteration with i == 0
does nothing anyway, so we can safely skip it!
$endgroup$
add a comment |
$begingroup$
It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.
The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i
will be sorted correctly:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
In particular, this invariant will obviously be true at the end of the first iteration, when i == 0
. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i
now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1
, the whole array will be correctly sorted.
Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1
; the iteration with i == j
obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i
with a larger one from the tail end of the array, which will still leave array[i]
greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i
:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < i; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
With this optimization, your algorithm can be recognized as a form of insertion sort.
It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i]
into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:
for (let i = 1; i < array.length; i++)
let j = i, temp = array[i];
while (j > 0 && array[j - 1] > temp)
array[j] = array[j - 1];
j--;
if (j < i) array[j] = temp;
// Invariant: here array[0] to array[i] will be correctly sorted!
By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.
The if (j < i)
part of the code above is not really necessary, since if j == i
, assigning temp
back to array[i]
would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1
instead of let i = 0
; the iteration with i == 0
does nothing anyway, so we can safely skip it!
$endgroup$
It's not even obvious at a glance that your algorithm really sorts all inputs correctly. In fact, it does, but proving that takes a bit of thought.
The key insight is that, at the end of each iteration of the outer loop, the elements at positions from 0 to i
will be sorted correctly:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < array.length - 1; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
In particular, this invariant will obviously be true at the end of the first iteration, when i == 0
. It is then not hard to inductively show that, if this was true at the end of the previous iteration, then it will remain true (with i
now one greater than before) after the next one as well. Thus, at the end of the last iteration, with i == array.length - 1
, the whole array will be correctly sorted.
Actually, to achieve this, we only need to iterate the inner loop up to j == i - 1
; the iteration with i == j
obviously does nothing useful, and any later iterations of the inner loop have no effect on the invariant. (Those iterations can only swap the element currently at index i
with a larger one from the tail end of the array, which will still leave array[i]
greater than or equal to all its predecessors.) So we can speed up your algorithm by only iterating the inner loop until j == i
:
for (let i = 0; i < array.length; i++)
for (let j = 0; j < i; j++)
if (array[j] > array[i])
[array[i], array[j]] = [array[j], array[i]]
// Invariant: here array[0] to array[i] will be correctly sorted!
With this optimization, your algorithm can be recognized as a form of insertion sort.
It's generally not the most efficient form of that algorithm, though, since the inner loop does the insertion of array[i]
into its correct position somewhat inefficiently. A somewhat more efficient implementation would be something like this:
for (let i = 1; i < array.length; i++)
let j = i, temp = array[i];
while (j > 0 && array[j - 1] > temp)
array[j] = array[j - 1];
j--;
if (j < i) array[j] = temp;
// Invariant: here array[0] to array[i] will be correctly sorted!
By running the inner loop "backwards" we can stop it as soon as we find an element that's ranked lower than the one we're inserting (thus avoiding lots of needless comparisons, especially if the input array is already mostly sorted), and by saving the element to be inserted in a temporary variable, we can replace the swaps with simple assignments.
The if (j < i)
part of the code above is not really necessary, since if j == i
, assigning temp
back to array[i]
would have no effect. That said, it's generally a useful optimization if integer comparisons are cheaper than array assignments, which is usually the case. The same goes for starting the outer loop from let i = 1
instead of let i = 0
; the iteration with i == 0
does nothing anyway, so we can safely skip it!
answered 2 hours ago
Ilmari KaronenIlmari Karonen
1,855915
1,855915
add a comment |
add a comment |
Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.
Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.
Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.
Ademola Adegbuyi is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review 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%2fcodereview.stackexchange.com%2fquestions%2f217017%2fpossibly-bubble-sort-algorithm%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