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.3
of the "Data Structures and Algorithms" course
Verificat:
Burlacu Natalia, PhD, associate professor
Department of Software and Automation Engineering,
Facultatea FCIM, UTM
Chisinau – 2023
1
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.
1)
2
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)
3
4
3)
Task1:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
int start_pos;
int end_pos;
int col;
}sub_arrays;
void print_norm(int* arr,int end){
printf("\n[");
for (int i = 0; i<end; i++){
printf("%d", arr[i]);
if(i != end-1){
printf(",");
}
}
printf("]\n");
}
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int** arr, int n, int i)
{
5
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && *(arr[left]) > *(arr[largest]))
largest = left;
if (right < n && *(arr[right]) > *(arr[largest]))
largest = right;
if (largest != i) {
swap(&(*arr[i]), &(*arr[largest]));
heapify(arr, n, largest);
}
}
void heapSort(int** arr, int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(&(*arr[0]), &(*arr[i]));
heapify(arr, i, 0);
}
}
int summing(int* arr, int n){
int sum = 0;
for (int i = 0; i<n && arr[i] != -1;i++){
sum+=arr[i];
}
return sum;
}
int shortest_pos(int* arr, int n, sub_arrays* sub){
int pos = 0;
int min = *arr;
for (int i = 0; i<n && arr[i] != -1;i++){
6
if(min>arr[i]){
min = arr[i];
pos = i;
}
}
return sub[pos].col;
}
int longest_pos(int* arr, int n){
int pos;
int max = *arr;
for (int i = 0; i<n;i++){
if(max<arr[i]){
max = arr[i];
pos = i;
}
}
return pos;
}
int longest_shortest_pos(int* arr, int n,int pos,sub_arrays* sub){
int max = arr[pos];
// print_norm(arr,n);
for (int i = 0; i < n;i++){
if(max<arr[i] && sub[i].col == pos){
max = arr[i];
pos = i;
}
}
return pos;
}
void print(int** arr,int end){
printf("\n[");
for (int i = 0; i<end; i++){
printf("%d", *(arr[i]));
if(i != end-1){
printf(",");
7
}
}
printf("]\n");
}
void counting_sort(int** arr ,int end){
int max = **arr;
int min = **arr;
// print(arr,end);
for (int i = 0; i < end; i++) {
if (*arr[i] > max)
max = *arr[i];
if (*arr[i] < min)
min = *arr[i];
}
for (int i = 0; i < end; ++i) {
*arr[i] = *arr[i] + abs(min);
}
int* arr_mask = (int*)malloc((max + 1 + abs(min)) * sizeof(int));
int* output = (int*)malloc(end * sizeof(int*));
for (int i = 0; i <= max + abs(min); ++i) {
arr_mask[i] = 0;
}
for (int i = 0; i < end; i++) {
arr_mask[*arr[i]+abs(min)]++;
}
// print_norm(arr_mask,max+abs(min));
for (int i = 1; i <= max + abs(min); i++) {
arr_mask[i] += arr_mask[i - 1];
}
// print_norm(arr_mask,max+abs(min));
for (int i = end-1; i >= 0; i--) {
output[arr_mask[*arr[i]] - 1] = *arr[i];
arr_mask[*arr[i]]--;
}
8
int k = 0;
for (int i = end-1; i >= 0; i--) {
*arr[k] = output[i]-abs(min);
k++;
}
free(arr_mask);
free(output);
}
int** create_2d(int n,int m){
int** arr = (int**)malloc(n*sizeof(int*));
for(int i = 0; i < n; i++){
arr[i] = (int*)malloc(m*sizeof(int));
}
return arr;
}
void fill_2d(int** arr,int n,int m){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
printf("Give the [%d][%d] element value: ",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("\n");
}
void print_2d(int** arr,int n,int m){
for(int i = 0; i < n; i++){
printf("%d [",i);
for(int j = 0; j < m; j++){
printf("%d", arr[i][j]);
if(j != m-1){
printf(",");
}
}
printf("]\n");
}
9
}
void sub_arraying(int** arr,int n,int m, int s){
int counter = 0;
sub_arrays* subArrays = (sub_arrays*)malloc(n*m*sizeof(sub_arrays));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int sum = 0;
for(int k = j; k < n;k++){
sum+=arr[k][i];
if (sum == s){
subArrays[counter].start_pos=j;
subArrays[counter].end_pos=k;
subArrays[counter].col = i;
counter++;
}
}
}
}
int* all_lengths = (int*)malloc((counter+1)*sizeof(int));
for(int i = 0; i < counter; i++){
all_lengths[i] = subArrays[i].end_pos-subArrays[i].start_pos+1;
}
int sum = summing(all_lengths,counter);
printf("\nThe number of subarrays found: %d\n",sum);
for(int i = 0; i < counter; i++){
printf("\nSubarray [%d] from [%d][%d] to [%d][%d]: [",i+1,subArrays[i].start_pos,subArrays[i].col,subAr-
rays[i].end_pos,subArrays[i].col);
for(int j = subArrays[i].start_pos; j<=subArrays[i].end_pos;j++){
printf("%d",arr[j][subArrays[i].col]);
if(j != subArrays[i].end_pos){
printf(",");
}
}
printf("]\n");
}
int* longest = (int*)malloc(n*sizeof(int));
for(int i = 0; i < n; i++){
10
longest[i] = -1;
}
int* save_i = (int*)malloc(n*sizeof(int));
for(int i = 0; i < n; i++){
save_i[i] = 0;
}
for(int i = 0;i < counter;i++){
// printf("%d\n",i);
if (longest[subArrays[i].col]<subArrays[i].end_pos-subArrays[i].start_pos){
longest[subArrays[i].col] = subArrays[i].end_pos-subArrays[i].start_pos;
save_i[subArrays[i].col] = i;
}
}
// print_norm(longest,n);
for(int i = 0; i < counter; i++){
all_lengths[i] = subArrays[i].end_pos-subArrays[i].start_pos+1;
}
int longestPos = longest_pos(longest,n);
int iPos = save_i[longestPos];
int shortestPos = longest_shortest_pos(longest,n,shortest_pos(all_lengths,counter,subArrays),subArrays);
int jPos = save_i[shortestPos];
if (sum % 2 == 1 ){
int** array = (int**)malloc(n*m*sizeof(int));
int k = 0;
for(int j = subArrays[iPos].start_pos; j<=subArrays[iPos].end_pos;j++){
array[k] = &arr[j][subArrays[iPos].col];
k++;
// printf("\n %d ",*(&arr[j][subArrays[save_i[i]].col]));
}
counting_sort(array,longest[longestPos]+1);
}else
{
printf("\nNothing to say(for odd)\n");
}
if (sum % 2 == 0){
int** array = (int**)malloc(n*m*sizeof(int));
int k = 0;
for(int j = subArrays[jPos].start_pos; j<=subArrays[jPos].end_pos;j++){
array[k] = &arr[j][subArrays[jPos].col];
k++;
11
}
heapSort(array,longest[shortestPos]+1);
}else
{
printf("\nNothing to say(for even)\n");
}
if (counter == 0){
printf("\nThere is no such array\n");
}
free(save_i);
free(longest);
free(subArrays);
}
int main(){
int row,col,s;
printf("Give the number of rows: ");
scanf("%d",&row);
printf("Give the number of cols: ");
scanf("%d",&col);
printf("\n");
printf("Give the number S: ");
scanf("%d",&s);
int** arr_2d = create_2d(row,col);
fill_2d(arr_2d,row,col);
print_2d(arr_2d,row,col);
sub_arraying(arr_2d,row,col,s);
print_2d(arr_2d,row,col);
for(int i = 0; i < row; i++){
free(arr_2d[i]);
}
if (arr_2d!=NULL) free(arr_2d);
}
12
Task2:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
int start_pos;
int end_pos;
int col;
int bounter;
}sub_arrays;
sub_arrays* sub;
void print_norm(int* arr,int end){
printf("\n[");
for (int i = 0; i<end; i++){
printf("%d", arr[i]);
if(i != end-1){
printf(",");
}
}
printf("]\n");
}
void print(int** arr,int end){
printf("\n[");
for (int i = 0; i<end; i++){
printf("%d", *(arr[i]));
if(i != end-1){
printf(",");
}
}
printf("]\n");
13
}
void counting_sort(int** arr ,int end, int place){
int max = arr[0][0];
// print(arr,end);
for (int i = 0; i < end; i++) {
if ((*arr[i]/place)%10 > max)
max = *arr[i];
}
int* arr_mask = (int*)malloc((max + 1) * sizeof(int));
int* output = (int*)malloc(end * sizeof(int*));
for (int i = 0; i <= max; ++i) {
arr_mask[i] = 0;
}
for (int i = 0; i < end; i++) {
arr_mask[(*arr[i]/place)%10]++;
}
for (int i = 1; i <= max; i++) {
arr_mask[i] += arr_mask[i - 1];
}
for (int i = end-1; i >= 0; i--) {
output[arr_mask[(*arr[i]/place)%10] - 1] = *arr[i];
arr_mask[*arr[i]/place]--;
}
// print_norm(output,end);
for (int i = end-1; i >= 0; i--) {
*arr[i] = output[i];
}
free(arr_mask);
free(output);
}
14
int summing(int* arr, int n){
int sum = 0;
for (int i = 0; i<n && arr[i] != -1;i++){
sum+=arr[i];
}
return sum;
}
int shortest_pos(int* arr, int n){
int pos = 0;
int min = *arr;
for (int i = 0; i<n && arr[i] != -1;i++){
if(min>arr[i]){
min = arr[i];
pos = i;
}
}
return sub[pos].col;
}
int longest_pos(int* arr, int n){
int pos = 0;
int max = *arr;
// print_norm(arr,n);
for (int i = 0; i<n;i++){
if(max<arr[i]){
max = arr[i];
pos = i;
}
}
return pos;
}
int longest_shortest_pos(int* arr, int n,int pos){
int max = arr[pos];
// print_norm(arr,n);
for (int i = 0; i < n;i++){
if(max<arr[i] && sub[i].col == pos){
15
max = arr[i];
pos = i;
}
}
return pos;
}
int** create_2d(int n,int m){
int** arr = (int**)malloc(n*sizeof(int*));
for(int i = 0; i < n; i++){
arr[i] = (int*)malloc(m*sizeof(int));
}
return arr;
}
void fill_2d(int** arr,int n,int m){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
printf("Give the [%d][%d] element value: ",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("\n");
}
void print_2d(int** arr,int n,int m){
for(int i = 0; i < n; i++){
printf("%d [",i);
for(int j = 0; j < m; j++){
printf("%d", arr[i][j]);
if(j != m-1){
printf(",");
}
}
printf("]\n");
}
}
16
int counting_sub_array(int** arr,int n, int m, int s, int i, int bounter){
if(i<n){
int counter = 0;
int** arr_mask = (int**)malloc(n*m*sizeof(int));
int v = 0;
for(int j = 0; j<=n;j++){
arr_mask[v] = &arr[j][i];
v++;
}
for(int j = 0; j < n; j++){
int sum = 0;
int d = 0;
for(int k = j; k < n;k++){
sum+=*(arr_mask[k]);
if (sum == s){
counter++;
sub[bounter].col = i;
sub[bounter].end_pos = k;
sub[bounter].start_pos = j;
bounter++;
}
}
}
return counter + counting_sub_array(arr, n, m, s, i + 1, bounter);
}
return 0;
}
void swap(int* x, int* y){
int temp = *x;
*x = *y;
*y = temp;
}
int get_next_gap(int gap)
{
// Shrink gap by Shrink factor
17
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
int get_max(int** array, int n) {
int max = *array[0];
for (int i = 1; i < n; i++)
if (*array[i] > max)
max = *array[i];
return max;
}
int get_min(int** array, int n) {
int min = *array[0];
for (int i = 1; i < n; i++)
if (*array[i] < min)
min = *array[i];
return min;
}
void comb_sort(int** a, int n)
{
int gap = n;
int swapped = 1;
while (gap != 1 || swapped == 1)
{
gap = get_next_gap(gap);
swapped = 0;
for (int i=0; i<n-gap; i++)
{
if (*a[i] > *a[i+gap])
{
swap(a[i], a[i+gap]);
// print(a,n);
swapped = 1;
18
}
}
}
}
void radixsort(int** array, int size) {
int min = get_min(array, size);
for (int i = 0; i < size; i++)
*array[i]+=abs(min);
int max = get_max(array, size);
for (int place = 1; max / place > 0; place *= 10)
counting_sort(array, size, place);
for (int i = 0; i < size; i++)
*array[i]-=abs(min);
}
void preparing_for_sorting(int** arr,int n, int m,int sub_array_number){
int* all_lengths = (int*)malloc((sub_array_number+1)*sizeof(int));
for(int i = 0; i < sub_array_number; i++){
all_lengths[i] = sub[i].end_pos-sub[i].start_pos+1;
}
int sum = summing(all_lengths,sub_array_number);
printf("\nTotal number of elements in subarrays: %d\n", sum);
for(int i = 0; i < sub_array_number; i++){
printf("\nSubarray [%d] from [%d][%d] to [%d][%d]:
[",i+1,sub[i].start_pos,sub[i].col,sub[i].end_pos,sub[i].col);
for(int j = sub[i].start_pos; j<=sub[i].end_pos;j++){
printf("%d",arr[j][sub[i].col]);
if(j != sub[i].end_pos){
printf(",");
}
}
printf("]\n");
}
int* longest = (int*)malloc(n*sizeof(int));
for(int i = 0; i < n; i++){
longest[i] = -1;
}
19
int* save_i = (int*)malloc(n*sizeof(int));
for(int i = 0; i < n; i++){
save_i[i] = 0;
}
for(int i = 0;i < sub_array_number;i++){
if (longest[sub[i].col]<sub[i].end_pos-sub[i].start_pos){
longest[sub[i].col] = sub[i].end_pos-sub[i].start_pos;
save_i[sub[i].col] = i;
}
}
int longestPos = longest_pos(longest,n);
int iPos = save_i[longestPos];
int shortestPos = longest_shortest_pos(longest,n,shortest_pos(all_lengths,sub_array_number));
int jPos = save_i[shortestPos];
// printf("Jpos: %d \n", jPos);
if (sum % 2 == 1 ){
int** array = (int**)malloc(n*m*sizeof(int));
int k = 0;
for(int j = sub[iPos].start_pos; j<=sub[iPos].end_pos;j++){
array[k] = &arr[j][sub[iPos].col];
k++;
}
// print(array,k);
comb_sort(array,longest[longestPos]+1);
}else
{
printf("\nNothing to say (not odd)\n");
}
if (sum % 2 == 0){
int** array = (int**)malloc(n*m*sizeof(int));
int k = 0;
for(int j = sub[jPos].start_pos; j<=sub[jPos].end_pos;j++){
array[k] = &arr[j][sub[jPos].col];
k++;
}
// print(array,k);
radixsort(array,longest[shortestPos]+1);
}else
{
20
printf("\nNothing to say (not even)\n");
}
if (sub_array_number == 0){
printf("\nThere is no such array\n");
}
free(save_i);
free(longest);
free(sub);
}
int main(){
int row,col,s;
printf("Give the number of rows: ");
scanf("%d",&row);
printf("Give the number of cols: ");
scanf("%d",&col);
printf("\n");
printf("Give the number S: ");
scanf("%d",&s);
sub = (sub_arrays*)malloc(row*col*sizeof(sub_arrays));
int** arr_2d = create_2d(row,col);
fill_2d(arr_2d,row,col);
print_2d(arr_2d,row,col);
int sub_array_number = counting_sub_array(arr_2d,row,col,s,0,0);
preparing_for_sorting(arr_2d,row,col,sub_array_number);
print_2d(arr_2d,row,col);
for(int i = 0; i < row; i++){
free(arr_2d[i]);
}
if (arr_2d!=NULL) free(arr_2d);
}
4)
Screenshots:
Task1:
21
Task2:
22
5)
Conclusion:
Worked a lot of time on the algorithm to work correctly without bugs and
implemented sorting algorithms like heap sort and counting sort.
23
