Commit9acbd4b

committed

better performance

1 parentc67316e commit9acbd4bCopy full SHA for 9acbd4b

File tree

+32

-14

lines changed

+32

-14

lines changed

Lines changed: 4 additions & 6 deletions

Original file line number	Diff line number	Diff line change
`@@ -2,13 +2,11 @@`
`2`	`2`
`3`	`3`	`Insertion sort is one of the most natural way of sorting. If you are given some cards that's probably how you are going to sort the.`
`4`	`4`
`5`		`-.This is how it works:`
`6`		`-. Start with the first element, assume that everything to its left is sorted and everything to the right is not.`
`7`		`-. Move to the next element.`
	`5`	`+Insertion sorts visit elements one by one. Everything to the left of the current element is curretly sorted and everything to the right is not.`
`8`	`6`
`9`		`-. Take the first element and consideritsorted.`
`10`		`-.Takethe2nd element, compare it with thefirst element. It 2nd is smaller swapitwith the first element.`
`11`		`-.Go to the 3rdelementcompare it withthealready sorted elements and if any of themissmaller, swap them.`
	`7`	`+.This is howitworks:`
	`8`	`+.Visit 2nd. Ifthecurrent element is smaller than theprevious one move to the placeitshould be.`
	`9`	`+.Visit nextelementand dothesame thing. The leftisalways sorted.`
`12`	`10`	`. Repeat for the rest of the array.`
`13`	`11`
`14`	`12`	`More efficient in practice than most other simple quadratic (i.e., O(n^2^)) algorithms such as <<Selection Sort>> or <<Bubble Sort>>.`

Lines changed: 5 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,17 +1,14 @@`
`1`		`-const{ swap}=require('./sorting-common');`
`2`		`-`
`3`	`1`	`functioninsertionSort(collection){`
`4`	`2`	`constarray=Array.from(collection);`
`5`	`3`
`6`		`-for(letouter=1;outer<array.length;outer+=1){`
	`4`	`+for(letouter=0;outer<array.length;outer+=1){`
	`5`	`+constinsert=array[outer];`
`7`	`6`	`letinner=outer-1;`
`8`		`-while(inner>=0&&array[outer]<array[inner]){`
	`7`	`+while(inner>=0&&array[inner]>insert){`
	`8`	`+array[inner+1]=array[inner];`
`9`	`9`	`inner-=1;`
`10`	`10`	`}`
`11`		`-if(outer!==inner+1){`
`12`		`-const[insert]=array.splice(outer,1);`
`13`		`-array.splice(inner+1,0,insert);`
`14`		`-}`
	`11`	`+array[inner+1]=insert;`
`15`	`12`	`}`
`16`	`13`	`returnarray;`
`17`	`14`	`}`

Lines changed: 15 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,7 @@`
`1`	`1`	`// tag::swap[]`
`2`	`2`	`/**`
`3`	`3`	`* Swap array elements in place`
	`4`	`+ * Runtime: O(1)`
`4`	`5`	`*@param {array} array to be modified`
`5`	`6`	`*@param {integer} from index of the first element`
`6`	`7`	`*@param {integer} to index of the 2nd element`
`@@ -10,6 +11,20 @@ function swap(array, from, to) {`
`10`	`11`	`}`
`11`	`12`	`// end::swap[]`
`12`	`13`
	`14`	`+/**`
	`15`	`+ * Move an element in an array from a postion to another.`
	`16`	`+ * Runtime: O(n)`
	`17`	`+ *@param {array} array`
	`18`	`+ *@param {integer} from index of the element to remove (source)`
	`19`	`+ *@param {integer} to index where the removed element would be move (destination)`
	`20`	`+ */`
	`21`	`+functionmoveElement(array,from,to){`
	`22`	`+if(from===to+1)return;`
	`23`	`+const[elementToInsert]=array.splice(from,1);// delete from position`
	`24`	`+array.splice(to+1,0,elementToInsert);// insert element in to the position.`
	`25`	`+}`
	`26`	`+`
`13`	`27`	`module.exports={`
`14`	`28`	`swap,`
	`29`	`+ moveElement,`
`15`	`30`	`};`

Lines changed: 8 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -5,6 +5,14 @@ const sortingAlgorithms = [`
`5`	`5`
`6`	`6`	`sortingAlgorithms.forEach((sort)=>{`
`7`	`7`	describe(`Sorting with${sort.name}`,()=>{
	`8`	`+it('should work with zero numbers',()=>{`
	`9`	`+expect(sort([])).toEqual([]);`
	`10`	`+});`
	`11`	`+`
	`12`	`+it('should work with one number',()=>{`
	`13`	`+expect(sort([3])).toEqual([3]);`
	`14`	`+});`
	`15`	`+`
`8`	`16`	`it('should sort numbers',()=>{`
`9`	`17`	`expect(sort([3,5,0])).toEqual([0,3,5]);`
`10`	`18`	`});`

Comments

(0)