Tag: Shell Sort

The Parallel Programming Library (PPL) is one of my favorite features in C++Builder runtime library. PPL allows developers to create tasks that run in parallel to take advantage of multi-core processors.

Using the PPL, you can: 1) speed up loops with a Parallel For, 2) run multiple tasks in parallel using TTask, and 3) use Future Objects to allow a process run with your program focused on other work until the future value is set.

To showcase the TTask feature of the PPL, I’ve created a C++Builder VCL application (build and tested using the C++Builder 10.4 Sydney release) that runs three sort algorithms in separate tasks – Bubble Sort, Shell Sort and the ISO C++ standard Sort (which implements the Quicksort algorithm).

The User Interface

The VCL user interface for my application includes a TButton, two TMemos, and four TLabels. The TButton onClick event handler creates a vector of integers, creates three TTasks (for the sort algorithms) and waits for the sort tasks to complete using the TTask::WaitForAll method.

The Code

MainUnit.h:

#ifndef MainUnitH
#define MainUnitH
//---------------------------------------------------------------------------
#include <System.Classes.hpp>
#include <Vcl.Controls.hpp>
#include <Vcl.StdCtrls.hpp>
#include <Vcl.Forms.hpp>
#include <Vcl.ExtCtrls.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:	// IDE-managed Components
	TButton *Button1;
	TLabel *SortingStatusLabel;
	TLabel *BubbleSortLabel;
	TMemo *Data_Memo;
	TMemo *SortResult_Memo;
	TLabel *ShellSortLabel;
	TLabel *STDSortLabel;
	void __fastcall Button1Click(TObject *Sender);
private:	// User declarations
public:		// User declarations
	__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif

MainUnit.cpp:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <System.Threading.hpp>
#include <vector>
#include <algorithm>
#pragma hdrstop

#include "MainUnit.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{

	_di_ITask My_Tasks[3];
	const int max_data = 15000;   // number of random numbers to create

	int LoopValue = 0;

	Button1->Enabled = false;
	Button1->Update();
	BubbleSortLabel->Caption = "Bubble Sort";
	BubbleSortLabel->Update();
	ShellSortLabel->Caption = "Shell Sort";
	ShellSortLabel->Update();
	STDSortLabel->Caption = "std::sort";
	STDSortLabel->Update();

	SortingStatusLabel->Caption = "Sorting "+IntToStr(max_data)+" integers!";
	SortingStatusLabel->Update();

	// Windows GetTicks() start and stop for each sort method
	int StartBubble,StopBubble;
	int StartShell,StopShell;
	int StartSTD,StopSTD;

	Data_Memo->Lines->Clear();
	SortResult_Memo->Lines->Clear();

	// create a vector of data that all sort algorithms will use
	std::vector<int> my_data;

	// populate the vector with integers
	for (int i = 1; i <= max_data; i++) {
		int random_value = Random(max_data);
		my_data.push_back(random_value);
		// Data_Memo->Lines->Add(IntToStr(random_value));
	}

	// copy data vector to sort vectors
	std::vector<int> bubble_data = my_data;
	std::vector<int> shell_data = my_data;
	std::vector<int> std_data = my_data;

	// First Task - Bubble Sort
	My_Tasks[0] = TTask::Create([&](){
		// Set Bubble Sort Windows GetTickCount()
		StartBubble = GetTickCount();
		// body of Bubble Sort
		bool swapp = true;
		while(swapp){
			swapp = false;
			for (size_t i = 0; i < bubble_data.size()-1; i++) {
				if (bubble_data[i]>bubble_data[i+1] ){
					bubble_data[i] += bubble_data[i+1];
					bubble_data[i+1] = bubble_data[i] - bubble_data[i+1];
					bubble_data[i] -=bubble_data[i+1];
					swapp = true;
				}
			}
		}
		// Set the Bubble Sort Stop GetTicks()
		StopBubble = GetTickCount();
	});
	// Start the Bubble Sort Task
	My_Tasks[0]->Start();


	// Second Task - Shell Sort
	My_Tasks[1] = TTask::Create([&](){
		// Set Shell Sort Windows GetTickCount()
		StartShell = GetTickCount();
		// body of the Shell Sort
		for (int gapSize = shell_data.size() / 2; gapSize > 0; gapSize /= 2) {
			for (int currentIndex = gapSize; currentIndex < shell_data.size(); currentIndex++) {
				// save the currentIndex
				int currentIndexCopy = currentIndex;
				// save the value of the currentIndex
				int item = shell_data[currentIndex];
				while (currentIndexCopy >= gapSize && shell_data[currentIndexCopy - gapSize] > item) {
					shell_data[currentIndexCopy] = shell_data[currentIndexCopy - gapSize];
					currentIndexCopy -= gapSize;
				}
				shell_data[currentIndexCopy] = item;
			}
		}
		// Set the Shell Sort Stop GetTicks()
		StopShell = GetTickCount();
	});
	// Start the Shell Sort
	My_Tasks[1]->Start();


	// Third Task - std::sort
	My_Tasks[2] = TTask::Create([&](){
		// Set std::sort Windows GetTickCount()
		StartSTD = GetTickCount();
		// Body of the std::sort
		std::sort(std_data.begin(),std_data.end());
		// Set the std::sort Stop GetTicks()
		StopSTD = GetTickCount();
	});
	// Start the Shell Sort
	My_Tasks[2]->Start();

	// wait until all of the sorting tasks complete
	TTask::WaitForAll(My_Tasks, sizeof(My_Tasks)/sizeof(My_Tasks[0])-1);

	SortingStatusLabel->Caption = "Sorting All done!";

	BubbleSortLabel->Caption = "Bubble Sort Time: "
		+ IntToStr(StopBubble - StartBubble)
		+ " ms";
	BubbleSortLabel->Update();

	ShellSortLabel->Caption = "Shell Sort Time: "
		+ IntToStr(StopShell - StartShell)
		+ " ms";
	ShellSortLabel->Update();

	STDSortLabel->Caption = "std::sort: "
		+ IntToStr(StopSTD - StartSTD)
		+ " ms";
	STDSortLabel->Update();

	// if you want to see the sort results un-comment
	// one of the for loops and the sort result memo statement
	// for(int n : std_data) {
	// for(int n : bubble_data) {
	// for(int n : shell_data) {
		// SortResult_Memo->Lines->Add(IntToStr(n));
	// }

	// clear the vectors
	my_data.clear();
	bubble_data.clear();
	shell_data.clear();
	std_data.clear();

	Button1->Enabled = true;
}
//---------------------------------------------------------------------------

The form after sorting 15,000 integers

References

PPL – Parallel Programming Library – http://docwiki.embarcadero.com/RADStudio/Sydney/en/Using_the_Parallel_Programming_Library

Using TTask – http://docwiki.embarcadero.com/RADStudio/Sydney/en/Using_TTask_from_the_Parallel_Programming_Library

Using TParallel::For – http://docwiki.embarcadero.com/RADStudio/Sydney/en/Using_TParallel.For_from_the_Parallel_Programming_Library

Using TTask::IFuture – http://docwiki.embarcadero.com/RADStudio/Sydney/en/Using_TTask.IFuture_from_the_Parallel_Programming_Library

Algorithms Library – https://en.cppreference.com/w/cpp/algorithm

std::sort – https://en.cppreference.com/w/cpp/algorithm/sort

C++Builder Product Information

C++Builder Product Page – Native Apps that Perform. Build Windows C++ Apps 10x Faster with Less Code
C++Builder Product Editions – C++Builder is available in four editions – Professional, Enterprise, Architect and Community (free). C++Builder is also available as part of the RAD Studio development suite.