humanwhocodes / computer-science-in-javascript Goto Github PK

I came here from this merge sort post: https://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/

But I don't see any merge sort examples here. :(

I was wondering why the constructor: LinkedList is either necessary or best practice on line 51 of data-structures/linked-list/linked-list.js?

Hi, Nicholas.

There is an error (misprint) in bubbleSort algorithm that makes unnecessary comparison beyond the range of items in each iteration.
var len = items.length
should be
var len = items.length - 1.

For example, having five items in the list, the last value for j index during first iteration must be 3 and not 4. Because we need to compare fourth item in the list (index 3) with the fifth item in the list (index 4).

The easiest way to see the issue is to put console.log(j, items[j], items[j+1]) in the inner loop and observe that for the first iteration the items[j+1] prints "undefined".

The same issue is in the article at http://www.nczonline.net/blog/2009/05/26/computer-science-in-javascript-bubble-sort/

Thanks
Alexei

Enhancement....def not a bug:

@nzakas as part of tidying up on some CS type things I planned on converting these to the new syntax, just wanted to give you the heads up and see if you'd be interested in a PR (I know they point to your blog series so not sure..) or would prefer to keep in the legacy format. In any case great stuff.

-Cheers

Zac

First off, thanks for sharing. This is a very clean, easy to follow implementation. Very nice.

The only issue I found is when deleting nodes with two children. Try this:
var bst = new BinarySearchTree();
bst.add(7);
bst.add(11);
bst.add(8);
bst.add(13);

At this point the structure looks like this:
7

11
/
8 13

bst.remove(11);

Expected result:
7

8

13

Actual result:
7

8
/
8

Node 8's left pointer points to itself, and the right node has been overwritten.

This line seems odd:

275: replacementParent.right = replacement.left;

This is where node 11 loses its 13 branch.

And

279: replacement.left = current.left;

assigns node 8 to itself.

Hope this helps. Thanks again.

This should be published as an npm package. I could lend you a hand with that if you like.

The day before the sale？？？？？

var bst = new BinarySearchTree();

bst.add(8);
bst.add(3);
bst.add(1);
bst.add(10);

bst.add(6);
bst.add(4);
bst.add(7);
bst.add(14);
bst.add(13);

bst.remove(3);
bst.traverse(node => {
// Error
    console.log(node.value);
});

?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. It gets its name because smaller elements "bubble" to the top of the list with each iteration.

Time Complexity:

Best Case: O(n)
Average Case: O(n^2)
Worst Case: O(n^2)

merge-sort-inplace.js is not an example of an in place Merge Sort because arrays are being created and concatenated. Here's an example of an in place merge sort...

const mergeSort = (array, left = 0, right = array.length - 1) => {
    
    if (left >= right) return array

    let mid = Math.floor((left + right) / 2),
        i = mid + 1
    
    mergeSort(array, left, mid)
    mergeSort(array, i, right)

    while (left <= mid && i <= right) {
        if (array[left] < array[i]) left++
        else {
            array.splice(left, 0, array.splice(i, 1)[0])
            left++
            mid++
            i++
        }
    }

    return array
}

It has no importance at all, but the header for quicksort is the header from insertion sort :P

https://github.com/nzakas/computer-science-in-javascript/blob/master/algorithms/sorting/quicksort/quicksort.js#L2

Your base64Decode fails on the following tests:
//
var tests = [
['YW55IGNhcm5hbCBwbGVhcw', 'any carnal pleas'],
['YQ', 'a'],
['YR', 'a'],
['', ''],
['YQA=', 'a\u0000'],
['YW55IGNhcm5hbCBwbGVhcw==YW55IGNhcm5hbCBwbGVhc3VyZS4=', 'any carnal pleasany carnal pleasure.'],
['YW55IGNhcm5hbCBwbGVhcw==YW55IGNhcm5hbCBwbGVhc3VyZS4', 'any carnal pleasany carnal pleasure.']
];

see https://gist.github.com/1284012

~/computer-science-in-javascript/src/data-structures/doubly-linked-list/doubly-linked-list.js

    insertBefore(data, index) {
            // ...omit other lines util here
            // line 183
            while ((current.next !== null) && (i < index)) {
                current = current.next;
                i++;
            }
        }

    insertAfter(data, index) {
        // ...omit other lines util here
        // line 259
        while ((current !== null) && (i < index)) {
            current = current.next;
            i++;
        }

I am confused about the difference of while condition between line 183 and 259,

and do a test in node for the insertAfter method:

const { DoublyLinkedListi } = require( "./doubly-linked-list.js");
const doublyLinkedList = new DoublyLinkedList();

doublyLinkedList.add(1);
doublyLinkedList.insertAfter(1, 1);

and it will throw an the error below, it's not a expected error throw by the doubly Linked List class.

            current.next.previous = newNode;
                    ^
TypeError: Cannot read property 'next' of null

So I think current.next !== null in insertBefore method is right for insertAfter, instead of current !== null

I learn a lot from your "quick sort" program, And it makes my program run so fast ! Thank you.

How about being able to merge binary trees?

C:\Users\AngularDev\Desktop\bot\api\node_modules@humanwhocodes\module-importer\dist
module-importer.d.cts:1
export class ModuleImporter {
^^^^^^

SyntaxError: Unexpected token 'export'
at internalCompileFunction (node:internal/vm:73:18)
at wrapSafe (node:internal/modules/cjs/loader:1176:20)
at Module._compile (node:internal/modules/cjs/loader:1218:27)
at Object.Module._extensions..js (node:internal/modules/cjs/loader:1308:10)
at Module.load (node:internal/modules/cjs/loader:1117:32)
at Function.Module._load (node:internal/modules/cjs/loader:958:12)
at Module.require (node:internal/modules/cjs/loader:1141:19)
at require (node:internal/modules/cjs/helpers:110:18)
at tryToRequire (C:\Users\AngularDev\Desktop\bot\api\src\util\ImportUtils.ts:21:1
7)
at importOrRequireFile (C:\Users\AngularDev\Desktop\bot\api\src\util\ImportUtils.
ts:27:65)