49
edits
Changes
→Assignment 1
Source Code: https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-to-ray-tracing/ray-tracing-practical-example
[[File:Profile.JPG]]
==== Profiling: bubble vs quick algorithm ====
It's a simple version of sorting algorithm.
Source code
void BubbleSort(int arr[], int size) {
int tmp; /*used for swapping*/
int i;
int j;
for (i = 0; i<size - 1; i++) {
for (j = 0; j<size - 1 - i; j++) {
if (arr[j + 1] < arr[j]) { /* compare the two neighbors */
tmp = arr[j]; /* swap a[j] and a[j+1] */
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
void InsertionSort(int arr[], int left, int right) {
int curr;
int i, j;
for (i = left + 1; i <= right; i++) {
curr = arr[i];
for (j = i; j>0 && arr[j - 1] > curr; j--) {
arr[j] = arr[j - 1];
}
arr[j] = curr;
}
}
void QuickSort(int arr[], int left, int right) {
if (right - left <= 3) {
InsertionSort(arr, left, right);
}
else {
int pivotpt = (left + right) / 2; //index of the pivot
int i = left;
int j = right - 1;
swap(arr[pivotpt], arr[right]);
pivotpt = right;
int pivot = arr[pivotpt];
while (i<j) {
while (i< right - 1 && arr[i]<pivot) i++;
while (j > 0 && arr[j]>pivot) j--;
if (i<j)
swap(arr[i++], arr[j--]);
}
if (i == j && arr[i] < arr[pivotpt])
i++;
swap(arr[i], arr[pivotpt]);
QuickSort(arr, left, i - 1);
QuickSort(arr, i + 1, right);
}
}
void QuickSort(int arr[], int size) {
QuickSort(arr, 0, size - 1);
}