Hot answers tagged

9

First thing first, make it into a function, such that your main will be int main(){ const int siz = 6; int arr[siz] = {4,6,3,1,3,8}; std::cout << "Before sort\n"; printarr(arr,siz); sort(arr, siz); std::cout << "After sort\n"; printarr(arr,siz); } Since you've tagged it c++, do not use c-style ...


8

Insertion sort allows a little known optimization. As coded, each iteration of an inner loop performs two comparisons: j > 0 and data[j - 1] > test_value. It is possible to get away with one: if (test_value < data[0]) { // No need to compare data anymore. Just shift. for (j = i; j > 0; j--) { data[j] = data[j - 1]; } } else { ...


7

Observations Very interesting question. The numbers I came up with when running the program are 10248 distinct values sorted Selection sort on 16384 items: 353 ms Insertion sort on 16384 items: 176 ms Which makes the insertion sort twice as fast as the selection sort. This is on Windows 10 using Visual Studio 2019 on a 4 year old Lenovo Thinkpad P50 with ...


5

Some notes: I would avoid running a loop while changing i inside, it is very unclear to the reader. I prefer using two nested loops. The swap can be done in one step less I would initialize a size variable and use it throughout the code instead of hard-coding 6. Printing the array to the console should be in a separate function (as well as the sorting ...


5

As the main point of the question is about performance and not refactoring, I will address the performance of the code. Unfortunately, the question doesn't include actual numbers, just my Insertion sort was way faster than my Selection sort on random input (about one fourth the running time), and Insertion was a clear winner even for its worst case of ...


5

That's not bubble sort. More like an overly eager selection sort. Bubble sort swaps neighbors.


4

The pop(0) takes linear time. Do that differently, in O(1) time. The standard way uses index variables. See this question's answers for some more pythonic ways. Or you could merge from right to left, using pop(), and then in the end reverse() the result. One way to do the latter: def merge(L1, L2): """Merges two (already sorted) lists to ...


3

It's wrong. For example for input {5,9,3,7,2,6} you print 5 2 3 6 7 9. It's not bubble sort. More like an inefficient insertion sort. It's not O(n2) but only O(n3). For example for input int arr[100] = {99,98,97,...,2,1,0} you have 161,799 iterations of your loop (that's 100C3 + 99).


3

You don't implement the obvious optimization to Bubble sort. If you run through the inner loop and no swapping is done then the array is now sorted. This reduces the "Best Case" complexity to O(n) rather than the O(n^2) that you have implemented. Your sort is based on integers. That is not very useful in C++ as arrays can be of nearly anything. So ...


3

I'm running this on an Haswell (4770K but the specific model shouldn't matter). I compiled with MSVC 2017 version 15.9 .. and MASM I suppose, you will see. The performance difference between the selection sort and insertion sort was 5x: 166ms vs 33ms. That difference is simmilar to what you saw, so it may be for the same reason. I am particularly interested ...


3

Welcome to Code Review. Here's some suggestions: Instead of taking a container as argument, take a pair of iterators for flexibility. Provide one function that uses iterator_category to find the correct version. Allow the user to specify a custom comparator. Personally, I'd say that bool swapped{false}; is clearer than bool swapped{}. Constantly ...


2

Find the index of the green and red items, then remove them from the array with splice. Then you can make a properly ordered array by combining the removed items with the rest of the items in the original array: const colors = [{name: 'yellow'}, {name: 'blue'}, {name: 'green'}, {name: 'red'}, {name: 'orange'}] const removeColor = colorToRemove => ( ...


2

I would suggest to use the newer C++ stuff at least where it very obviously simplifies the code. The int tmp = arr[i]; arr[i] = arr[i-1]; arr[i-1] = tmp; can be written in one line instead of three: std::swap(arr[i], arr[i-1]); std::array is just the same as the plain old array but knows the own size: std::...


2

Code review You should use better variable names then a, x and y. But otherwise since your code works your code is fine. Performance It seems a couple of users are confused why Python has strange performance. Enumerate vs index This is pretty simple both enumerate and index have the same time and space complexity. If we have a list of False and set one to ...


2

You have implemented an unusual bucket sort. First, the logic to compute the bucket number makes assumptions about the values themselves and will fail on many types of numbers (for example, positive integers). And second, if N is the size of the input list, you are creating N buckets. Typically, bucket sort uses a number of buckets that is smaller than N. A ...


1

In which we defend the honor of enumerate() Although I learned from and appreciated the write-up by Peilonrayz, I was not convinced by all of the characterizations. Also, I had some specific questions not covered in those benchmarks, so I explored on my own using the script below. These notes cover a few things I learned and reframe the discussion a bit. ...


1

int [] arrayToBeSorted; Scanner scan=new Scanner(System.in); Without any modifier, members and functions are package-private. Which means that they are accessible from the same package, but not by instances extending the class. That's an extremely odd thing, actually, when looking at it from an object-oriented point of view. You want to either make them ...


Only top voted, non community-wiki answers of a minimum length are eligible