Sorting time (Editorial)

Sort the moments of time in non-decreasing order.

Algorithm implementation

Define a structure Mytime containing the following fields: hour, minute, and second. Create an array $l s t$ to store the given moments of time.

struct MyTime
{
  int hour, min, sec;
};

MyTime lst[100];

The function f is a comparator that determines the sorting order of moments of time.

int f(MyTime a, MyTime b)
{

If the values of hours and minutes are the same, the sorting is done in ascending order of seconds.

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

If the values of hours are the same (but the minutes differ), the sorting is done in ascending order of minutes.

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

In all other cases, the sorting is done in ascending order of hours.

  return a.hour < b.hour;
}

The main part of the problem. Read the input data.

scanf("%d",&n);
for (i = 0; i < n; i++)
  scanf("%d %d %d",&lst[i].hour,&lst[i].min,&lst[i].sec);

Sort the moments of time.

sort(lst, lst + n, f);

Print the moments of time.

for (i = 0; i < n; i++)
  printf("%d %d %d\n",lst[i].hour,lst[i].min,lst[i].sec);

Algorithm implementation — 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;
}

C++

Algorithm implementation — 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;
}

C++

Algorithm implementation — 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;
}

C++

Algorithm implementation — 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;
}

C++

Java implementation

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

Java implementation — 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

Java implementation — 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

Java implementation — 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();
  }
}

Java

Python implementation

Read the number of moments of time $n$ .

n = int(input())

Let's represent a moment of time as a tuple $(h, m, s)$ (h, m, s). The list $t im e$ will contain all the input moments of time.

time = []

Read the input moments of time and store them in the list $t im e$ .

for _ in range(n):
  h, m, s = map(int, input().split())
  time.append((h, m, s))

Sort the moments of time according to the given criterion.

time.sort()

Print the answer.

for t in time:
  print(*t)