Is this a badly written partition algorithm? Quicksort

[shivajikobardan]

        public static int partition(int[] list, int first, int last) {
            int pivot = list[first];
            int low = first + 1;
            int high = last;
   
            while (high > low) {
                while (low <= high && list[low] <= pivot) low++;
                while (low <= high && list[high] > pivot) high--;
                if (high > low) {
                    int temp = list[high];
                    list[high] = list[low];
                    list[low] = temp;
                }
            }
            while (high > first && list[high] >= pivot) high--;
            if (pivot > list[high]) {
                list[first] = list[high];
                list[high] = pivot;
                return high;
            } else {
                return first;
            }
        }

This is the algorithm I want to understand as a whole. Obviously when I dry run it, it produces correct results. But that is not what I want. I want to be able to write this in a closed-book exam. I memorized it with a neat trick. But I hope to understand it as well.

My concerns with the algorithms:

- Why nested loops for high and low comparison?(The first loop)

- The algorithm seems counterintuitive and unreadable. It loops till high>low, then checks high>low inside that loop. Haha. I understand high and low were changed just earlier but it makes no sense. Maybe it is the naming conventions or maybe the algorithm itself.

- Why is the need to do high-- out of the nested loop? I can obviously trace it with list={1,3,2,-1} and it will show that it is necessary. But I think code should be so  clear that a simple person can read it and immediately understand its need.

- Increasing/Decreasing low/high

The intuition is clearly missing in this algorithm and that is what I really hate about it.

[xvr]

It looks like it's written by ChatGPT.
It looks similar, almost correct, but not.

[kite31]

Akin to the video you were provided to illustrate insertion sort, here is the one on quicksort:

[TheCalligrapher]

My concerns with the algorithms:

- Why nested loops for high and low comparison?(The first loop)

Why not? There are many different ways to implement the search for two swappable elements. I actually find this approach with additional loops more natural than any alternative. I usually do it the same way. When facing a choice between a) write a greater number of cycles, each of which is narrowly specialized, or b) write a lesser number of cycles, each of which does several things at once, I'd prefer option a.

And it is ostensibly more efficient than the classic "kindergarten" implementation of partitioning without these nested loops.

- The algorithm seems counterintuitive and unreadable.

That's the inherent property of quicksort/partitioning algorithm. If I'm not mistaken, it was Knuth who said that even seasoned programmers usually cannot implement quicksort properly at the first try.

It loops till high>low, then checks high>low inside that loop. Haha. I understand high and low were changed just earlier but it makes no sense.

Yes, it does perform an unnecessary condition duplication and double checking (i.e. after the `if` the cycle condition will check the same thing) on every iteration except the very first one. I personally prefer to avoid such things, so I'd opt for a `break` inside the `if` (and a `do/while (true)` cycle with a pre-check). But it is not really a big deal. More of a matter of a personal preference.

- Why is the need to do high-- out of the nested loop? I can obviously trace it with list={1,3,2,-1} and it will show that it is necessary. But I think code should be so  clear that a simple person can read it and immediately understand its need.

We need to find the proper final location to transfer (swap) our pivot value to. That's what that extra cycle does.

The intuition is clearly missing in this algorithm and that is what I really hate about it.

It is property of the algorithm, not of the implementation you quoted.

[cfbsoftware]

- The algorithm seems counterintuitive and unreadable.

Hopefully you can find an algorithm / implementation that you believe to be more "readable and intuitive" from the many solutions presented here:

https://rosettacode.org/wiki/Sorting_algorithms/Quicksort

[paulca]

Am I the only one to pick up on "partition algorithm"?

Sorting as a way to partition data would normally fall into "if you have a really good reason you need to do it that way".

Partitioning in my experience is usually related to not being able to hold all the data at once and wanting to spread it across many nodes in a "uniform" but "practical" way.  That or specific "autonomous" groupings for concurrency scope.

[golden_labels]

The thread is about quicksort. Partition is a step in this sorting algorithm.

[SiliconWizard]

Partitioning is a base step for a any divide-and-conquer algorithm.
Partition data into smaller subsets and process those subsets recursively.

[paulca]

Partitioning is a base step for a any divide-and-conquer algorithm.
Partition data into smaller subsets and process those subsets recursively.

You mean like a btree et. al?

I'm more familiar with partitions being a burden to sorting.  If you partition in 2, on basically anything and sort 1 and 2 then you still need to resort 1+2.

I suppose if you were to, say, take the average and bucket things "smaller than averge", "larger than average" and then recursively traverse the dividing halfs.  That would sort the whole list.

[TheCalligrapher]

If you partition in 2, on basically anything and sort 1 and 2 then you still need to resort 1+2.

Not "resort". Merge. See below.

I suppose if you were to, say, take the average and bucket things "smaller than averge", "larger than average" and then recursively traverse the dividing halfs.  That would sort the whole list.

Yes, that's how partitioning is used in quick-sort. Thanks to that, once you sorted the halfs, the whole array becomes sorted, no need to do anything extra.

But in general case, the divide-and-conquer approach might require an additional post-processing step. I.e. at each recursive level of D&C, once the smaller sub-problems are solved, we might still need an additional step to combine the smaller sub-solutions into one larger solution for the current level. That's normal. There's nothing wrong with it, as long as the combining operation is reasonably efficient. This is the backtracking stage of recursion, also a natural part of D&C approach.

For example, that's exactly how a recursive implementation of merge-sort would work. At each recursive level we arbitrarily split our array into two (or more) smaller chunks, apply the algorithm (recursively) to each chunk, and then merge the results into the sorted array at the current level. Note, we don't "resort" as you seemed to suggest above. We merge. Merging of already sorted arrays is a significantly simpler and more efficient operation than full-blown resorting. The whole idea of merge-sort is based on that.

[paulca]

The thing is, in 25+ years of professional software development the number of times I have had to write a sorting algo is exactly 0.

At best investigations into them are viable when choosing for performance or foot print.  Usually when performance is concerned sorting becomes taboo entirely.  Otherwise they are best "lift and drop in" from a much more acdemically correct and peer reviewed source/library, even IEEE.

The most knarly sorting problems I have faced have involved data which does not and cannot fit on any single node.  Data get loaded where it lies and if you want to sort (or group or any other aggregate) on the full set.... you have problems.  Problems that if you don't address carefully will result in upwards of 10 times the total datasize transiting the network in "shuffles". 

This is where a hint for sorting data emerges.  Don't sort the data, sort the index.  It's usually far more performant to sort an index than the data itself.  Leaving the data "random" access and "random stored" or just "stored in optimised storage form" has advantages unless you stored it on tape of offline storage.