SDA Lab 6

Download as pdf or txt
Download as pdf or txt
You are on page 1of 19

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

Report
Laboratory Work No.6

of the "Data Structures and Algorithms" course

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

Chisinau – 2024

1
The purpose of this laboratory work is to enhance my C programming skills. I'll be
solving problems using procedural programming and implementing solutions using
two parameter passing methods: by value and by address/pointers. Additionally, I'll
develop custom functions for specific tasks and modify problem statements to
introduce additional challenges.

Task number 2: Develop a procedural-style program in C / C++, using its own


written functions. Data processing in your program should be organized according
to a given length of input records based on memory allocation functions.

1. To check if all the elements of the vector are different two by two.

#include <stdio.h>

// Function to check if all elements of the array are different pairwise


int areAllDifferent(int arr[], int size) {
// Loop through each element of the array
for (int i = 0; i < size - 1; i++) {
// Compare the current element with all subsequent elements
for (int j = i + 1; j < size; j++) {
// If two elements are the same, return 0 (indicating not all
elements are different)
if (arr[i] == arr[j]) {
return 0; // Not all elements are different pairwise
}
}
}
// If no two elements are the same, return 1 (indicating all elements are
different)
return 1; // All elements are different pairwise
}

2. If the elements of the array correspond to the requirement formulated in the item
to perform the ascending sorting of the elements for the copy of the original vector,
applying the Bubble Sort method.

2
#include <stdio.h>

// Function to check if all elements of the array are different two by two
int areElementsUnique(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
return 0; // Not unique
}
}
}
return 1; // All unique
}

// Function to perform ascending sorting using Bubble Sort


void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

3. If the elements of the array do not correspond to the requirement formulated in


item I, perform the descending sorting of the elements for the original vector,
applying the Selection Sort method.

#include <stdio.h>
#include <stdbool.h>
void selectionSort(int *arr, int size) {
for (int i = 0; i < size - 1; i++) {
int min_index = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] > arr[min_index]) {
min_index = j;
}
}
// Swap arr[i] and arr[min_index]
int temp = arr[i];
arr[i] = arr[min_index];

3
arr[min_index] = temp;
}
}
bool checkDistinct(int *arr, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] == arr[j]) {
return false;
}
}
}
return true;
}

4. After each manipulation, the results should be displayed as a conclusion (For


example: If there are such elements, the program displays them (the element and its
index, other data stipulated in the condition of the problem); there are no such
elements – the program informs about their absence), etc.

#include <stdio.h>
#include <stdbool.h>

void bubbleSort(int *arr, int size) {


for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (*(arr + j) > *(arr + j + 1)) {
// Swap *(arr + j) and *(arr + j + 1)
int temp = *(arr + j);
*(arr + j) = *(arr + j + 1);
*(arr + j + 1) = temp;
}
}
}
}

void selectionSort(int *arr, int size) {


for (int i = 0; i < size - 1; i++) {
int max_index = i;
for (int j = i + 1; j < size; j++) {
if (*(arr + j) > *(arr + max_index)) {
max_index = j;
}
}

4
// Swap *(arr + i) and *(arr + max_index)
int temp = *(arr + i);
*(arr + i) = *(arr + max_index);
*(arr + max_index) = temp;
}
}

bool checkDistinct(int *arr, int size) {


for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (*(arr + i) == *(arr + j)) {
return false;
}
}
}
return true;
}

int main() {
int size;
printf("Enter the size of the array: ");
scanf("%d", &size);

int arr[size];
printf("Enter %d elements for the array:\n", size);
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

if (checkDistinct(arr, size)) {
bubbleSort(arr, size);
printf("Array sorted in ascending order using Bubble Sort (elements are
distinct):\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
} else {
selectionSort(arr, size);
printf("Array sorted in descending order using Selection Sort (elements
are not distinct):\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

return 0;
}

5
Version 2.

Version A - with the use of the method of transmitting the parametric functions by
value;

#include <stdio.h>
#include <stdbool.h>

// Function to merge two sorted subarrays arr[l..m] and arr[m+1..r]


void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

// create temporary arrays


int L[n1], R[n2];

// Copy data to temporary 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];

// Merge the temporary arrays back into arr[l..r]


i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}

6
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++;
}
}

// Main function of Merge Sort that sorts the array arr[l..r]


void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;

// Sort first and second halves


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

// Merge the sorted halves


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

// Function to perform descending sorting using Insertion Sort


void insertionSortDesc(int arr[], int n) {
int arr_copy[n];
for (int i = 0; i < n; i++) {
arr_copy[i] = arr[i];
}

for (int i = 1; i < n; i++) {


int key = arr_copy[i];
int j = i - 1;
while (j >= 0 && arr_copy[j] < key) {
arr_copy[j + 1] = arr_copy[j];
j = j - 1;
}
arr_copy[j + 1] = key;
}

7
// Copy back the sorted array to the original array
for (int i = 0; i < n; i++) {
arr[i] = arr_copy[i];
}
}

// Function to check if all elements of the array are distinct


bool checkDistinct(int arr[], int size) {
int arr_copy[size];
for (int i = 0; i < size; i++) {
arr_copy[i] = arr[i];
}

for (int i = 0; i < size - 1; i++) {


for (int j = i + 1; j < size; j++) {
if (arr_copy[i] == arr_copy[j]) {
return false;
}
}
}
return true;
}

int main() {
int size;
printf("Enter the size of the array: ");
scanf("%d", &size);

int arr[size];
printf("Enter %d elements for the array:\n", size);
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

int arr_copy[size]; // Copy of the array

// Sort the array in ascending order using Merge Sort


for (int i = 0; i < size; i++) {
arr_copy[i] = arr[i];
}
mergeSort(arr_copy, 0, size - 1);
printf("Array sorted in ascending order using Merge Sort:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr_copy[i]);
}
printf("\n");

// Sort the array in descending order using Insertion Sort

8
insertionSortDesc(arr, size);
printf("Array sorted in descending order using Insertion Sort:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Check if all elements are distinct


if (checkDistinct(arr, size)) {
printf("All elements are distinct.\n");
} else {
printf("Not all elements are distinct.\n");
}

return 0;
}

Version B - with the use of the method of passing parameters of functions by


address/pointers (the formal parameter will be a pointer to the value of the
corresponding object).

#include <stdio.h>
#include <stdbool.h>

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


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

// create temporary arrays


int L[n1], R[n2];

9
// Copy data to temporary 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);

// Merge the temporary arrays back into arr[l..r]


i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
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++;
}
}

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


if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;

// Sort first and second halves


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

// Merge the sorted halves


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

10
void insertionSortDesc(int *arr, int n) {
for (int i = 1; i < n; i++) {
int key = *(arr + i);
int j = i - 1;
while (j >= 0 && *(arr + j) < key) {
*(arr + j + 1) = *(arr + j);
j = j - 1;
}
*(arr + j + 1) = key;
}
}

bool checkDistinct(int *arr, int size) {


for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (*(arr + i) == *(arr + j)) {
return false;
}
}
}
return true;
}

int main() {
int size;
printf("Enter the size of the array: ");
scanf("%d", &size);

int arr[size];
printf("Enter %d elements for the array:\n", size);
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

int arr_copy[size]; // Copy of the array

// Sort the array in ascending order using Merge Sort


for (int i = 0; i < size; i++) {
arr_copy[i] = arr[i];
}
mergeSort(arr_copy, 0, size - 1);
printf("Array sorted in ascending order using Merge Sort:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr_copy[i]);
}
printf("\n");

// Sort the array in descending order using Insertion Sort

11
insertionSortDesc(arr, size);
printf("Array sorted in descending order using Insertion Sort:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");

// Check if all elements are distinct


if (checkDistinct(arr, size)) {
printf("All elements are distinct.\n");
} else {
printf("Not all elements are distinct.\n");
}

return 0;
}

Conclusion: With this lab, I was able to gain a practical understanding of basic
principles while being fully immersed in the complex realm of sorting algorithms
and array manipulation. As I experimented with various tactics, I encountered both
hurdles and moments of frustration along the way. It was a challenging journey to
optimize the code effectively while ensuring its accuracy. I often found myself
tirelessly testing and retesting, facing situations where the code fell short of my
intentions. Yet, through the process of creating thorough test cases and diligently
debugging issues, I not only deepened my comprehension of sorting algorithms
and array manipulation but also developed a newfound appreciation for the
importance of user experience.

12
13
14
15
16
17
18
19

You might also like