Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcf61af5

Browse files
optimized for loop & corrected comments (trekhleb#617)
The existing insertion sort implementation began by iterating from0 until the end of the array, but it is only necessary toiterate from 1 until the end of the array, since at the0th index, there is nothing to compare to the left ofthe element.In order to complete this change, I also had to update the teststo reflect the fact that the algorithm visits each index 1 lesstime.Finally, I corrected the grammar/wording of the comments.Co-authored-by: Oleksii Trekhleb <trehleb@gmail.com>
1 parent8124034 commitcf61af5

File tree

2 files changed

+7
-7
lines changed

2 files changed

+7
-7
lines changed

‎src/algorithms/sorting/insertion-sort/InsertionSort.js

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,14 +5,14 @@ export default class InsertionSort extends Sort {
55
constarray=[...originalArray];
66

77
// Go through all array elements...
8-
for(leti=0;i<array.length;i+=1){
8+
for(leti=1;i<array.length;i+=1){
99
letcurrentIndex=i;
1010

1111
// Call visiting callback.
1212
this.callbacks.visitingCallback(array[i]);
1313

14-
//Go and checkif previouselements and greaterthen currentone.
15-
// Ifthis is thecase then swap that elements.
14+
//Checkif previouselement is greaterthan currentelement.
15+
// Ifso, swap thetwo elements.
1616
while(
1717
array[currentIndex-1]!==undefined
1818
&&this.comparator.lessThan(array[currentIndex],array[currentIndex-1])

‎src/algorithms/sorting/insertion-sort/__test__/InsertionSort.test.js

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,10 +8,10 @@ import {
88
}from'../../SortTester';
99

1010
// Complexity constants.
11-
constSORTED_ARRAY_VISITING_COUNT=20;
12-
constNOT_SORTED_ARRAY_VISITING_COUNT=101;
13-
constREVERSE_SORTED_ARRAY_VISITING_COUNT=210;
14-
constEQUAL_ARRAY_VISITING_COUNT=20;
11+
constSORTED_ARRAY_VISITING_COUNT=19;
12+
constNOT_SORTED_ARRAY_VISITING_COUNT=100;
13+
constREVERSE_SORTED_ARRAY_VISITING_COUNT=209;
14+
constEQUAL_ARRAY_VISITING_COUNT=19;
1515

1616
describe('InsertionSort',()=>{
1717
it('should sort array',()=>{

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp