Skip to content

Instantly share code, notes, and snippets.

@scabbiaza

scabbiaza/bigO.js

Last active August 3, 2016 06:30
Show Gist options
  • Save scabbiaza/c3b73df44e785e7dafd2dc7bc169acf1 to your computer and use it in GitHub Desktop.
Save scabbiaza/c3b73df44e785e7dafd2dc7bc169acf1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. scabbiaza revised this gist Aug 3, 2016. 2 changed files with 105 additions and 0 deletions.
    83 changes: 83 additions & 0 deletions bigO.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,83 @@
    var R = require("ramda");


    function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
    }

    function generateNumberList(size) {
    return R.map(i => getRandomInt(0, size), R.range(0, size));
    }


    var list = generateNumberList(1000);
    var quickSortCount = 0;
    var insertionSortCount = 0;
    var mergeSortCount = 0;


    function quickSort(list) {
    quickSortCount++;
    var len = R.length(list);
    if (len == 0 || len == 1) return list;
    var pivot = R.last(list);

    var firstHalf = R.filter(i => i<= pivot, R.init(list));
    var secondHalf = R.filter(i => i> pivot, R.init(list));
    return R.concat(quickSort(firstHalf), R.prepend(pivot, quickSort(secondHalf)));
    }


    function insert(val, result) {
    insertionSortCount++;
    var head = R.head(result);
    var len = R.length(result);
    if (len > 0 && val > head) {
    result = R.insert(0, head, insert(val, R.tail(result)));
    } else {
    result = R.insert(0, val, result);
    }
    return result;
    };

    function insertionSort(input) {
    insertionSortCount++;
    var len = R.length(input);
    if (len == 0 || len == 1) return input;
    return insert(R.head(input), insertionSort(R.tail(input)));
    }


    function merge(a, b) {
    mergeSortCount++;
    if (R.length(a) == 0) return b;
    if (R.length(b) == 0) return a;

    var headA = R.head(a);
    var headB = R.head(b);
    var tailA = R.tail(a);
    var tailB = R.tail(b);

    return headA <= headB ?
    R.insert(0, headA, merge(tailA, b)) :
    R.insert(0, headB, merge(a, tailB));
    }

    function mergeSort(list) {
    mergeSortCount++;
    var len = R.length(list);
    if (len == 0 || len == 1) return list;
    var firstHalf = R.slice(0, len/2, list);
    var secondHalf = R.slice(len/2, len, list);
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    }


    quickSort(list);
    //insertionSort(list);
    //mergeSort(list);
    console.log("Array lenght: " + R.length(list));
    console.log("Function calls:");
    console.log("INSERTION SORT:", insertionSortCount);
    console.log("MERGE SORT:", mergeSortCount);
    console.log("QUICK SORT:", quickSortCount);
    22 changes: 22 additions & 0 deletions bigO.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,22 @@
    http://bigocheatsheet.com/

    Avarage
    INSERTION SORT: O(n^2)
    MERGE SORT: O(n log(n))
    QUICK SORT: O(n log(n))



    Array lenght: 1000000
    Function calls:
    INSERTION SORT: RangeError: Maximum call stack size exceeded
    MERGE SORT: RangeError: Maximum call stack size exceeded
    QUICK SORT: 1354895


    Array lenght: 1000
    Function calls:
    INSERTION SORT: 249612
    MERGE SORT: 11726
    QUICK SORT: 1353

  2. scabbiaza revised this gist Aug 3, 2016. 3 changed files with 13 additions and 0 deletions.
    0 insertion.js → insertionSort.js
    View file
    File renamed without changes.
    0 merge.js → mergeSort.js
    View file
    File renamed without changes.
    13 changes: 13 additions & 0 deletions quickSort.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,13 @@
    var R = require("ramda");

    function quickSort(list) {
    var len = R.length(list);
    if (len == 0 || len == 1) return list;
    var pivot = R.last(list);

    var firstHalf = R.filter(i => i<= pivot, R.init(list));
    var secondHalf = R.filter(i => i> pivot, R.init(list));
    return R.concat(quickSort(firstHalf), R.prepend(pivot, quickSort(secondHalf)));
    }

    console.log('QUICK SORT:', quickSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));
  3. scabbiaza revised this gist Aug 2, 2016. 1 changed file with 0 additions and 8 deletions.
    8 changes: 0 additions & 8 deletions merge.js
    View file
    Original file line number Diff line number Diff line change
    @@ -23,12 +23,4 @@ function mergeSort(list) {
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    }

    function mergeSort(list) {
    var len = R.length(list);
    if (len == 0 || len == 1) return list;
    var firstHalf = R.slice(0, len/2, list);
    var secondHalf = R.slice(len/2, len, list);
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    }

    console.log('MERGE SORT:', mergeSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));
  4. scabbiaza revised this gist Aug 2, 2016. 2 changed files with 29 additions and 0 deletions.
    21 changes: 21 additions & 0 deletions insertion.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,21 @@
    var R = require("ramda");


    function insert(val, result) {
    var head = R.head(result);
    var len = R.length(result);
    if (len > 0 && val > head) {
    result = R.insert(0, head, insert(val, R.tail(result)));
    } else {
    result = R.insert(0, val, result);
    }
    return result;
    };

    function insertionSort(input) {
    var len = R.length(input);
    if (len == 0 || len == 1) return input;
    return insert(R.head(input), insertionSort(R.tail(input)));
    }

    console.log('INSERTION SORT:', insertionSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));
    8 changes: 8 additions & 0 deletions merge.js
    View file
    Original file line number Diff line number Diff line change
    @@ -23,4 +23,12 @@ function mergeSort(list) {
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    }

    function mergeSort(list) {
    var len = R.length(list);
    if (len == 0 || len == 1) return list;
    var firstHalf = R.slice(0, len/2, list);
    var secondHalf = R.slice(len/2, len, list);
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    }

    console.log('MERGE SORT:', mergeSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));
  5. scabbiaza created this gist Aug 2, 2016.
    26 changes: 26 additions & 0 deletions merge.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,26 @@
    var R = require("ramda");


    function merge(a, b) {
    if (R.length(a) == 0) return b;
    if (R.length(b) == 0) return a;

    var headA = R.head(a);
    var headB = R.head(b);
    var tailA = R.tail(a);
    var tailB = R.tail(b);

    return headA <= headB ?
    R.insert(0, headA, merge(tailA, b)) :
    R.insert(0, headB, merge(a, tailB));
    }

    function mergeSort(list) {
    var len = R.length(list);
    if (len == 0 || len == 1) return list;
    var firstHalf = R.slice(0, len/2, list);
    var secondHalf = R.slice(len/2, len, list);
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    }

    console.log('MERGE SORT:', mergeSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));