ADVANCE_QUICKSORT: print every step of partition/insertion

user_19169227 0
Viewed 51

I've learned and coded QuickSort(), Partition() and InsertionSort() myself, hence be able to run the code and sort arrays correctly, but what if I want to print in java and show every single steps the SORT algorithms do?

***Demand:

***Use QuickSort combines InsertionSort to enhence the efficiency. If the amount of element of left/right subArray which devided by pivot is below 3(A[0..n-1], n<=3),

***=>use InsertionSort()

The output should be like this:

<BEFORE SORTING>:[10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
use_partition:[1, 4, 2, 8, 7, 3, 5, 9, 6, 10]
use_partition:[1, 3, 2, 4, 7, 8, 5, 9, 6, 10]
use_insertion:[1, 2, 3, 4, 7, 8, 5, 9, 6, 10]
use_partition:[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]
use_partition:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
<AFTER SORTING>:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

I would like to print the steps by java making the implementation more clearly, my first thought is to use some conditional loop, does anyone know where can I find the relative article? Thanks a lot.

Sorry, here's the code I wrote:

import java.util.Arrays;
public class Main{
   public static void main(String args[]){
      int[] array1 = {10, 4, 2, 8, 7, 3, 5, 9, 6, 1};
      int n1 = array1.length;
      System.out.print("Before sorting is: ");
      System.out.println(Arrays.toString(array1));
      System.out.print("After sorting is: ");
      Quicksort(array1, 0, n1-1);
      /*
      the display loop I need
      */
   } //end main()

    public static void Quicksort(int[] array, int start, int end){
        if(start<end){
            if(end-start <=3){
           InsertionSort(array, start, end);
        }else{
            int pivot = HoarePartition(array, start, end); 
            Quicksort(array, start, pivot); 
            Quicksort(array, pivot+1, end);}    
        }
        }
    } //end Quicksort()

    public static void swapIJ(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    } //end swapIJ

    public static int HoarePartition(int[] array, int start, int end){
        int pivot = array[start];
        int i = start -1 ;
        int j = end + 1;
        while(true){
            do{i++;}while(array[i] < pivot);
            do{j--;}while(array[j] > pivot);

            if(i>=j)
               return j;
            swapIJ(array, i, j);
        } //end while
    } //end HoarePartition()

    public static void InsertionSort(int[] array) {
       for(int i = 1; i < array.length; i++) {
           int temp = array[i];
           int j = i - 1;
        
           while(j >= 0 && array[j] > temp) {
               array[j + 1] = array[j];
               j--;
           }
           array[j + 1] = temp;
       } //end for
    } //end InsertionSort()
insertion-sort implementation quicksort algorithm java
1 Answers

As suggested in the comments, you could place a System.out.println(Arrays.toString(array)) at every call of your quicksort method. This will print the state of your array at every sorting iteration.

For example, in your code it could be placed in the HoarePartition method right before returning.

public static int HoarePartition(int[] array, int start, int end) {
    int pivot = array[start];
    int i = start - 1;
    int j = end + 1;
    while (true) {
        do {
            i++;
        } while (array[i] < pivot);
        do {
            j--;
        } while (array[j] > pivot);

        if (i >= j) {
            //Printing the array status after the updates and right before returning
            System.out.println(Arrays.toString(array));
            return j;
        }
        swapIJ(array, i, j);
    } //end while
} //end HoarePartition()
user_44156250
Related