Lab 2: Bubble Sort #534
Lab 2: Bubble Sort #534
Conversation
krnicolson
requested review from
anzboi,
anzdaddy,
camscale,
joshcarp,
juliaogris,
linuxmonk,
pentaphobe and
rokane
as code owners
Codecov Report
@@ Coverage Diff @@
## master #534 +/- ##
=====================================
Coverage 100% 100%
=====================================
Files 107 108 +1
Lines 1861 1874 +13
=====================================
+ Hits 1861 1874 +13
Continue to review full report at Codecov.
|
02_bubble/nicholsk/main.go
Outdated
| sorted := false | ||
|
|
||
| // make a slice copy to perform sort on | ||
| sCopy := s |
There was a problem hiding this comment.
Not sure why you need a variable to make a copy over here.
| swaps := false | ||
|
|
||
| // iterate every index in the list, starting at index 1 | ||
| for i := 1; i < len(s); i++ { |
There was a problem hiding this comment.
why len(s) and why not len(sCopy) ?
|
Don't forget to be descriptive with your commit messages and PR. Currently your PR does not inform the reviewer what has been done, nor the issue being resolved. Also remember to use the appropriate tags. @mohitnag Don't forget to update the tags as well. |
krnicolson
changed the title
There was a problem hiding this comment.
Please fix commit messages with git rebase -i HASH.
Your bubble sort implementation is lacking a key parts to be called bubble sort IMO.
| } | ||
|
|
||
| func bubble(s []int) []int { | ||
|
|
There was a problem hiding this comment.
Unnecessary blank line.
No need for blank lines at beginning or end of block.
Use blank lines between type, method and function definitions and within a block for logical separation.
| func bubble(s []int) []int { | ||
|
|
||
| // track whether the sort is complete | ||
| sorted := false |
There was a problem hiding this comment.
you don't need sorted and swaps; swaps alone should suffice.
|
|
||
| // an iteration with no swaps indicates the array is sorted | ||
| if !swaps { | ||
| sorted = true |
| if s[i-1] > s[i] { | ||
|
|
||
| // if less than previous then swap elements | ||
| s[i], s[i-1] = s[i-1], s[i] |
There was a problem hiding this comment.
you haven't created a copy of the input slice and you are there for modifying the input.
create a test case that fails when checking that input is left unmodified and fix with copy()
| // track whether the sort is complete | ||
| sorted := false | ||
|
|
||
| for !sorted { |
There was a problem hiding this comment.
Typically bubble sort has to nested loops.
After the first iteration of the outer loop the largest element has "bubbled" up to the highest index position.
Therefore no more comparisons with the highest index position need to be executed:
for i := len(s); i > 0; i-- {
for j := 1; j < i; j++ {
if s[j-1] > s[j] {
s[j-1], s[j] = s[j], s[j-1]
}
}
}you can add in an early bail when nothing has been swapped ie the slice is already sorted:
for i := len(s); i > 0; i-- {
swapped := false
for j := 1; j < i; j++ {
if s[j-1] > s[j] {
s[j-1], s[j] = s[j], s[j-1]
swapped = true
}
}
if !swapped {
// If no elements were swapped, the slice is sorted so we can stop here
return
}
}| func TestBubbleWithLargeSlice(t *testing.T) { | ||
| a := assert.New(t) | ||
|
|
||
| expected := make([]int, 100) |
There was a problem hiding this comment.
Poor naming: this is the input not the expectedOutput.
| expected := []int{-3, -2, 1} | ||
|
|
||
| a.Equal(expected, sorted) | ||
| } |
There was a problem hiding this comment.
Add test cases for empty slice and already sorted.
Fixes #540
Review of colleague's PR #554
Changes proposed in this PR: