I am working towards displaying intermediate steps of sorting while my program on quicksort executes.
In Essence, after every iteration the console window must show the current situation of the sorting of the array in progress.
I was able to add the total counts of Swaps and Comparisons in my Program but am not able to figure out a way to add logic in the existing code whereby the program also displays the intermediate steps after each iteration.
#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;
}
In terms of being specific to the desired output,
I am trying to have it as follows,
say for array of size 5
Initial Array: 12,3,54,6,32,87
Iteration 1:
Iteration 2: ....
....
....
so on...
till
Sorted Array: 3,6,12,32,64,87
I have an implementation in Java where the console displays steps of literally everything that is going on within the program.
Since it also includes printing intermediate steps of arrays while sorting, I am sure it will be helpful to you.
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.");
}
}