Я пытаюсь сделать блок-схему для моей быстрой рекурсивной сортировки. Я так далеко, но не уверен, правильно ли.
Я пытаюсь показать детали в простой блок-схеме без какого-либо кода в блок-схеме.
Это то, что я сделал до сих пор, но я не уверен, что это правильно. Я пытаюсь найти то, как и когда быстрая сортировка узнала, что она отсортирована. Затем я могу изменить текст в окне принятия решений на блок-схеме, чтобы иметь больше смысла.
Вот мой код с комментариями, если они имеют какое-либо отношение.
#include <iostream>
using namespace std;
//this variable is the size of the array (amount of numbers in sort)
int const SIZE = 5;// This function swaps two numbers, arguments for these 2 numbers
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
// This function prints an array, Arguments for the array to be printed and number of elements in array
void PrintArray(int* array, int n)
{
int i;
for( i = 0; i < n; i++) cout<<array[i]<<',';
}
// This function splits the array around the pivot
// Arguments; array to be split, pivot to be returned, first element and last element
int SplitArray(int* array, int pivot, int startIndex, int endIndex)
{
int leftBoundary = startIndex;
int rightBoundary = endIndex;
//shuffle pivot until both the boundaries meet
while(leftBoundary < rightBoundary)
{
//keep moving until a lesser element is found or until the leftBoundary is reached
while( pivot < array[rightBoundary]
&& rightBoundary > leftBoundary)
{
//shift left through the split section
rightBoundary--;
}
swap(array[leftBoundary], array[rightBoundary]);
//keep moving through the array until a greater or equal element is found or until the section end is reached
while( pivot >= array[leftBoundary]
&& leftBoundary < rightBoundary)
{
//shift right through the split section
leftBoundary++;
}
swap(array[rightBoundary], array[leftBoundary]);
}
//returns the split point of the array because the left and right boundary are equal
return leftBoundary;
}
//This function quicksorts the data with arguments for array and its first and last element
void QuickSort(int* array, int startIndex, int endIndex)
{
//set the pivot as the start of split array
int pivot = array[startIndex];
int splitPoint;
//if they are equal then there is only one element and the sorting has finished
if(endIndex > startIndex)
{
//gets the position of the pivot and sets data in that position to pivot variable
splitPoint = SplitArray(array, pivot, startIndex, endIndex);
array[splitPoint] = pivot;
//**RECURSION - Quick sort first half of the array (left of pivot point)
QuickSort(array, startIndex, splitPoint-1);
//**RECURSION - Quick sort second half of the array (right of pivot point)
QuickSort(array, splitPoint+1, endIndex);
}
}
//beggining of main program, makes use of the functions declared before this
int main()
{
int array[SIZE];
//input unsorted array elements
cout << "This program demonstrates a quick sort using a recursive algorithm" << endl;
for(int i = 0; i < SIZE; i++)
{
cout<<"Enter an integer : ";
cin>>array[i];
}
//output the unsorted list
cout<<endl<<"The list you input is : "<<endl;
PrintArray(array, SIZE);
//sort array from first to last element and output the sorted list
QuickSort(array,0,SIZE - 1);
cout<<endl<<"The list has been sorted, now it is : "<<endl;
PrintArray(array,SIZE);
//refresh the input stream and
cin.sync();
cin.get();
}
Задача ещё не решена.
Других решений пока нет …