Skip to main content
Code Review

Return to Answer

added 102 characters in body
Source Link
J_H
J_H
  • 42.1k
  • 3
  • 38
  • 157

cite your reference

There is a rich literature on QuickSort. Pick an author and cite the work.

Preferably work that includes worst case analysis, so we don't need a second citation, and so there's consistent notation throughout.

write down loop variants

Also pre- and post- conditions.

You don't have to throw an error if caller of partition() passed in some low > high parameters, but it would improve clarity. Especially for the case of low == high -- is it OK for caller to do that? The code can tell the Gentle Reader that, and seeing such an error during interactive testing might quickly reveal an OBOB, saving you some debugging effort. I know, I know, I see a caller making an if (low >= high) { test. What I'm shooting for is Local Analysis, being able to reason about a function in isolation, understanding the promises involved. The author's goal should be to make it easy for the Gentle Reader to reason about what's happening.

Within the loop, and/or at the end of partition(), it would be nice to see a comment and/or assertion describing what we guarantee upon exit.

Since generateWorstCaseForQuickSortPivotPoint() covers less familiar ground, the above points are especially relevant for that code.

concise identifier

whereToPut isn't a bad identifier, but it sounds like a temporary name you meant to come back to and rename later. Consider using a straightforward noun like worstLocation.

define a logging object

The partitionIndexHistory is a common parameter that comes along for the ride throughout. Which is a code smell. The code is telling you that it wants you to create a Sorter object with the history as an attribute. Then we can make the usual quicksort calls without noisily drawing attention to the history log which will be side effected.

chatty test

testWorstCaseForMiddlePivotQuickSortGenerator() sends many lines to stdout. Prefer to make automated unit tests succeed silently, displaying Green Bar rather than Red.

cite your reference

There is a rich literature on QuickSort. Pick an author and cite the work.

Preferably work that includes worst case analysis, so we don't need a second citation, and so there's consistent notation throughout.

write down loop variants

Also pre- and post- conditions.

You don't have to throw an error if caller of partition() passed in some low > high parameters, but it would improve clarity. Especially for the case of low == high -- is it OK for caller to do that? The code can tell the Gentle Reader that, and seeing such an error during interactive testing might quickly reveal an OBOB, saving you some debugging effort. I know, I know, I see a caller making an if (low >= high) { test. What I'm shooting for is Local Analysis, being able to reason about a function in isolation, understanding the promises involved.

Within the loop, and/or at the end of partition(), it would be nice to see a comment and/or assertion describing what we guarantee upon exit.

Since generateWorstCaseForQuickSortPivotPoint() covers less familiar ground, the above points are especially relevant for that code.

concise identifier

whereToPut isn't a bad identifier, but it sounds like a temporary name you meant to come back to and rename later. Consider using a straightforward noun like worstLocation.

define a logging object

The partitionIndexHistory is a common parameter that comes along for the ride throughout. Which is a code smell. The code is telling you that it wants you to create a Sorter object with the history as an attribute. Then we can make the usual quicksort calls without noisily drawing attention to the history log which will be side effected.

chatty test

testWorstCaseForMiddlePivotQuickSortGenerator() sends many lines to stdout. Prefer to make automated unit tests succeed silently, displaying Green Bar rather than Red.

cite your reference

There is a rich literature on QuickSort. Pick an author and cite the work.

Preferably work that includes worst case analysis, so we don't need a second citation, and so there's consistent notation throughout.

write down loop variants

Also pre- and post- conditions.

You don't have to throw an error if caller of partition() passed in some low > high parameters, but it would improve clarity. Especially for the case of low == high -- is it OK for caller to do that? The code can tell the Gentle Reader that, and seeing such an error during interactive testing might quickly reveal an OBOB, saving you some debugging effort. I know, I know, I see a caller making an if (low >= high) { test. What I'm shooting for is Local Analysis, being able to reason about a function in isolation, understanding the promises involved. The author's goal should be to make it easy for the Gentle Reader to reason about what's happening.

Within the loop, and/or at the end of partition(), it would be nice to see a comment and/or assertion describing what we guarantee upon exit.

Since generateWorstCaseForQuickSortPivotPoint() covers less familiar ground, the above points are especially relevant for that code.

concise identifier

whereToPut isn't a bad identifier, but it sounds like a temporary name you meant to come back to and rename later. Consider using a straightforward noun like worstLocation.

define a logging object

The partitionIndexHistory is a common parameter that comes along for the ride throughout. Which is a code smell. The code is telling you that it wants you to create a Sorter object with the history as an attribute. Then we can make the usual quicksort calls without noisily drawing attention to the history log which will be side effected.

chatty test

testWorstCaseForMiddlePivotQuickSortGenerator() sends many lines to stdout. Prefer to make automated unit tests succeed silently, displaying Green Bar rather than Red.

Source Link
J_H
J_H
  • 42.1k
  • 3
  • 38
  • 157

cite your reference

There is a rich literature on QuickSort. Pick an author and cite the work.

Preferably work that includes worst case analysis, so we don't need a second citation, and so there's consistent notation throughout.

write down loop variants

Also pre- and post- conditions.

You don't have to throw an error if caller of partition() passed in some low > high parameters, but it would improve clarity. Especially for the case of low == high -- is it OK for caller to do that? The code can tell the Gentle Reader that, and seeing such an error during interactive testing might quickly reveal an OBOB, saving you some debugging effort. I know, I know, I see a caller making an if (low >= high) { test. What I'm shooting for is Local Analysis, being able to reason about a function in isolation, understanding the promises involved.

Within the loop, and/or at the end of partition(), it would be nice to see a comment and/or assertion describing what we guarantee upon exit.

Since generateWorstCaseForQuickSortPivotPoint() covers less familiar ground, the above points are especially relevant for that code.

concise identifier

whereToPut isn't a bad identifier, but it sounds like a temporary name you meant to come back to and rename later. Consider using a straightforward noun like worstLocation.

define a logging object

The partitionIndexHistory is a common parameter that comes along for the ride throughout. Which is a code smell. The code is telling you that it wants you to create a Sorter object with the history as an attribute. Then we can make the usual quicksort calls without noisily drawing attention to the history log which will be side effected.

chatty test

testWorstCaseForMiddlePivotQuickSortGenerator() sends many lines to stdout. Prefer to make automated unit tests succeed silently, displaying Green Bar rather than Red.