56
edits
Changes
→Assignment 1
LZSS Source Code: http://my.execpc.com/~geezer/code/lzss.c
==== SelectionSort ====
Selection Sort algorithm loops through every value in an array and finds the minimum values, assuming sort in ascending order, then puts it to the sorted area.
'''Source Code'''
<pre>
// C program for implementation of selection sort
#include <stdio.h>
#include<cstdlib>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
// Driver program to test above functions
int main()
{
int arrSize = 150000;
int arr[arrSize];
for (int i = 0; i < arrSize; i++) {
arr[i] = rand() % 10000 + 1;
}
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
return 0;
}
</pre>
'''gprof results'''
Tested the selection sort algorithm with three different array size: 50000, 100000, and 150000. The amount of time spent increased noticeably.
<pre>
// Array Size 50000
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
100.00 8.45 8.45 1 8.45 8.45 selectionSort(int*, int)
0.00 8.45 0.00 49999 0.00 0.00 swap(int*, int*)
granularity: each sample hit covers 4 byte(s) for 0.12% of 8.45 seconds
index % time self children called name
<spontaneous>
[1] 100.0 0.00 8.45 main [1]
8.45 0.00 1/1 selectionSort(int*, int) [2]
-----------------------------------------------
8.45 0.00 1/1 main [1]
[2] 100.0 8.45 0.00 1 selectionSort(int*, int) [2]
0.00 0.00 49999/49999 swap(int*, int*) [6]
-----------------------------------------------
0.00 0.00 49999/49999 selectionSort(int*, int) [2]
[6] 0.0 0.00 0.00 49999 swap(int*, int*) [6]
-----------------------------------------------
</pre>
<pre>
// Array Size 100000
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
100.00 33.96 33.96 1 33.96 33.96 selectionSort(int*, int)
0.00 33.96 0.00 99999 0.00 0.00 swap(int*, int*)
granularity: each sample hit covers 4 byte(s) for 0.03% of 33.96 seconds
index % time self children called name
<spontaneous>
[1] 100.0 0.00 33.96 main [1]
33.96 0.00 1/1 selectionSort(int*, int) [2]
-----------------------------------------------
33.96 0.00 1/1 main [1]
[2] 100.0 33.96 0.00 1 selectionSort(int*, int) [2]
0.00 0.00 99999/99999 swap(int*, int*) [6]
-----------------------------------------------
0.00 0.00 99999/99999 selectionSort(int*, int) [2]
[6] 0.0 0.00 0.00 99999 swap(int*, int*) [6]
-----------------------------------------------
</pre>
<pre>
// Array Size 150000
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
99.99 76.65 76.65 1 76.65 76.66 selectionSort(int*, int)
0.01 76.66 0.01 149999 0.00 0.00 swap(int*, int*)
granularity: each sample hit covers 4 byte(s) for 0.01% of 76.66 seconds
index % time self children called name
<spontaneous>
[1] 100.0 0.00 76.66 main [1]
76.65 0.01 1/1 selectionSort(int*, int) [2]
-----------------------------------------------
76.65 0.01 1/1 main [1]
[2] 100.0 76.65 0.01 1 selectionSort(int*, int) [2]
0.01 0.00 149999/149999 swap(int*, int*) [3]
-----------------------------------------------
0.01 0.00 149999/149999 selectionSort(int*, int) [2]
[3] 0.0 0.01 0.00 149999 swap(int*, int*) [3]
-----------------------------------------------
</pre>
'''Result in chart diagram'''
[[File:selectionSort.png]]
'''Reference'''
code website: https://www.geeksforgeeks.org/selection-sort/
=== Assignment 2 ===
=== Assignment 3 ===
