Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Understanding the mechanics of swapping variables for the quicksort algorithm

1. ## Understanding the mechanics of swapping variables for the quicksort algorithm

I'm trying to learn the swap functionality for the quick sort algorithm, but the variable swapping seems to be going around in circles.

Here is the class with the partition and quickSort functions:
```package samsExperiments;

public class SamsArrays {

//Partition function:
//places pivot element at its correct position in the sorted array,
//and places all elements smaller than the pivot to the left of the
//pivot, and all elements larger than the pivot to the right of the
//pivot.
public int partition(int[] arr, int low, int high) {
int pivot = arr[high];//select the last element in the array as the initial pivot
int i = (low - 1);//index of smaller element
for(int j = low; j < high; j++) {
if(arr[j] <= pivot) {//if the current element is <= the pivot
i++;
//then swap the smaller element with the current element:
int temp = arr[i];System.out.println(temp + " = " + arr[i]);
arr[i] = arr[j];System.out.println(arr[i] + " = " + arr[j]);
arr[j] = temp;System.out.println(arr[j] + " = " + temp);
}
}
//else if the current element is > the pivot
//then swap the next element to the right of
//the low with the high element (or pivot):
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;

return i+1;
}

//Quick Sort:
void quickSort(int arr[], int low, int high) {
if(low < high) {
//pi is the partitioning index, and arr[pi]
//is now at the right place:
int pi = partition(arr,low,high);

//recursively sort elements before partition
//and after partition:
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
}```

And here is the class with the main method that calls the functions:
```package samsExperiments;

import java.util.Scanner;
import java.util.Arrays;

public class SamsExperimentsMain {

public static void main(String[] args){

int[] arr = {10,7,8,9,1,5};
int size = arr.length;

SamsArrays x = new SamsArrays();
x.quickSort(arr, 0, size-1);

}//end of main method

}//end of class```

Due to the output of the System.out.println on lines 17 thru 19 in the SamsArrays class, the output looks like this:

10 = 10
1 = 1
10 = 10

Seriously, if we wanted to assign the smaller element to the current element on line 18, what was the point of reassigning the current element BACK TO the smaller element (which was stored in temp on line 17) on line 19?  Reply With Quote

2. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm

What is printed when you print the values of arr[i] and arr[j]
before the swap
and after the swap?
That should show you the results.

The print statement in this code:
`int temp = arr[i];System.out.println(temp + " = " + arr[i]);`
will show that the two variables have the same value because that is what the assignment statement does.  Reply With Quote

3. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm

Okay, lets start over, following this guy's example:

According to him, the quick sort algorithm is explained like this:

In order for the element on the the left portion of the partition (x) to swap with the element on the right portion of the partition (y), x must be > the pivot, and y must be < the pivot.

Alternatively, if the swap doesn't happen that way, then:

If x > the pivot, but y is >= the pivot, then x stays at its current element, and y moves one element to the left.

If x <= the pivot, but y < the pivot, then y stays at its current element, and x moves one element to the right.

This keeps happening until the x and y pointers meet in the middle, and then the then the element in the middle swaps with the pivot.

Here is his code, with my own comments demonstrating what I understand about it:

```package SamsArrays;
import java.util.Arrays;
import java.util.Random;

public class QuickSort {

public void quickSort(int[] arr) {
quickSort(arr, 0, arr.length-1);
}

private void quickSort(int[] arr, int low, int high) {
if(low < high+1) {//if the distance between low and high is greater than 1
//(in other words if there's still more than one item to
//sort in that range of that partition),

int pi = partition(arr,low,high);//then we shall get a new pivot value (see partition function).

//Once we have the pivot, we need to call the quickSort function on both the left and right groups
//(partitions) of the pivot, so we can sort their elements:
quickSort(arr, low, pi-1);//left partition (low = leftmost element, pi-1 = rightmost element)
quickSort(arr, pi+1, high);//right partition (pi+1 = leftmost element, high = rightmost element)
}
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

private int getPivot(int low, int high) {
Random rand = new Random();
return rand.nextInt((high - low) + 1) + low;
}

private int partition(int[] arr, int low, int high) {
swap(arr, low, getPivot(low,high));//Swap the pivot value with the leftmost position (z),
int border = low + 1;//and then create a border value that points to the next right hand element of z.
for(int i = border; i <= high; i++) {
if(arr[i] < arr[low]) {//If the current element is less than the pivot,
swap(arr, i, border++);//then swap it with the border value.
System.out.println("We now have: " + Arrays.toString(arr));
}
}
swap(arr, low, border-1);//After the iteration, swap the pivot value into its proper position,
return border-1;//and return the new index of the pivot value.
}
}```
```package samsExperiments;

import java.util.Scanner;
import java.util.Arrays;
import SamsArrays.QuickSort;

public class SamsExperimentsMain {

public static void main(String[] args){

//int[] arr = {9,0,1,3,4,5,2,9,8,7,6,5,9,1,0,9};//array with duplicates
QuickSort qs = new QuickSort();
int[] arr = {17,41,5,22,54,6,29,3,13};

System.out.println("We start out with: " + Arrays.toString(arr));
qs.quickSort(arr);
System.out.println("Our sorted array is: " + Arrays.toString(arr));

}//end of main method

}//end of class```

The proper positions of both partitions are set in the quickSort function. The pivot value is randomly set in the partition function, which reduces the chance of a worst case scenario of maximum swaps and comparisons. We also iterate through the partition and swap elements as needed. That's all good. My problem is this:

What portion of his code causes the x and y pointers move?  Reply With Quote

4. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm

What portion of his code causes the x and y pointers move?
Sorry, I do not see any variable named x or named y?  Reply With Quote

5. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm

Regards,
Jim  Reply With Quote

6. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm

Graphic Explanation Quick Sort Algorithm

en.verejava.com/?id=19997472530244

Divide the array into 2 subarrays, then call yourself recursively, sort the subarrays quickly, and continue to the end.  Reply With Quote

7. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm Originally Posted by Norm Sorry, I do not see any variable named x or named y?
x and y were never variables in the actual code. If you read the first statement of my green text in that post:

In order for the element on the the left portion of the partition (x) to swap with the element on the right portion of the partition (y)

I used x and y, so that I wouldn't have to keep saying "the element on the left portion of the partition" and "the element on the right portion of the partition" over and over again, as that would be long-winded.

Getting back to the question I asked, watch the video from 1:34 - 1:57 with the link that I provided in the other post, as it reflects what I explained with my green text. In my existing code, there is a border variable in the partition function used to iterate through and compare the current element with the pivot, and then swap as needed, but why aren't there two pointers like he talked about in the video? Where is the action described with my green text in my other post actually happening in the code?  Reply With Quote

8. ## Re: Understanding the mechanics of swapping variables for the quicksort algorithm

As Jim said, the green color makes the text hard to read. Please use another color.

I don't see how this question is about java programming. It seems to be about the sorting algorithm. Use Google to find discussions about the sorting algorithm you are interested in.  Reply With Quote