/*
Вариант 4
АТД - СТЕК
СД - Односвязанный список
Объектная облать - Студенты, общие данные
Сортировка слиянием, шейкером
*/

#include <stdio.h>
#include <stdlib.h>
#include "Data_Structure.h"

int unsorted_array[10] = { 2, 5, 1,8,3,4,7,6,9,0 };
int arr[10] = { 2, 5, 1,8,3,4,7,6,9,0 };
int n = 10;

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


void Merge(int arr[], int begin, int end) {
	int mid = begin + (end - begin) / 2;
	int i = begin;
	int j = mid + 1;
	int d[11] = { 0 };
	int k = 0;

	while (i <= mid && j <= end) {
		if (arr[i] <= arr[j]) {
			d[k] = arr[i];
			i++;
		}
		else {
			d[k] = arr[j];
			j++;
		}
		k++;
	}
	while (i <= mid) {
		d[k] = arr[i];
		k++;
		i++;
	}
	while (j <= end) {
		d[k] = arr[j];
		k++;
		j++;
	}
	for (i = 0; i < k; i++) {
		arr[begin + i] = d[i];
	}

}

void Merge_sort(int* arr, int left, int right) {
	int temp = 0;
	if (left < right) {
		if (right - left == 1) {
			if (arr[left] > arr[right]) {
				temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
			}
		}
		else {
			Merge_sort(arr, left, (right - left) / 2);
			Merge_sort(arr, left + (right - left) / 2 + 1, right);
			Merge(arr, left, right);
		}
	}

}


void Shake_sort() {
	int direction = 0;
	int left = arr[0];
	int left_index = 0;
	int right = arr[n];
	int right_index = n;
	for (int _ = 0; _ < n - 1; _++) {
		if (direction == 0) {
			for (int i = left_index; i < right_index - 1; i++) {
				if (arr[i] > arr[i + 1]) {
					int temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
				}
			}
			if (right != arr[right_index]) {
				for (int i = n; i > 0; i--) {
					if (arr[i] == right) {
						right_index = i;
					}
				}
			}
			direction = 1;
		}
		else {
			for (int j = right_index; j > left_index; j--) {
				if (arr[j] < arr[j - 1]) {
					int temp1 = arr[j];
					arr[j] = arr[j - 1];
					arr[j - 1] = temp1;
				}
			}
			if (left != arr[left_index]) {
				for (int i = 0; i < n; i++) {
					if (arr[i] == left) {
						left_index = i;
					}
				}
			}
		}
		direction = 0;
	}

}

void print_list() {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}



struct Node {
	int student_year;
	int student_group;
	struct Node* next;
	

};

struct Node* first = NULL;



void s_addToHead(int year, int group) {
	struct Node* NewNode = (struct Node*)malloc(sizeof(NewNode));
	NewNode->student_year = year;
	NewNode->student_group = group;
	NewNode->next = first;

	first = NewNode;

}

void s_deleteFromHead() {
	struct Node* DelNode = first;
	int val1 = DelNode->student_year;
	int val2 = DelNode->student_group;

	first = first->next;
	printf("****|PI-%d, %d| - Deleted\n", val2, val1);

}

void s_print() {
	struct Node* i = first;
	while (i) {
		printf("|PI-%d, %d|\n", i->student_group, i->student_year);
		i = i->next;
	}


}


int main() {
	s_addToHead(2020, 12);
	s_addToHead(2021, 13);
	s_addToHead(2022, 14);
	s_addToHead(2024, 15);
	s_print();
	printf("------------------------\n");
	s_deleteFromHead();
	s_print();

	print_list();
	Shake_sort();
	//Merge_sort(arr, 0, n - 1);
	print_list();
	//Data_structure newStructure;


	return 0;
}