Thread: 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?

Okay, lets start over, following this guy's example:
https://www.youtube.com/watch?v=Fiot5yuwPAg&t=315s

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?

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.

Originally Posted by Norm

Sorry, I do not see any variable named x or named y?
What variables are you asking about?

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?