Game Engine - Unreal Engine, C++, Python
Learning Outcome - Implementation of Different Sorting Algorithms and their Visualization
About the Project :
- I implemented visualization of different sorting algorithms for comparing completion time, swap count, and much more of each algorithms.
- I also used shuffle system (Fisher-Yates Shuffle) to randomize data using seeds.
- Future Update - Web Player Demo with UI interaction so others can visualize all functionality of project.
- More details about each algorithms and code Snippets are below.
What is sorting algorithm?
Using a comparison operator on the items, a sorting algorithm is used to reorder an array or list of elements. To determine the new order of elements in the relevant data structure, the comparison operator is utilized.
Comparison Table :
| Selection | Bubble | Merge | Insertion | Quick | Heap | Count | ||
|---|---|---|---|---|---|---|---|---|
| Random Seed 1 | Swaps | 198 | 5046 | 0 | 0 | 734 | 1162 | 0 |
| Time | 1.47s | 37.79s | 10.88s | 39.23s | 5.94s | 9.40s | 1.60s | |
| Random Seed 2 | Swaps | 198 | 5224 | 0 | 0 | 800 | 1152 | 0 |
| Time | 1.59s | 39.58s | 12.18s | 49.83s | 7.27s | 10.69s | 1.73s | |
| Random Seed 3 | Swaps | 198 | 5096 | 0 | 0 | 720 | 1124 | 0 |
| Time | 1.59s | 41.46s | 10.81s | 43.20s | 5.60s | 8.55s | 1.48s | |
Image Slicing using Python :
from image_slicer import slice
slice_count = 1000
slice('filename.jpg', slice_count)
Fisher-Yates Shuffle :
void ATileManager::ShuffleTiles()
{
//set seed value form randinit
FMath::RandInit(SeedNumber);
for (int i = AllTiles.Num() - 1; i > 0; i--)
{
//get random number between 0 and i
int j = FMath::Rand() % (i + 1);
//swap tile position and index
SwapTiles(AllTiles[i], AllTiles[j]);
}
//TempArray = AllTiles;
}
Selection Sort :
if (CurrentSort == ESortType::SELECTION)
{
//float StartTime = GetWorld()->GetTimeSeconds();
//temp index for comparison
int MinIndex;
for (int i = 0; i < AllTiles.Num() - 1; i++)
{
MinIndex = i;
//compare temp index with rest of indeces
for (int j = i + 1; j < AllTiles.Num(); j++)
{
if (AllTiles[j]->GetTileIndex() < AllTiles[MinIndex]->GetTileIndex())
MinIndex = j;
}
//add tiles to array for visualization
TileSwap1.Add(AllTiles[MinIndex]);
TileSwap2.Add(AllTiles[i]);
//swap tile i with temp index
SwapTileIndeces(AllTiles[MinIndex], AllTiles[i]);
//GetWorldTimerManager().SetTimer(SwapTimer, this, &ATileManager::SwapTilesTimer, 0.001f, true);
//SwapTiles(AllTiles[MinIndex], AllTiles[i]);
}
//float EndTime = GetWorld()->GetTimeSeconds();
//GEngine->AddOnScreenDebugMessage(-1, 2.f, FColor::Orange, FString::Printf(TEXT("%f"), (EndTime - StartTime) * 100000000.0f));
}
Bubble Sort :
else if (CurrentSort == ESortType::BUBBLE)
{
//float StartTime = GetWorld()->GetTimeSeconds();
//bool to check inner loop caused any swaps or not
//if not, means array is sorted
bool Swapped;
for (int i = 0; i < AllTiles.Num() - 1; i++)
{
Swapped = false;
for (int j = 0; j < AllTiles.Num() - i - 1; j++)
{
//compare j item with j + 1 item
if (AllTiles[j]->GetTileIndex() > AllTiles[j + 1]->GetTileIndex())
{
//add tiles to array for visualization
TileSwap1.Add(AllTiles[j]);
TileSwap2.Add(AllTiles[j + 1]);
//swap tiles
SwapTileIndeces(AllTiles[j], AllTiles[j + 1]);
//GetWorldTimerManager().SetTimer(SwapTimer, this, &ATileManager::SwapTilesTimer, 0.001f, true);
//SwapTiles(AllTiles[j], AllTiles[j + 1]);
Swapped = true;
}
}
//no swaps in inner loop, so break outer loop to stop sorting
if (!Swapped)
break;
}
//float EndTime = GetWorld()->GetTimeSeconds();
//GEngine->AddOnScreenDebugMessage(-1, 2.f, FColor::Orange, FString::Printf(TEXT("%f"), (EndTime - StartTime) * 1000000.0f));
}
Insertion Sort :
else if (CurrentSort == ESortType::INSERTION)
{
//temp array
auto* TempArray = new uint16[AllTiles.Num()];
for (int i = 0; i < AllTiles.Num(); i++)
TempArray[i] = AllTiles[i]->GetTileIndex();
//temp key for current item
int Key, j;
for (int i = 1; i < AllTiles.Num(); i++)
{
//setting key
Key = TempArray[i];
//setting inner loop item index
j = i - 1;
//cheking item [0, 1,...j] with key
//if item j index is greater than key
//add j item to j + 1 index
while (j >= 0 && TempArray[j] > Key)
{
//add tiles to array for visualization
TempArrayTiles.Add(AllTiles[j + 1]);
TempArrayIndexNew.Add(TempArray[j]);
TempArrayPosition.Add(FindLocationOfIndex(TempArray[j]));
TempArray[j + 1] = TempArray[j];
j = j - 1;
}
//loop break if j item is smaller than key
//then add key to j + 1 index
//add tiles to array for visualization
TempArrayTiles.Add(AllTiles[j + 1]);
TempArrayIndexNew.Add(Key);
TempArrayPosition.Add(FindLocationOfIndex(Key));
TempArray[j + 1] = Key;
}
}
Merge Sort :
else if (CurrentSort == ESortType::MERGE)
{
//temp array
auto* TempArray = new uint16[AllTiles.Num()];
for (int i = 0; i < AllTiles.Num(); i++)
TempArray[i] = AllTiles[i]->GetTileIndex();
//for (int i = 0; i < AllTiles.Num(); i++)
//UE_LOG(LogTemp, Warning, TEXT("%d"), TempArray[i]);
MergeSort(TempArray, 0, AllTiles.Num() - 1);
}
void ATileManager::MergeSort(uint16 TempArray[], int const FirstIndex, int const LastIndex)
{
if (FirstIndex >= LastIndex)
return;
auto MidIndex = FirstIndex + (LastIndex - FirstIndex) / 2;
MergeSort(TempArray, FirstIndex, MidIndex);
MergeSort(TempArray, MidIndex + 1, LastIndex);
Merge(TempArray, FirstIndex, MidIndex, LastIndex);
//ShowSortResult(FirstIndex, LastIndex);
}
//combining two array while sorting
void ATileManager::Merge(uint16 TempArray[], int const Left, int const Mid, int const Right)
{
//size for left array, with mid index
int const LeftArraySize = Mid - Left + 1;
//size for right array, with mid + 1 index
int const RightArraySize = Right - Mid;
//initialize left and right array
auto* LeftArray = new uint16[LeftArraySize];
auto* RightArray = new uint16[RightArraySize];
//setting left and right array value
for (int i = 0; i < LeftArraySize; i++)
LeftArray[i] = TempArray[Left + i];
for (int j = 0; j < RightArraySize; j++)
RightArray[j] = TempArray[Mid + 1 + j];
//index for left and right sub-array
int i = 0, j = 0;
//index of merged array
int IndexOfMergedArray = Left;
//copy data from left and right array to merged array
while (i < LeftArraySize && j < RightArraySize)
{
//if i index of left is smaller than j index of right
//set i index of left as merged index of temp array
if (LeftArray[i] <= RightArray[j])
{
//TempArrayIndexOld.Add(TempArray[IndexOfMergedArray]);
//add tiles to array for visualization
TempArrayTiles.Add(AllTiles[IndexOfMergedArray]);
TempArrayIndexNew.Add(LeftArray[i]);
TempArrayPosition.Add(FindLocationOfIndex(LeftArray[i]));
//setting i index of left as merged index of temp
TempArray[IndexOfMergedArray] = LeftArray[i];
i++;
}
//if i index of left is bigger than j index of right
//set j index of right as merged index of temp array
else
{
//TempArrayIndexOld.Add(TempArray[IndexOfMergedArray]);
//add tiles to array for visualization
TempArrayTiles.Add(AllTiles[IndexOfMergedArray]);
TempArrayIndexNew.Add(RightArray[j]);
TempArrayPosition.Add(FindLocationOfIndex(RightArray[j]));
//setting j index of right as merged index of temp
TempArray[IndexOfMergedArray] = RightArray[j];
j++;
}
IndexOfMergedArray++;
}
//checking if any item from left array is left to add in merged array
while (i < LeftArraySize)
{
//TempArrayIndexOld.Add(TempArray[IndexOfMergedArray]);
TempArrayTiles.Add(AllTiles[IndexOfMergedArray]);
TempArrayIndexNew.Add(LeftArray[i]);
TempArrayPosition.Add(FindLocationOfIndex(LeftArray[i]));
TempArray[IndexOfMergedArray] = LeftArray[i];
i++;
IndexOfMergedArray++;
}
//checking if any item from right array is left to add in merged array
while (j < RightArraySize)
{
//TempArrayIndexOld.Add(TempArray[IndexOfMergedArray]);
TempArrayTiles.Add(AllTiles[IndexOfMergedArray]);
TempArrayIndexNew.Add(RightArray[j]);
TempArrayPosition.Add(FindLocationOfIndex(RightArray[j]));
TempArray[IndexOfMergedArray] = RightArray[j];
j++;
IndexOfMergedArray++;
}
}
Quick Sort :
void ATileManager::QuickSort(int LowIndex, int HighIndex)
{
if (LowIndex < HighIndex)
{
//pivot index, as pivot index is in correct sorted position
int PivotIndex = Partition(LowIndex, HighIndex);
//sort array before pivot index
QuickSort(LowIndex, PivotIndex - 1);
//sort array after pivot index
QuickSort(PivotIndex + 1, HighIndex);
}
}
int ATileManager::Partition(int LowIndex, int HighIndex)
{
//set pivot at last item
int PivotIndex = AllTiles[HighIndex]->GetTileIndex();
//set i index as low index - 1
//correct index of pivot for now
int i = LowIndex - 1;
for (int j = LowIndex; j <= HighIndex - 1; j++)
{
//if j item is smaller than pivot, swap j item to i item
if (AllTiles[j]->GetTileIndex() < PivotIndex)
{
//increment low index, i.e increment correct position of pivot
i++;
//add tiles for visualization
TileSwap1.Add(AllTiles[i]);
TileSwap2.Add(AllTiles[j]);
//swap items
SwapTileIndeces(AllTiles[i], AllTiles[j]);
}
}
//now swap pivot to i + 1 index, as i + 1 is correct position of pivot
//add tiles for visualization
TileSwap1.Add(AllTiles[i + 1]);
TileSwap2.Add(AllTiles[HighIndex]);
//swap items
SwapTileIndeces(AllTiles[i + 1], AllTiles[HighIndex]);
//return correct index of pivot
return (i + 1);
}
Heap Sort :
void ATileManager::HeapSort(int Size)
{
//build heap
for (int i = (Size / 2) - 1; i >= 0; i--)
Heapify(Size, i);
//remove root node one by one from heap
for (int i = Size - 1; i > 0; i--)
{
//move root node to last
//add tiles for visualization
TileSwap1.Add(AllTiles[0]);
TileSwap2.Add(AllTiles[i]);
//swap items
SwapTileIndeces(AllTiles[0], AllTiles[i]);
//call max heapify on reduced heap
Heapify(i, 0);
}
}
void ATileManager::Heapify(int Size, int Node)
{
//Root node as largest
int Largest = Node;
int Left = 2 * Node + 1;
int Right = 2 * Node + 2;
//if left node is greater than largest, then largest is equal to left node
if (Left < Size && AllTiles[Left]->GetTileIndex() > AllTiles[Largest]->GetTileIndex())
Largest = Left;
//if right node is greater than largest, then largest is equal to right node
if (Right < Size && AllTiles[Right]->GetTileIndex() > AllTiles[Largest]->GetTileIndex())
Largest = Right;
//if largest not root node
if (Largest != Node)
{
//add tiles for visualization
TileSwap1.Add(AllTiles[Node]);
TileSwap2.Add(AllTiles[Largest]);
//swap tiles
SwapTileIndeces(AllTiles[Node], AllTiles[Largest]);
//heapify the sub tree
Heapify(Size, Largest);
}
}
Count Sort :
void ATileManager::CountSort()
{
//set first element as max
int Max = AllTiles[0]->GetTileIndex();
//find max element from array
for (int i = 1; i < AllTiles.Num(); i++)
{
if (AllTiles[i]->GetTileIndex() > Max)
Max = AllTiles[i]->GetTileIndex();
}
//set first element as min
int Min = AllTiles[0]->GetTileIndex();
//find min element from array
for (int i = 1; i < AllTiles.Num(); i++)
{
if (AllTiles[i]->GetTileIndex() < Min)
Min = AllTiles[i]->GetTileIndex();
}
//get range
int Range = Max - Min + 1;
//create new count array
TArray Count;
//create new temp array
auto* TempArray = new int[AllTiles.Num()];
//add 0 in count Tarray, to create Tarray of range number of element
for (int i = 0; i <= Range; i++)
{
Count.Add(0);
}
//store count of each element inside count array
for (int i = 0; i < AllTiles.Num(); i++)
{
Count[AllTiles[i]->GetTileIndex() - Min]++;
}
//set the count of each index by adding the count of previos index
for (int i = 1; i < Count.Num(); i++)
{
Count[i] += Count[i - 1];
}
for (int i = AllTiles.Num() - 1; i >= 0; i--)
{
//find i element of main array in count array
//set position of i in temp array based on position found in count array
TempArray[Count[AllTiles[i]->GetTileIndex() - Min] - 1] = AllTiles[i]->GetTileIndex();
//decresing the count of (i - min) element in count array
Count[AllTiles[i]->GetTileIndex() - Min]--;
}
//add tiles for visualization
for (int i = 0; i < AllTiles.Num(); i++)
{
TempArrayTiles.Add(AllTiles[i]);
TempArrayIndexNew.Add(TempArray[i]);
TempArrayPosition.Add(FindLocationOfIndex(TempArray[i]));
}
}
Resources :
- Sorting Algorithms - https://www.geeksforgeeks.org/sorting-algorithms/