Kattis/sortofsorting.cpp at master · wgzesg/Kattis · 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
#include <iostream>

using namespace std;
void mergeSort(string name[], int start, int end, int mid);
void merge(string name[], int start, int end, int mid);
void printList(string name[], int no_of_names);


int main(void){
    int no_of_names = 0;
    cin >> no_of_names;
    while(no_of_names != 0){
        string name[no_of_names];
        for(int i = 0; i < no_of_names; i++){
            cin >> name[i];
        }
        mergeSort(name, 0, no_of_names, no_of_names / 2);
        printList(name, no_of_names);
        cin >> no_of_names;
    }
}

void mergeSort(string name[], int start, int end, int mid){
    if(end - start <= 1){
        return;
    }
    else{
        mergeSort(name, start, mid, (start + mid) / 2);
        mergeSort(name, mid, end, (end + mid) / 2);
        merge(name, start, end, mid);
    }
}

void merge(string name[], int start, int end, int mid){
    int left = start;
    int right = mid;
    string temp[end - start];
    int tempidx = 0;
    while(left < mid && right < end){
        if(name[left][0] < name[right][0]){
            temp[tempidx++] = name[left++];
        }
        else if(name[left][0] > name[right][0]){
            temp[tempidx++] = name[right++];
        }
        else{
            if(name[left][1] <= name[right][1]){
                temp[tempidx++] = name[left++];
            }
            else if(name[left][1] > name[right][1]){
                temp[tempidx++] = name[right++];
            }
        }
    }
    while(left < mid)
        temp[tempidx++] = name[left++];
    while(right < end)
        temp[tempidx++] = name[right++];
    for (int k = start; k < end; k++)
        name[k] = temp[k - start];
}

void printList(string name[], int no_of_names){
    for(int i = 0; i < no_of_names; i ++){
        cout << name[i] << endl;
    }
}