20thSept_Sorting1

// A list xs from a given Universe X, and a total order on X

// A permutation of xs such that each element is greater than or 
// equal to the previous one wrt each other

// comparisons only


// wishful thinking

// imagine we can sort lists with m elements, where m < n

// m can be n - 1
// or m = n/2

// using n-1

// insert the head in the right place, and sort the tail through wishful thinking


// insertion sort for approach A : n-1

function insert(x, xs) {
    return is_null(xs) // null, return x as it is
        ? list(x)
        : x <= head(xs) // less than head
        ? pair(x, xs) // include before the list
        : pair(head(xs), insert(x, tail(xs))); // include first element of head(xs) since it is greater than x and then again check for tail
}

function insertion_sort(xs) { // wishful thinking, using insert function to check head and repeating for tail
    return is_null(xs)
        ? xs
        : insert(head(xs), insertion_sort(tail(xs)));
}

// order of growth in time: is it n^2?


// selection sort for approach A : n - 1

// find the smallest element x
// remove from the list
// sort the remaining list
// put x in front



function smallest(xs) {
    return accumulate((x, y) => x < y ? x : y,
                            head(xs), tail(xs));
}

function selection_sort(xs) {
    if (is_null(xs)) {
        return xs;
    } else {
        const x = smallest(xs);
        return pair(x, selection_sort(remove(x, xs)));
    }
}

// order of growth of time?