#Help with QuickSort partition function (sort function)

1 messages · Page 1 of 1 (latest)

jagged robin
#

Trying to understand this function:
public static int sort(int[] arr, int start, int end) {
int pivot = arr[end];
int pIndex = start;
for (int i = start; i < end; i++) {
if (arr[i] <= pivot) {
final int temp = arr[i];
arr[i] = arr[pIndex];
arr[pIndex] = temp;
pIndex++;
}
}
final int temp = arr[pIndex];
arr[pIndex] = pivot;
arr[end] = temp;
return pIndex;
}

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    // finding the pivot element
    int pivot = sort(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

how does it find the pivot element and how does it sort the array? how does it sort sub arrays? and how does it finally change the index of the pivot?

hot pollenBOT
#

<@&987246717831381062> please have a look, thanks.

dry fog
#

id suggest u watch a good video on quicksort first

#

starring at the full code like that wont work

#

u need to fully understand the algorithm first and thats best done watching illustrations

#

and then, after that, going through the code line by line with a small examplw input

#

i. e. running the logic per hand with pen/paper on a small example dataset

#

in particular for recursive stuff

jagged robin
#

I understand the recursive stuff

#

but the actual sorting no

#

if you can please explain it quickly that would be very nice 🙂

dry fog
#

as said, u should watch a video/illustration first

jagged robin
#

I saw a video

dry fog
#

the idea is that everything smaller than pivot is put left

#

and everything bigger right

#

then repeat the step on each half

#

this leads to everything sorted

#

the choice of pivot doesnt matter

#

any element will work

#

to understand why this technique works, u gotta watch illustrations

#

to understand why the code does what the illustration shows u gotta run it with pen/paper step by step

#

that sort method in ur code is just doing that step

#

it runs through all elements and pushes everything smaller than pivot left

#

and everything bigger right

#

thats all

jagged robin
#

how do I run it with pen/paper?

#

how do I illustrate this on paper?

dry fog
#

step by step, line by line

#

pick a small example dataset

#

[3, 6, 2, 8, 1]

#

for example

jagged robin
#

like [1,2,5,3,4,92,1,-6]

#

?

#

ok

dry fog
#

now look at sort([3, 6, 2, 8, 1], 0, 4)

jagged robin
#

what do I see?

dry fog
#

first line
int pivot = arr[end]

#

plug in, what is it?

#

its int pivot = arr[4] and thats int pivot = 1

jagged robin
#

oh and now I just put on left what's smaller than the pivot

dry fog
#

dont rush ahead

#

run the code step by step with pen paper

#

that way ull understand it

#

still with me or did i lose u on the first line?

jagged robin
#

I think i understand

dry fog
#

oh, okay. well then, good to go

#

cheers

jagged robin
#

cheers

#

.solved

dry fog
#

slash commands 🙂

jagged robin
#

/solved

dry fog
#

sounds like ur new to this^^

jagged robin
#

yes

hot pollenBOT
#

Closed the thread.

jagged robin
#

thank you