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?