Program-/Time sort at master · VladislavErshov/Program- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <stdlib.h>
using namespace std;
void bubblesort(int* &A, int l1, int l, int r){
  int* B = new int[r-l];
  int n = 0, n1, n2 = 0;
  for(int i = l; i <= l1; i++){
  	B[n2] = A[i];
  	n2++;
  	n++;
  }
  for(int i = l1+1; i < r; i++){
    n1 = 0;
    while(A[i] < B[n1] && n1 < n)
      n1++;
    for(int j = n; j > n1; j--)
      B[j] = B[j-1];
    B[n1] = A[i];
    n++;
  }
  n = 0;
  for(int i = l; i < r; i++){
    A[i] = B[n];
    n++;
  }
}
void mergesort(int* &A, int size, int l, int r){
  if(size >= r-l){
  	int l1 = l;
  	if(A[l1] < A[l1+1]){
  	  swap(A[l1], A[l1+1]);
  	  l1++;
  	}
  	while(A[l1] > A[l1+1] && l1 < r-1)
  	  l1++;
    bubblesort(A, l1, l, r);
    return;
  }
  mergesort(A, size, l, (r+l)/2);
  mergesort(A, size, (r+l)/2, r);
  int* B = new int[r-l];
  int n1 = l, n2 = (r+l)/2, n3 = 0;
  while(n1 < (r+l)/2 && n2 < r){
  	if(A[n1] > A[n2]){
      B[n3] = A[n1];
  	  n3++;
      n1++;
    }
    else{
      B[n3] = A[n2];
  	  n3++;
      n2++;
    }
  }
  if(n1 >= (r+l)/2)
  	while(n2 < r){
  	  B[n3] = A[n2];
  	  n3++;
      n2++;
    }
  else
    while(n1 < (r+l)/2){
  	  B[n3] = A[n1];
  	  n3++;
      n1++;
    }
  n3 = 0;
  for(int i = l; i < r; i++){
    A[i] = B[n3];
    n3++;
  }
}
int main(){
  int n, size = 8;
  cin >> n;
  int* A = new int[n];
  for(int i = 0; i < n; i++)
    A[i] = rand()%1000;
  if(n <= 64)
    size = n;
  mergesort(A, size, 0, n);
  for(int i = 0; i < n; i++)
    cout << A[i] << " ";
  return 0;
}