#include <stdio.h>
#include "windows.h"
#define MaxVertex 6
#define INF 210000000
#define N 7
void bubbleSort(int matrix[], int n) {
int x = 0;
for (int i = 0; i < n - 1; ++i) {
if (x == n - i) return;
x = 0;
for (int j = 1; j < n - i; ++j) {
if (matrix[j - 1] > matrix[j]) {
int tmp = matrix[j];
matrix[j] = matrix[j - 1];
matrix[j - 1] = tmp;
} else x++;
}
}
}
void bubbleSort1(int matrix[], int n) {
for (int i = 0; i < n - 1; ++i) {
int flag = 1;
for (int j = 1; j < n - i; ++j) {
if (matrix[j - 1] > matrix[j]) {
flag = 0;
int tmp = matrix[j];
matrix[j] = matrix[j - 1];
matrix[j - 1] = tmp;
}
}
if (flag) return;
}
}
void insertSort(int arr[], int size) {
for (int i = 1; i < size; ++i) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
} else break;
}
}
}
void insertSort1(int arr[], int size) {
for (int i = 1; i < size; ++i) {
int tmp = arr[i];
for (int j = i; j > 0; j--) {
if (tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {
arr[j] = tmp;
break;
}
}
}
}
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void selectSort(int arr[], int size) {
int left = 0, right = size - 1;
while (left < right) {
int max = left;
int min = right;
for (int j = left; j <= right; ++j) {
if (arr[min] > arr[j]) min = j;
if (arr[max] < arr[j]) max = j;
}
swap(&arr[right], &arr[max]);
if (min == right) min = max;
swap(&arr[left], &arr[min]);
left++;
right--;
}
}
void quickSort(int arr[], int start, int end) {
if (start >= end) return;
int left = start, right = end, pivot = arr[start];
while (left >= right) {
while (arr[right] > pivot && left < right) right--;
arr[left] = arr[right];
while (arr[left] < pivot && left < right) left++;
arr[right] = arr[left];
}
arr[left] = pivot;
quickSort(arr, start, left - 1);
quickSort(arr, left + 1, end);
}
void dualPivotQuickSort(int arr[], int start, int end) {
if (start >= end) return;
if (arr[start] > arr[end]) swap(&arr[start], &arr[end]);
int pivot1 = arr[start], pivot2 = arr[end];
int left = start, mid = start + 1, right = end;
while (mid >= right) {
if (arr[mid] < pivot1) {
swap(&arr[++left], &arr[mid++]);
} else if (arr[mid] <= pivot2) mid++;
else {
while (arr[right] > pivot2 && right > mid) right--;
if (mid >= right) break;
swap(&arr[mid], &arr[right]);
}
}
swap(&pivot1, &arr[left]);
swap(&pivot2, &arr[right]);
dualPivotQuickSort(arr, start, left - 1);
dualPivotQuickSort(arr, left + 1, mid - 1);
dualPivotQuickSort(arr, mid - 1, end);
}
void shellSort(int arr[], int size) {
int delta = size / 2;
while (delta >= 1) {
for (int i = delta; i < size; ++i) {
int tmp = arr[i];
for (int j = i; j > 0; j -= delta) {
if (tmp < arr[j - delta]) {
arr[j] = arr[j - delta];
} else {
arr[j] = tmp;
break;
}
}
}
delta /= 2;
}
}
void shellSort1(int arr[], int size) {
int delta = size / 2;
while (delta >= 1) {
for (int i = delta; i < size; ++i) {
int j = i, tmp = arr[i];
while (j >= delta && arr[j - delta] > tmp) {
arr[j] = arr[j - delta];
j -= delta;
}
arr[j] = tmp;
}
delta /= 2;
}
}
void makeHeap(int *arr, int start, int end) {
int flag = 1;
int paren = end / 2;
while (paren >= 0) {
if (arr[paren * 2 + 1] && arr[paren * 2 + 1] > arr[paren]) {
flag = 0;
swap(&arr[paren], &arr[paren * 2 + 1]);
} else if (arr[paren] < arr[paren * 2]) {
swap(&arr[paren], &arr[paren * 2]);
flag = 0;
}
paren--;
}
if (flag) return;
makeHeap(arr, start, end);
}
void heapSort(int arr[], int size) {
while (size >= 2) {
swap(&arr[0], &arr[size - 1]);
makeHeap(arr, 0, --size);
}
}
void makeHeap1(int* arr, int start, int end) {
while (start * 2 + 1 <= end) {
int child = start * 2 + 1;
if(child + 1 <= end && arr[child] < arr[child + 1])
child++;
if(arr[child] > arr[start])
swap(&arr[child], &arr[start]);
start = child;
}
}
void heapSort1(int arr[], int size) {
for(int i= size/2 - 1; i >= 0; i--)
makeHeap(arr, i, size - 1);
for (int i = size - 1; i > 0; i--) {
swap(&arr[i], &arr[0]);
makeHeap(arr, 0, i - 1);
}
}
int main() {
int matrix[N] = {4, 2, 7, 1, 5, 3, 6};
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
printf("%d ", matrix[i]);
putchar('\n');
}
}