Quicksort: Partitioning an array
Why Stack Overflow recommends it
Stack Overflow users link it as an explanation of the partition step, both as a recommended learning aid and as the source they followed while writing their own quicksort code.
Recommended by 1 people across 1 different months, 2015 to 2021.
What it is
A short whiteboard-style walkthrough of the partition step in Quicksort, showing how an array is split around a pivot into smaller and larger elements and how the pivot's final position is returned. The presenter, KC Ang, notes in the description that the final shift could be a swap, which is more efficient.
What people said
Recommends Schwern · 2015-03 · Stack Overflow · on “In- place quick sort - Ruby”
Rather than trying to understand it in code, there's a number of very elegant explanations of the quicksort algorithm out there. Here are a few of my favorite illustrations which may help your understanding. With cups [this video] With Hungarian Dance [LINK] As for a Ruby example, the answers to this question cover that [LINK] .
Cites Ferda-Ozdemir-Sonmez · 2016-12 · Stack Overflow · on “Quick Sort Implementation Attempt”
I attempted to write a quicksort implementation after watching this video on youtube. [this video] but it does not work. Can someone tell me what I am doing wrong? Thank you Ferda public class Trial{ public static void main(String []args){ int arr[] = {7, 3, 4, 2, 6, 1, 5}; quickSort(arr, 0, 6); } public static void quickSort(int[] arrInput, int start, int end){ int arr[] = new int[end-start+1]; for(int i=start, j=0; i<end; i++, j++){ arr[j]=arrInput[i]; } int size = arr.length; int pivotValue = arr[size-1]; for (int i=-1; i<arr.length; i++){ for(int j=0; j<arr.length; j++){ if(arr[j]< pivotValue){ int temp = arr[j]; i++; arr[j] = arr[i]; arr[i] = temp; } for(int p = i; p< size-2; p++ ){ arr[p+1]
Cites SeanyMc · 2021-05 · Stack Overflow · on “Recursion confusion QuickSort”
In solutions online people seem to use a recursive method that calls partition to get pivot index, but i don't understand why this recursive method doesn't work def quickSort(arr, start, pivot_idx): if start>=pivot_idx: return i=start-1 j=start while(j<pivot_idx): if arr[j]<arr[pivot_idx]: i+=1 arr[j],arr[i]=arr[i],arr[j] j+=1 arr[pivot_idx], arr[i+1]=arr[i+1], arr[pivot_idx] quickSort(arr, 0, i) quickSort(arr, i+2, len(arr)-1) Edit: I've been following this explanation [this video] . A solution that works is changing 0 to start and len(arr)-1 to pivot_idx, but im not sure why that changes it