From cbc47d4e56a04cc4295a0dc5f09b52a356a455f1 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 19 Sep 2021 16:20:13 -0600 Subject: complete 2-2.2 --- exercises/2.2-2/selection_sort_test.go | 6 ++++-- notes.md | 20 ++++++++++++++++++++ 2 files changed, 24 insertions(+), 2 deletions(-) diff --git a/exercises/2.2-2/selection_sort_test.go b/exercises/2.2-2/selection_sort_test.go index e4abc5d..2b175e9 100644 --- a/exercises/2.2-2/selection_sort_test.go +++ b/exercises/2.2-2/selection_sort_test.go @@ -7,11 +7,13 @@ func Sort(i *[]int) { n := len(A) for i := 0; i < n; i++ { + min := i for j := i + 1; j < n; j++ { - if A[j] < A[i] { - A[i], A[j] = A[j], A[i] + if A[j] < A[min] { + min = j } } + A[i], A[min] = A[min], A[i] } } diff --git a/notes.md b/notes.md index 521d113..a8ba4c4 100644 --- a/notes.md +++ b/notes.md @@ -460,6 +460,26 @@ the rate of growth in determining computational efficiency for large inputs. > manner for the first `n - 1` elements of `A`. Write pseudocode for *selection sort*. + + n = A.length + for i = 1 to n - 1 { + min = i + for j = i + 1 to n { + if A[j] < A[min] + min = j + A[i], A[min] = A[min], A[i] + + What loop invariant does this algorithm maintain? + + * intialization: inner loop initializes to the right index of the outer loop + * maintenance: with the inner right array of the outer array. + * termination: when end of loop is reached + Why does it need to run for only the first n-1 elements, rather than for all `n` elements? + + * The last element of the array should has nothing to be compared against. + Give the best-case and worst-case running times of selection sort in 𝚯-notation. + + = 𝚯(n^2). two loops, one nested within the other. -- cgit v1.2.3