Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting algorithms that don’t hate you

medium.com

Post reply on HN
Print view View original

81–84 of 84 posts

Re: Sorting algorithms that don’t hate you

#81

Post by lucumo »

hypertele-Xii wrote: post #78
lucumo wrote: post #28

Earlier quoted context omitted.

No, there could be unsortable properties that are nonetheless different. Or the use case could really require that the original order is relevant. But yeah, I don't usually need stability either.

Forgive me for sounding like an idiot but how can two properties be different, yet unsortable?

If you can digitize it, you can probably sort it, that's true. But the sort keys can get very artificial and weird.

Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes.

You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 10x100 pixel image. But it's not very weird to pick one either.

Next you could sort on properties of the first pixel. But those are multidimensional. Sorting by the most red first, for example, would be weird.

You could still create an ordering if you need the consistency, but it wouldn't mean anything.

If you don't sort by them, you can get images that are different in ways that aren't sorted. Stability (well, instability) becomes detectable.

If you have to use an unstable sorting algorithm you'll be stuck choosing between images jumping around or being in a certain spot because the 34th pixel on the 56th line is slightly more greenish than in the image before it. It can depend on your use case which of those is least desirable.

Having a stable sort would give you another option.

Re: Sorting algorithms that don’t hate you

#82

Post by thomasmg »

graycat wrote: post #76
graycat wrote: post #75

Earlier quoted context omitted.

> In fact, I'm not aware of an algorithm that is as simple as Shell sort, and at the same time much faster than O(n^2). My favorite is heap sort, guaranteed O(n log(n)) average case and worst case, meets the Gleason bound and, thus, is the fastest possible sort based on comparing pairs of keys (in one of volumes of D. Knuth, The Art of Computer Programming ). You mentioned simple: The logic of the heap data structure…

' Ascending integer (Int32) heap sort. ' ' For i = 1, 2, ..., n, sort components of key_array(i) ' into ascending order using heap sort. ' ' We check parameters for reasonable values and, in case of ' a error, raise the error condition. ' ' Upon return, for i = 1, 2, ..., n - 1, ' ' key_array( i ) key_array( i_child2 ) Then i_max_child = i_child1 Else i_max_child = i_child2 End If If key_array( i_max_child ) > key_fa…

You are right, heap sort doesn't need recursion, and is more efficient than shell sort for large arrays. But if you compare the code size, it is hard to beat shell sort. This is a Java version:

    static void shellSort(T[] a, Comparator c) {
        int n = a.length;
        int h = 16, g = 1;
        while (n > g) {
            h = h + h + h / 4 + 16;
            g = (h + 15) / 16;
        }
        do {
            h = (h - 16) * 4 / 9;
            g = (h + 15) / 16;
            for (int i = g; i = g && c.compare(a[j - g], t) > 0; j -= g) {
                    a[j] = a[j - g];
                }
                a[j] = t;
            }
        } while (g > 1);
    }
I was wondering, is there anything as simple as that, and similarly efficient? I doubt it.

Re: Sorting algorithms that don’t hate you

#83

Post by hypertele-Xii »

lucumo wrote: post #81
hypertele-Xii wrote: post #78

Earlier quoted context omitted.

Forgive me for sounding like an idiot but how can two properties be different, yet unsortable?

If you can digitize it, you can probably sort it, that's true. But the sort keys can get very artificial and weird. Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes. You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 1…

Is there such a thing as visual similarity -sort?

Asking because you're actually describing a problem I have with a data set :D

Re: Sorting algorithms that don’t hate you

#84

Post by graycat »

thomasmg wrote: post #82
graycat wrote: post #76

Earlier quoted context omitted.

' Ascending integer (Int32) heap sort. ' ' For i = 1, 2, ..., n, sort components of key_array(i) ' into ascending order using heap sort. ' ' We check parameters for reasonable values and, in case of ' a error, raise the error condition. ' ' Upon return, for i = 1, 2, ..., n - 1, ' ' key_array( i ) key_array( i_child2 ) Then i_max_child = i_child1 Else i_max_child = i_child2 End If If key_array( i_max_child ) > key_fa…

You are right, heap sort doesn't need recursion, and is more efficient than shell sort for large arrays. But if you compare the code size, it is hard to beat shell sort. This is a Java version: static void shellSort(T[] a, Comparator c) { int n = a.length; int h = 16, g = 1; while (n > g) { h = h + h + h / 4 + 16; g = (h + 15) / 16; } do { h = (h - 16) * 4 / 9; g = (h + 15) / 16; for (int i = g; i = g && c.compare(a[…

My code examples for heaps could be shorter than what I posted if I omitted my verbose documentation, error handling, and double spacing!!
Post reply on HN