Commit 99bef39

authored

Merge pull request trekhleb#10 from albertstill/improve-bubble-sort

stop bubble sort revisiting already sorted elements

2 parents 35fff1f + f34fd84 commit 99bef39Copy full SHA for 99bef39

File tree

-4

lines changed

src/algorithms/sorting/bubble-sort
- BubbleSort.js
- __test__
  - BubbleSort.test.js

-4

lines changed

Lines changed: 2 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -7,13 +7,13 @@ export default class BubbleSort extends Sort {`
`7`	`7`	`// Clone original array to prevent its modification.`
`8`	`8`	`const array = [...originalArray];`
`9`	`9`
`10`		`- for (let i = 0; i < array.length; i += 1) {`
	`10`	`+ for (let i = 1; i < array.length; i += 1) {`
`11`	`11`	`swapped = false;`
`12`	`12`
`13`	`13`	`// Call visiting callback.`
`14`	`14`	`this.callbacks.visitingCallback(array[i]);`
`15`	`15`
`16`		`- for (let j = 0; j < array.length - 1; j += 1) {`
	`16`	`+ for (let j = 0; j < array.length - i; j += 1) {`
`17`	`17`	`// Call visiting callback.`
`18`	`18`	`this.callbacks.visitingCallback(array[j]);`
`19`	`19`

Lines changed: 2 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,8 +9,8 @@ import {`
`9`	`9`
`10`	`10`	`// Complexity constants.`
`11`	`11`	`const SORTED_ARRAY_VISITING_COUNT = 20;`
`12`		`-const NOT_SORTED_ARRAY_VISITING_COUNT = 280;`
`13`		`-const REVERSE_SORTED_ARRAY_VISITING_COUNT = 400;`
	`12`	`+const NOT_SORTED_ARRAY_VISITING_COUNT = 189;`
	`13`	`+const REVERSE_SORTED_ARRAY_VISITING_COUNT = 209;`
`14`	`14`	`const EQUAL_ARRAY_VISITING_COUNT = 20;`
`15`	`15`
`16`	`16`	`describe('BubbleSort', () => {`

Comments

(0)