• Basisinformationstechnologie 1 (BIT 1)
• Code

Code

// Deno [https://deno.land/]

// Arraybeispiel: [15][3][8][1] -> [3][15][8][1] -> [3][8][15][1] -> [3][8][1][15]
const bubbleSort = (array) => {
    let len = array.length-1;
    let swapped;

    do {
        swapped = false;

        for (let i = 0; i < len; i++) {
            if (array[i] > array[i+1]) {
                let tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;
                swapped = true;
            }
        }
    } while (swapped);
};

const linearSearch = (array, target) => {
    let len = array.length;
    for (let i = 0; i < len; i++) {
        if (array[i] === target) return i;
    }
    return false;
};

const binarySearch = (array, target) => {
    let startIndex = 0;
    let endIndex = array.length-1;
    let middleIndex;

    while (startIndex <= endIndex) {
        middleIndex = Math.floor((startIndex+endIndex) / 2);

        if (target === array[middleIndex]) {
            return middleIndex;
        }

        if (target > array[middleIndex]) {
            startIndex = middleIndex + 1;
        } else if (target < array[middleIndex]) {
            endIndex = middleIndex - 1;
        }
    }
    return false;
};

const randomizeArray = (count, max) => {
    return Array.from({length: count}, () => Math.floor(Math.random() * max));
};

let randomNumbers = randomizeArray(1000000, 1000);

console.log(`started sorting`);
let start = performance.now();

// quadratische Zeitkompletität, O(n^2)
// bubbleSort(randomNumbers);

// TimSort
randomNumbers.sort(function(a, b){return a-b});

let end = performance.now();

console.log(randomNumbers);
console.log(`sorting took ${end-start} milliseconds`);

const searchNumber = 15;
// Lineare Suche
console.log(`started linear search`);
start = performance.now();
// Zeitkomplexitätsklasse O(n)
let found = linearSearch(randomNumbers, searchNumber);
end = performance.now();
console.log(`linear search took ${end-start} milliseconds`);

if (found) {
    console.log(`number ${searchNumber} has been found at index ${found}: ${randomNumbers[found]}`);
} else console.log('number not found in array');

// Binäre Suche
console.log(`started linear search`);
start = performance.now();

found = binarySearch(randomNumbers, searchNumber);
end = performance.now();
console.log(`binary search took ${end-start} milliseconds`);

if (found) {
    console.log(`number ${searchNumber} has been found at index ${found}: ${randomNumbers[found]}`);
} else console.log('number not found in array');