972. Сортировка времени

Отсортируйте время согласно заданному критерию.

Вход. Сначала задано число n (1 ≤ n ≤ 100), а затем n моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60).

Выход. Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно).

Пример входа	Пример выхода
4 10 20 30 7 30 00 23 59 59 13 30 30	7 30 0 10 20 30 13 30 30 23 59 59

РЕШЕНИЕ

сортировка

Анализ алгоритма

В задаче следует отсортировать моменты времени по неубыванию.

Реализация алгоритма

Объявим структуру времени Mytime, содержащую поля час, минута, секунда. Объявим массив lst, куда будем заносить заданные времена.

struct MyTime

{

int hour, min, sec;

};

MyTime lst[100];

Функция f является компаратором, которая сортирует время.

int f(MyTime a, MyTime b)

{

Если часы и минуты одинаковы, то сортируем по возрастанию секунд.

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

Если часы одинаковы (минуты уже не одинаковы), то сортируем по возрастанию минут.

if (a.hour == b.hour) return a.min < b.min;

Иначе сортируем по возрастанию часов.

return a.hour < b.hour;

}

Основная часть программы. Читаем входные данные.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

Сортируем время.

sort(lst,lst+n,f);

Выводим время.

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

Реализация алгоритма – динамическое выделение памяти

#include <cstdio>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTtime

{

int hour, min, sec;

MyTtime (int hour = 0, int min = 0, int sec = 0) :

hour (hour), min(min), sec(sec) {};

} *lst;

int f(MyTtime a, MyTtime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

int main(void)

{

scanf("%d",&n);

lst = new MyTtime[n];

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

sort(lst,lst+n,f);

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

delete[] lst;

return 0;

}

Реализация алгоритма – вектор

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTime

{

int hour, min, sec;

};

vector<MyTime> lst;

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

int main(void)

{

scanf("%d",&n);

lst.resize(n);

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

sort(lst.begin(),lst.end(),f);

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

return 0;

}

Реализация алгоритма – встроенный компаратор

#include <cstdio>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTtime

{

int hour, min, sec;

MyTtime (int hour = 0, int min = 0, int sec = 0) :

hour (hour), min(min), sec(sec) {};

int operator< (const MyTtime &a) const

{

if ((hour == a.hour) && (min == a.min)) return sec < a.sec;

if (hour == a.hour) return min < a.min;

return hour < a.hour;

}

} *lst;

int main(void)

{

scanf("%d",&n);

lst = new MyTtime[n];

for(i = 0; i < n; i++)

scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

sort(lst,lst+n);

for(i = 0; i < n; i++)

printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

delete[] lst;

return 0;

}

Реализация алгоритма – swap sort

#include <stdio.h>

int i, j, n, h, m, s;

struct MyTime

{

int hour, min, sec;

};

MyTime lst[100];

int f(MyTime a, MyTime b) // return 1 if a < b

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

void swap(MyTime &a, MyTime &b)

{

MyTime temp = a; a = b; b = temp;

}

int main(void)

{

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

if (!f(lst[i], lst[j])) swap(lst[i], lst[j]);

for (i = 0; i < n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

return 0;

}

Реализация алгоритма – Heap Sort

#include <stdio.h>

#define MAX 1001

int i, n;

struct MyTime

{

int hour, min, sec;

MyTime() {};

MyTime(MyTime &a) : hour(a.hour), min(a.min), sec(a.sec) {};

};

MyTime lst[MAX];

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

int left(int i)

{

return 2 * i;

}

int right(int i)

{

return 2 * i + 1;

}

void swap(MyTime &i, MyTime &j)

{

MyTime temp = i; i = j; j = temp;

}

// max - heap

void heapify(MyTime a[], int i, int n)

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && f(a[i], a[l])) largest = l;

else largest = i;

if (r <= n && f(a[largest], a[r])) largest = r;

if (largest != i)

{

swap(a[i], a[largest]);

heapify(a, largest, n);

}

}

void BuildHeap(MyTime a[], int n)

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n);

}

void HeapSort(MyTime a[], int n)

{

BuildHeap(a, n);

for (int i = n; i >= 2; i--)

{

swap(a[1], a[i]);

heapify(a, 1, i - 1);

}

}

int main(void)

{

scanf("%d", &n);

for (i = 1; i <= n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

HeapSort(lst, n);

for (i = 1; i <= n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

printf("\n");

return 0;

}

Реализация алгоритма – MergeSort

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int i, n, h, m, s;

struct MyTime

{

int hour, min, sec;

MyTime() {};

MyTime(int hour, int min, int sec) :

hour(hour), min(min), sec(sec) {};

};

MyTime lst[100];

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

void merge(MyTime a[], int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright] are merged into a[bleft..cright]

int i, left = bleft, len = cright - bleft + 1;

MyTime *res = new MyTime[len];

for (i = 0; i < len; i++)

{

if ((bleft > bright) || (cleft > cright)) break;

if (f(a[bleft], a[cleft])) res[i] = a[bleft], bleft++;

else res[i] = a[cleft], cleft++;

}

while (bleft <= bright) res[i++] = a[bleft++];

while (cleft <= cright) res[i++] = a[cleft++];

for (i = left; i < left + len; i++) a[i] = res[i - left];

delete[] res;

}

void mergeSort(MyTime a[], int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a, left, middle);

mergeSort(a, middle + 1, right);

merge(a, left, middle, middle + 1, right);

}

int main(void)

{

scanf("%d", &n);

for (i = 1; i <= n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

mergeSort(lst, 1, n);

for (i = 1; i <= n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

return 0;

}

Реализация алгоритма – QuickSort

#include <cstdio>

#include <vector>

using namespace std;

int i, n, h, m, s;

struct MyTime

{

int hour, min, sec;

};

vector<MyTime> lst;

int f(MyTime a, MyTime b)

{

if ((a.hour == b.hour) && (a.min == b.min)) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

void swap(int &i, int &j)

{

int temp = i; i = j; j = temp;

}

int Partition(vector<MyTime> &m, int L, int R)

{

MyTime x = m[L];

int i = L - 1, j = R + 1;

while (1)

{

do j--; while (f(x, m[j]));

do i++; while (f(m[i], x));

if (i < j) swap(m[i], m[j]); else return j;

}

}

void QuickSort(vector<MyTime> &m, int L, int R)

{

int q;

if (L < R)

{

q = Partition(m, L, R);

QuickSort(m, L, q); QuickSort(m, q + 1, R);

}

}

int main(void)

{

scanf("%d", &n);

lst.resize(n);

for (i = 0; i < n; i++)

scanf("%d %d %d", &lst[i].hour, &lst[i].min, &lst[i].sec);

QuickSort(lst, 0, lst.size() - 1);

for (i = 0; i < n; i++)

printf("%d %d %d\n", lst[i].hour, lst[i].min, lst[i].sec);

return 0;

}

Java реализация

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static class MyFun implements Comparator<MyTime>

{

public int compare(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec - b.sec;

if (a.hour == b.hour) return a.min - b.min;

return a.hour - b.hour;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<MyTime> tm = new ArrayList<MyTime>();

for (int i = 0; i < n; i++)

tm.add(new MyTime(con.nextInt(), con.nextInt(), con.nextInt()));

Collections.sort(tm, new MyFun());

for (int i = 0; i < n; i++)

System.out.println(tm.get(i).hour + " " + tm.get(i).min + " " + tm.get(i).sec);

con.close();

}

}

Java реализация – Heap sort

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static boolean f(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

static int left(int i)

{

return 2 * i;

}

static int right(int i)

{

return 2 * i + 1;

}

static void swap(MyTime a[], int i, int j)

{

MyTime temp = a[i]; a[i] = a[j]; a[j] = temp;

}

//max - heap

static void heapify(MyTime a[], int i, int n) // n = size of a heap

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && f(a[i],a[l])) largest = l;

else largest = i;

if (r <= n && f(a[largest],a[r])) largest = r;

if (largest != i)

{

swap(a, i, largest);

heapify(a, largest, n);

}

}

static void BuildHeap(MyTime a[], int n)

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n);

}

static void HeapSort(MyTime a[], int n)

{

BuildHeap(a, n);

for (int i = n; i >= 2; i--)

{

swap(a, 1, i);

heapify(a, 1, i - 1);

}

}

public static void main(String[] args) {

Scanner con = new Scanner(System.in);

int n = con.nextInt();

MyTime[] tm = new MyTime[n+1];

for (int i = 1; i <= n; i++)

tm[i] = new MyTime(con.nextInt(), con.nextInt(), con.nextInt());

HeapSort(tm, n);

for (int i = 1; i <= n; i++)

System.out.println(tm[i].hour + " " + tm[i].min + " " + tm[i].sec);

System.out.println();

con.close();

}

}

Java реализация – MergeSort

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static boolean f(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

static void merge(MyTime a[], int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright] are merged

// into a[bleft..cright]

int i, left = bleft, len = cright - bleft + 1;

MyTime res[] = new MyTime[len];

for (i = 0; i < len; i++)

{

if ((bleft > bright) || (cleft > cright)) break;

if (f(a[bleft],a[cleft]))

{

res[i] = a[bleft];

bleft++;

}

else

{

res[i] = a[cleft];

cleft++;

}

}

while (bleft <= bright) res[i++] = a[bleft++];

while (cleft <= cright) res[i++] = a[cleft++];

for (i = left; i < left + len; i++) a[i] = res[i - left];

}

static void mergeSort(MyTime a[], int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a, left, middle);

mergeSort(a, middle + 1, right);

merge(a, left, middle, middle + 1, right);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

MyTime[] tm = new MyTime[n+1];

for (int i = 1; i <= n; i++)

tm[i] = new MyTime(con.nextInt(), con.nextInt(), con.nextInt());

mergeSort(tm, 1, n);

for (int i = 1; i <= n; i++)

System.out.println(tm[i].hour + " " + tm[i].min + " " + tm[i].sec);

System.out.println();

con.close();

}

}

Java реализация – QuickSort

import java.util.*;

class MyTime

{

int hour;

int min;

int sec;

public MyTime(int hour, int min, int sec)

{

this.hour = hour;

this.min = min;

this.sec = sec;

}

}

public class Main

{

public static boolean f(MyTime a, MyTime b)

{

if (a.hour == b.hour && a.min == b.min) return a.sec < b.sec;

if (a.hour == b.hour) return a.min < b.min;

return a.hour < b.hour;

}

static void swap(MyTime a[], int i, int j)

{

MyTime temp = a[i]; a[i] = a[j]; a[j] = temp;

}

static int Partition(MyTime a[], int L, int R)

{

MyTime x = a[L];

int i = L - 1, j = R + 1;

while (true)

{

do j--; while (f(x,a[j]));

do i++; while (f(a[i],x));

if (i < j) swap(a, i, j); else return j;

}

}

static void QuickSort(MyTime a[], int L, int R)

{

if (L < R)

{

int q = Partition(a, L, R);

QuickSort(a, L, q);

QuickSort(a, q + 1, R);

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

MyTime[] tm = new MyTime[n+1];

for (int i = 1; i <= n; i++)

tm[i] = new MyTime(con.nextInt(), con.nextInt(), con.nextInt());

QuickSort(tm, 1, n);

for (int i = 1; i <= n; i++)

System.out.println(tm[i].hour + " " + tm[i].min + " " + tm[i].sec);

System.out.println();

con.close();

}

}