MINISTRY OF EDUCATION, CULTURE AND RESEARCH

OF THE REPUBLIC OF MOLDOVA

Technical University of Moldova
Faculty of Computers, Informatics and Microelectronics
Department of Software and Automation Engineering

GEORGE RĂBUȘ

Report
Laboratory Work No.2

of the "Data Structures and Algorithms" course

Verificat:
Burlacu Natalia, PhD, associate professor
Department of Software and Automation Engineering,
Facultatea FCIM, UTM

Chisinau – 2023

21
 The structure of the report for the laboratory work in the "Data
Structures and Algorithms" course will contain:

1. The purpose of the laboratory work (formulated by the student according

to the problem to be solved);
2. For each task should be written the condition/conditions of the problems;
3. The program code, having relevant comments in it will be present for
each given task;
4. For each task should be shown the screenshot of the code execution (in all
aspects of the code run);
5. The student's conclusions regarding the content of the laboratory work
with personal reflections on what was achieved.
6. The name and surname of the student/teacher and no. the laboratory work
should be modified according to didactical requirements.

Note:
 The report pages should be numbered in the footer, center area;
 The text from items 1 & 2; 4 & 5 have to be written in Times New Roman, font
size 14 pt;
 The space between the lines will be set at 1,5 lines.
 Item 3 of this list (the developed program code should be written in relation to
Courier New, font size 10 pt; the space between code lines being 1.15 lines).
 The report should be uploaded for checking by the lab teacher in the right
Report section (numbered in the same mode as your task) according to the
deadline terms specified by your teacher.

21
1)
The purpose of this laboratory was to familiarize myself and to be able to work
with new sorting alogirthms like shell sort, quicksort and counting merge.
2)

21
3)
Program Task1:
#include <stdio.h>
#include <math.h>

void swap(int *a, int *b){

int aux = *a;
*a = *b;
*b = aux;
}

void print_array(int *a, int n){

for (int i = 0; i < n; i++){
printf("%d ", *(a+i));
}
printf("\n");
}

void task1(int *a, int n){

int min = a[0];
int index_min = 0;
int index_max = 0;
int max = a[0];
for (int i = 0; i < n; i++){
if (*(a+i) < min){
min = *(a+i);
index_min = i;
}
if (*(a+i) > max){
max = *(a+i);
index_max = i;
}
}
// printf("Min: %d, index: %d\n", min, index_min);
// printf("Max: %d, index: %d\n", max, index_max);

21
 for (int i = index_min + 1; i < trunc(index_max-index_min)/2 + index_min;
i++) {
int j = index_max - (i - index_min);
swap(&(*(a+i)), &(*(a+j)));
}
}

void task2(int *a,int *b, int n){

print_array(a, n);
print_array(b, n);
}

// function to find the partition position

int partition(int *array, int low, int high) {

// select the rightmost element as pivot

int pivot = *(array + high);

// pointer for greater element

int i = (low - 1);

// traverse each element of the array

// compare them with the pivot
for (int j = low; j < high; j++) {
if (*(array + j) <= pivot) {

// if element smaller than pivot is found

// swap it with the greater element pointed by i
i++;

// swap element at i with element at j

swap(&(*(array + i)), &(*(array + j)));
}
}

// swap the pivot element with the greater element at i

swap(&(*(array + i + 1)), &(*(array + high)));

// return the partition point

21
 return (i + 1);
}

int partition2(int *array, int low, int high) {

// select the rightmost element as pivot
int pivot = *(array + high);

// pointer for greater element

int i = (low - 1);

// traverse each element of the array

// compare them with the pivot
for (int j = low; j < high; j++) {
if (*(array +j) >= pivot) { // Change this line to reverse the sorting
order
// if element greater than pivot is found
// swap it with the smaller element pointed by i
i++;

// swap element at i with element at j

swap(&(*(array + i)), &(*(array + j)));
}
}

// swap the pivot element with the smaller element at i

swap(&(*(array + i + 1)), &(*(array + high )));

// return the partition point

return (i + 1);
}

void task3(int *array, int low, int high) {

if (low < high) {

// find the pivot element such that

// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);

21
 // recursive call on the left of pivot
task3(array, low, pi - 1);

// recursive call on the right of pivot

task3(array, pi + 1, high);
}
}
void task3_2(int *array, int low, int high) {
if (low < high) {

// find the pivot element such that

// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition2(array, low, high);

// recursive call on the left of pivot

task3_2(array, low, pi - 1);

// recursive call on the right of pivot

task3_2(array, pi + 1, high);
}
}

void task4(int *array, int n) {

// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = *(array + i);
int j;
for (j = i; j >= interval && *(array + j - interval) > temp; j -=
interval) {
*(array + j) = *(array + j - interval);
}
*(array + j) = temp;
}
}
}

void task4_2(int *array, int n) {

21
 // Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = *(array + i);
int j;
for (j = i; j >= interval && *(array+j - interval) < temp; j -=
interval) {
*(array + j) = *(array+j - interval);
}
*(array + j) = temp;
}
}
}

int main() {
int n;
scanf("%d", &n);
int a_original[50];
int a_modified[50];
for (int i = 0; i < n; i++)
scanf("%d", &a_original[i]);
for (int i = 0; i < n; i++)
{a_modified[i] = a_original[i];}
printf("\nTasks:\n\n");
task1(a_modified,n);
printf("Display the original and modified arrays:\n");
task2(a_original,a_modified,n);
printf("Display the original array after quick-sorting:\n");
task3(a_original, 0, n - 1);
print_array(a_original, n);
task3_2(a_original, 0, n - 1);
print_array(a_original, n);
printf("Display the modified array after shell-sorting:\n");
task4(a_modified,n);
print_array(a_modified, n);
task4_2(a_modified,n);
print_array(a_modified, n);
return 0;
//-18 10 -3 7 28 55 -4
}

21
Program Task2:
#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {

int aux = *a;
*a = *b;
*b = aux;
}

void print_array(int *a, int n) {

for (int i = 0; i < n; i++) {
printf("%d ", *(a + i));
}
printf("\n");
}

void task1(int *a, int n) {

int min = a[0];
int index_min = 0;
int index_max = 0;
int max = a[0];
for (int i = 0; i < n; i++) {
if (*(a + i) < min) {
min = *(a + i);
index_min = i;
}
if (*(a + i) > max) {
max = *(a + i);
index_max = i;
}
}

21
 for (int i = index_min + 1; i < (index_max - index_min) / 2
+ index_min; i++) {
int j = index_max - (i - index_min);
swap(&(*(a + i)), &(*(a + j)));
}
}

void task2(int *a, int *b, int n) {

print_array(a, n);
print_array(b, n);
}

void merge(int *arr, int l, int m, int r) {

int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

// Create temp arrays on the stack

int *L = malloc(n1 * sizeof(int));
int *R = malloc(n2 * sizeof(int));

// Check for memory allocation errors

if (L == NULL || R == NULL) {
fprintf(stderr, "Memory allocation error\n");
exit(EXIT_FAILURE);
}

// Copy data to temp arrays L[] and R[]

for (i = 0; i < n1; i++)
*(L + i) = *(arr + l + i);
for (j = 0; j < n2; j++)
*(R + j) = *(arr + m + 1 + j);

21
 // Merge the temp arrays back into arr[l..r]
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (*(L + i) <= *(R + j)) {
*(arr + k) = *(L + i);
i++;
} else {
*(arr + k) = *(R + j);
j++;
}
k++;
}

// Copy the remaining elements of L[], if there are any

while (i < n1) {
*(arr + k) = *(L + i);
i++;
k++;
}

// Copy the remaining elements of R[], if there are any

while (j < n2) {
*(arr + k) = *(R + j);
j++;
k++;
}

// Free the dynamically allocated memory

free(L);
free(R);
}

21
void mergeSort(int *arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

void merge2(int *arr, int l, int m, int r) {

int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

// Create temp arrays on the stack

int *L = malloc(n1 * sizeof(int));
int *R = malloc(n2 * sizeof(int));

// Check for memory allocation errors

if (L == NULL || R == NULL) {
fprintf(stderr, "Memory allocation error\n");
exit(EXIT_FAILURE);
}

// Copy data to temp arrays L[] and R[]

for (i = 0; i < n1; i++)
*(L + i) = *(arr + l + i);
for (j = 0; j < n2; j++)
*(R + j) = *(arr + m + 1 + j);

21
// Merge the temp arrays back into arr[l..r]
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (*(L + i) >= *(R + j)) {
*(arr + k) = *(L + i);
i++;
} else {
*(arr + k) = *(R + j);
j++;
}
k++;
}

// Copy the remaining elements of L[], if there are any

while (i < n1) {
*(arr + k) = *(L + i);
i++;
k++;
}

// Copy the remaining elements of R[], if there are any

while (j < n2) {
*(arr + k) = *(R + j);
j++;
k++;
}

// Free the dynamically allocated memory

free(L);
free(R);

21
}

void mergeSort2(int *arr, int l, int r) {

if (l < r) {
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort2(arr, l, m);
mergeSort2(arr, m + 1, r);

merge2(arr, l, m, r);
}
}

void countingSort(int *array, int size) {

int output[10];

// Find the largest element of the array

int max = *array;
for (int i = 1; i < size; i++) {
if (*(array + i) > max)
max = *(array + i);
}

// The size of count must be at least (max+1) but

// we cannot declare it as int count(max+1) in C as
// it does not support dynamic memory allocation.
// So, its size is provided statically.
int count[100];

// Initialize count array with all zeros.

for (int i = 0; i <= max; ++i) {
*(count + i) = 0;

21
 }

// Store the count of each element

for (int i = 0; i < size; i++) {
(*(count + *(array + i)))++;
}

// Store the cumulative count of each array

for (int i = 1; i <= max; i++) {
*(count + i) += *(count + (i - 1));
}

// Find the index of each element of the original array in

count array, and
// place the elements in the output array
for (int i = size - 1; i >= 0; i--) {
*(output + (*(count + *(array + i))) - 1) = *(array + i);
(*(count + *(array + i)))--;
}

// Copy the sorted elements into the original array

for (int i = 0; i < size; i++) {
*(array + i) = *(output + i);
}
}

void countingSort2(int *array, int size) {

int output[100];

// Find the largest element of the array

int max = *array;
for (int i = 1; i < size; i++) {
if (*(array + i) > max)

21
 max = *(array + i);
}

// The size of count must be at least (max+1)

int count[max + 1]; // Changed to dynamic allocation for
flexibility

// Initialize count array with all zeros.

for (int i = 0; i <= max; ++i) {
*(count + i) = 0;
}

// Store the count of each element

for (int i = 0; i < size; i++) {
(*(count + *(array + i)))++;
}

// Store the cumulative count of each array

for (int i = 1; i <= max; i++) {
*(count + i) += *(count + (i - 1));
}

// Find the index of each element of the original array in

count array, and
// place the elements in the output array
for (int i = size - 1; i >= 0; i--) {
*(output + (*(count + *(array + i))) - 1) = *(array + i);
(*(count + *(array + i)))--;
}

// Copy the sorted elements into the original array in

decreasing order
for (int i = 0; i < size; i++) {

21
 *(array + i) = *(output + size - i - 1);
}
}

int isTriangle(int a, int b, int c) {

return (a + b > c) && (b + c > a) && (c + a > b);
}

// Function to count triangles in an array of numbers

int countTriangles(int *arr, int n) {
int count = 0;

// Iterate through all possible combinations of three

elements
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// Check if the current combination forms a
triangle
if (isTriangle(*(arr + i),*(arr + j), *(arr +
k))) {
count++;
}
}
}
}
}

int main() {
int n;
scanf("%d", &n);
int a_original[50];
int a_modified[50];

21
 int a[50];
for (int i = 0; i < n; i++)
scanf("%d", &a_original[i]);
for (int i = 0; i < n; i++)
a_modified[i] = a_original[i];
for (int i = 0; i < n; i++)
a[i] = a_original[i];
printf("\nTasks:\n\n");
task1(a_modified, n);
printf("Display the original and modified arrays:\n");
task2(a_original, a_modified, n);
printf("Display the original array after merge-sorting:\n");
mergeSort(a_original, 0, n - 1);
print_array(a_original, n);
mergeSort2(a_original, 0, n - 1);
print_array(a_original, n);
printf("Display the modified array after count-sorting:\n");
countingSort(a_modified, n);
print_array(a_modified, n);
countingSort2(a_modified, n);
print_array(a_modified, n);
printf("\n");
printf("Additional task: Find in an array how many triangles
can be formed.\n\n");
int triangleCount = countTriangles(a, n);
printf("Number of triangles that can be formed: %d\n",
triangleCount);
return 0;
}

21
FLOWCHARTS:

21
4)
Screenshots:

5)
Conclusion:

21
In conclusion, the laboratory work focused on implementing and understanding
various sorting algorithms, including shell sort, merge sort, quick sort counting sort
as well as developing our creativity on problem solving.

21