打印 QuickSort 中间步骤的逻辑应该是什么

Question

我正在努力在我的快速排序程序执行时显示排序的中间步骤。

本质上，每次迭代后控制台window必须显示正在进行的数组排序的当前情况。

我能够在我的程序中添加交换和比较的总计数，但我无法找到一种方法来在现有代码中添加逻辑，程序也会在每次迭代后显示中间步骤。

#include <cstdlib>
#include <iostream>
using namespace std;

void quick_sort(int C[],int low,int high, int & quick_count);
void partition ( int C[], int low, int high, int &m, int &n, int & quick_count );
void swap(int* a, int* b);

int main()
{
    int num_of_items;
    int quick_count = 0;

    cout<<"Enter The Number Of Elements To Be Sorted: ";
    cin>>num_of_items;

    int quick[num_of_items];

    for(int i=0;i<num_of_items;i++)
    {
        cout<<"Element "<<i<<": ";
        cin>>quick[i];
    }

    cout<<endl;

    cout<<"Unsorted: "<<endl;
    for(int i=0;i<num_of_items;i++)
    cout<<quick[i]<<endl;
    cout<<"----------------------------------------"<<endl<<endl;
    cout<<"Sorted: "<<endl;

    quick_sort(quick,0,num_of_items-1, quick_count);
    for(int i=0;i<num_of_items;i++)
        cout<<quick[i]<<endl;

    cout<<"Quick sort count: "<<quick_count<<endl;
}



//preconditions: an array of integers is passed to the function,an integer that represents the low value, an integer that
// represents the high value in the array, an integer that is passed by reference that acts as the step counter for the sort
//postcondition: the array is sorted and the step counter is maintained back to the main since it was passed by reference.
void quick_sort (int C[], int low, int high, int & quick_count )
{
    int m, n;
    if ( low < high )
    {
        partition ( C, low, high, m, n, quick_count );
        quick_sort ( C, low, m, quick_count );
        quick_sort ( C, n, high, quick_count );
    }
}

//preconditions: an array of integers is passed to the function,an integer that represents the low value,an integer that
// represents the mid value in a section and an integer that represents the high value in the array,
// an integer that is passed by reference that acts as marker for one section, an integer that is passed by reference that acts as another marker,
// and an integer that is passed by reference that acts as the step counter for the sort.
//Postconditions:  The array is shifted into the partitions that make the quick sort function.
void partition ( int C[], int low, int high, int &m, int &n, int & quick_count)
{
    int pivot = C[low];
    int lastS1 = low - 1;
    int firstU = low;
    int firstS3 = high + 1;

    while ( firstU < firstS3 )
    {

        quick_count++;
        if ( C[firstU] < pivot )        // S1
        {
            ++lastS1;
            swap ( C[firstU],C[lastS1] );
            ++firstU;
        }
        else if ( C[firstU] == pivot ) // S2
            {++firstU;}
        else // C[firstU] > pivot      // S3
        {
            --firstS3;
            swap ( C[firstU], C[firstS3] );
        }
    }
        m = lastS1;
        n = firstS3;
}

//preconditions:  two integer pointer variables are passed to the function
//postconditions: The values that are pointed to by the pointers, swap address locations.
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

在特定于所需输出方面，

我正在尝试如下，

假设数组大小为 5

初始数组：12,3,54,6,32,87

迭代 1：

迭代 2： ....

.....

等等...

直到

排序数组：3,6,12,32,64,87

Answer 1

[更新]

在进一步的研究中，发现有一种方法可以使用称为 Lomuto Partitioning Method

的高效技术来显示快速排序的中间步骤

我最终能想出的程序如下： [如有需要，请随意进一步改进]

代码：

#include <iostream>
using namespace std;
int n;

// Function to print intermediate steps Array
void printArr(int A[])
{
    cout<<"-----------------------"<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<A[i]<<' ';
    }
    cout<<endl;
}


// Partition Function for Quicksort
int partition(int A[], int l, int r){
     int pivotValue = A[r];
     int storeIndex = l;
     for(int i=l; i<=r-1; i++){
         if(A[i] < pivotValue){
             swap(A[i], A[storeIndex]);
             storeIndex++;
         }
     }
     swap(A[storeIndex], A[r]);  // Move pivot to its final place
     return storeIndex;

}


void quick(int A[], int l, int r)
{
    if(l<r){
        int p = partition(A, l, r);
        printArr(A);
        quick(A, l, p-1);
        quick(A, p+1, r);

    }
}

int main()
{
    cout<<"Enter The Number Of Elements: ";
    cin>>n;
    int A[n];
    for(int i=0;i<n;i++)
    {
        cout<<"Element "<<i<<":";
        cin>>A[i];
    }

    quick(A, 0, n-1);
    cout<<"\nSorting Completed !"<<endl;
    return 0;
}

Answer 2

我在 Java 中有一个实现，其中控制台显示程序中发生的所有步骤。

由于它还包括在排序时打印数组的中间步骤，相信对您有所帮助。

import java.util.Arrays;
public class QuicksortDemo
{
  //Passes an array, the starting index and final idex.
  public static void quickSort(int[] arr, int start, int end)
  {
    //The following is used to recursively call the quickSort method.
    int partition = partition(arr, start, end);
    
    //Left partition
    if(partition-1>start) 
    {
      int indexToPrint=partition - 1;
      System.out.println("*** Quicksort occurs recursively with starting position "+start +" and ending position "+indexToPrint + " ***"); 
      quickSort(arr, start, partition - 1);
      System.out.println("Using partition "+ partition + " after quicksort. Array is now "+Arrays.toString(arr));
    }
    
    //Right partition
    if(partition+1<end) {
       int indexToPrint=partition + 1;
      System.out.println("*** Quicksort occurs recursively with starting position " + indexToPrint + " end position "+end + " ***");
      quickSort(arr, partition + 1, end);
      System.out.println("Using partition " + partition + " after quicksort. Array is now "+Arrays.toString(arr));
    }
  }
  
  //Partitions the array.
  public static int partition(int[] arr, int start, int end)
  {
    //Last element is taken as the index.
    int pivot = arr[end];
    System.out.println("Pivot is "+pivot +" based on array start position "+start+ " and end position "+end); 
    
    //Goes through each element of the array.
    for(int i=start; i<end; i++)
    {
      System.out.println ("Is the element " + arr[i] + " at position " + i +" less than the pivot " + pivot + "?");
      if(arr[i]<pivot)
      {
 int temp= arr[start];
 arr[start]=arr[i];
 System.out.println ("Yes it is, swapping " + temp + " at the comparison position " + start + " and " + arr[i] + " at position " + i);
 arr[i]=temp;
 
 //Increments the 'start' or 'i' value, which is used for swapping.
 start++;
 System.out.println("After swap, incremented the comparison position to "+start+". Array is now "+Arrays.toString(arr));
 System.out.println ();
      }
      else
      {
 System.out.println("No, do nothing.");
 System.out.println ();
      }
    }
    
    System.out.println("Reached end of array, swapping values at position " + start + " and pivot position "+end);
    int temp = arr[start];
    arr[start] = pivot;
    arr[end] = temp;
    //Prints array after each iteration.
    System.out.println("The array is now "+Arrays.toString(arr));
    return start;
  }
  
  public static void main(String[] args) 
  {
    long start = System.currentTimeMillis();
    // int[] arr = {331,57,96,3,4,5,66};
 int[] arr = {1,2,3,4,5,6,7};
    System.out.println("Unsorted array "+Arrays.toString(arr));
    quickSort(arr, 0, arr.length-1);
    long end = System.currentTimeMillis();
    long timeElapsed = end - start;
    System.out.println("Final sorted array "+Arrays.toString(arr));
    System.out.println ("The total elapsed time is : " + timeElapsed + "ms.");
  }
  
}

打印 QuickSort 中间步骤的逻辑应该是什么

What Should Be The Logic To Print Intermediate Steps Of QuickSort

c++

sorting

algorithm

quicksort

divide-and-conquer