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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

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

  1. #1
    Member
    Join Date
    Dec 2018
    Location
    Wisconsin
    Posts
    54
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Default 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?

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,140
    Thanks
    65
    Thanked 2,720 Times in 2,670 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Dec 2018
    Location
    Wisconsin
    Posts
    54
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Default Re: Understanding the mechanics of swapping variables for the quicksort algorithm

    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?

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,140
    Thanks
    65
    Thanked 2,720 Times in 2,670 Posts

    Default 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?
    What variables are you asking about?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Member
    Join Date
    Sep 2018
    Location
    Virginia
    Posts
    284
    My Mood
    Cool
    Thanks
    0
    Thanked 38 Times in 36 Posts

    Default Re: Understanding the mechanics of swapping variables for the quicksort algorithm

    Your highlighted code is difficult to read.

    Regards,
    Jim

  6. #6
    Junior Member
    Join Date
    Apr 2019
    Posts
    25
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Default 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.

  7. #7
    Member
    Join Date
    Dec 2018
    Location
    Wisconsin
    Posts
    54
    Thanks
    5
    Thanked 0 Times in 0 Posts

    Default Re: Understanding the mechanics of swapping variables for the quicksort algorithm

    Quote Originally Posted by Norm View Post
    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?

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,140
    Thanks
    65
    Thanked 2,720 Times in 2,670 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. swapping.
    By snehasishmohanta@gmail.co in forum What's Wrong With My Code?
    Replies: 22
    Last Post: July 10th, 2014, 09:24 AM
  2. Replies: 9
    Last Post: April 28th, 2014, 11:08 AM
  3. [SOLVED] [HELP] [HELP] Trouble To Understanding The Algorithm of my project
    By noobies in forum Algorithms & Recursion
    Replies: 4
    Last Post: April 15th, 2014, 09:01 PM
  4. swapping integers OOP
    By iamgonge in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 12th, 2013, 06:19 AM
  5. Quicksort algorithm displaying strange behaviour
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 0
    Last Post: April 19th, 2011, 12:56 PM