11
Avoid code duplication
Your code is more verbose than necessary, because you are repeating a lot of things unnecessarily, or write things in a more complex way than necessary. For example:
(index + (index + length)) / 2
This looks really weird, and is actually equivalent to:
index + length / 2
Which makes much more sense. Even with that change, that ...
7
Questions (+ design review)
Could anyone do some little code review please?
The biggest issue I see with your current design is that you are using the “god object” anti-pattern. Your Sorter class:
Loads the data from a file.
Implements over a half-dozen sort algorithms.
Tests over a half-dozen sort algorithms.
Writes sorted data to a file (over a half-dozen ...
5
I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).
Performance wise, it's hard to beat if you have a small ...
4
Interface
A more appropriate type for length would be size_t. And I'd expect the compare argument to be a function returning plain int, and accepting pointers to const void.
Test program
The test program could be improved with the addition of a is_sorted() function to confirm the result and return the appropriate success/failure value. I would recommend ...
3
I'm not too confident with my knowledge on (void) pointers so I will avoid giving feedback on the pointer related stuff.
Unnecessary if...else statement.
if(length % 2 == 0)
mergesort_helper(array, (index + (index + length)) / 2, length / 2, size_element, compare, storage);
else
mergesort_helper(array, (index + (index + length)) / 2, length / 2 + 1, ...
3
IMHO - I usually use recursive to break down a complex loop code into a simpler and smaller code. So if the function I end up created is still a complex one I'd rather use loop instead. In your case it's simpler and easier to do loop instead of recursion.
public static int[] BubbleSort(int[] arrayOfValues)
{
bool swapOccurred;
do
{
...
3
Less efficient? It consumes more stack space, which shouldn’t be a problem for any dataset where a bubble sort would be appropriate.
With the latest version of the c# compiler, tuple deconstruction will allow you to swap the values with a single line of code (although it will probably be slower).
On a side note, I’m not clear on why you have a separate ...
3
TLDR: in order to improve performance while keeping it simple, switch to insertion sort for small arrays.
Congratulations on choosing mergesort! This is a great choice. It is very elegant, stable and can achieve great performance without the code turning in an horrible mess as is typically the case with quicksort.
There are many answers already so I will ...
3
Keep your includes ordered for maintainability and shorter diffs.
The separate sorted groups should be in order: This files header (first to ensure it remains self-contained), external libraries (standard and additional), this project's headers.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
There are ...
2
Your insertionSort() is OK, but I would write:
template<std::forward_iterator Iter>
void insertion_sort(Iter first, Iter last) {
for (Iter it = first; it != last; ++it)
std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}
insertion_sort(v.begin(), v.end());
display() copys your vector, so make the parameter as const (lvalue)...
2
Cool project!
Good work so far.
Clean code is important and that's one of the things I struggle with. A lot.
From your code, I can see that you would benefit a lot from that too.
const token = "TOKEN_HERE";
Tokens and sensitive information you should try to store in .env files. Especially if your code might be accessible on github or similar sites....
1
int i = 1;
while (i < arr.size())
{
// body of loop
++i;
}
That is the quintessential for loop. Write it as:
const auto ASize = arr.size();
for (size_t i= 1; i < ASize; ++i) {
// body of loop
}
I also saved the array size since it doesn't change... but your variable arr is not const and the compiler can't really deduce ...
1
The typical insertion sort is O(n) for already sorted input, and "almost O(n)" for "almost sorted" input. Which is somewhat common in real world data. Your way you don't have that, you're \$\Theta(n^2)\$. Someone not familiar with how lists work internally might think your code is O(n) for reverse-sorted input, but since del lst[i] takes ...
1
last_thing
You define last_thing and use it to initialise your array, which is fine, however you also use it within your actual bubble_sort function. This seems wrong, it would be better to use the length of the supplied array in order to determine when to stop. This will make your code more portable and able to handle different sized arrays.
When to check ...
1
Your bubble sort algorithm has way too many variables. You don't need to keep track of the right and left item. All you need to do is compare two values, and swap if one is bigger than the other.
def bubble_sort(nums):
length = len(nums)
for i in range(length - 1):
for j in range(0, length - i - 1):
if nums[j] > nums[j + 1]:
...
Only top voted, non community-wiki answers of a minimum length are eligible
