The first line gives the number of file names n, followed by n file names, one per line.
Sort the file names in the order people read them (natural order) and print them one per line.
The order of two names a and b is decided by comparing the two names from the start, step by step, as follows. Number chunks can have different lengths, so the current positions in the two names can differ.
If the current characters of both names are digits (0 to 9), each name groups the digits that continue from its position into one number chunk.
Two number chunks are compared by the size of the number without leading zeros, and the smaller one comes first ("9" < "10"; "007" and "7" are equal).
If the numbers are equal, each name continues from the character right after its own chunk.
If at least one of the two characters is not a digit, compare their character codes (ASCII): the smaller comes first, and if they are equal both names move on to the next character.
The codes are 45 for -, 46 for ., 48 to 57 for the digits 0 to 9, 65 to 90 for English uppercase letters, 95 for _, and 97 to 122 for English lowercase letters.
If only one name runs out first, that name comes first.
If no difference is found by the time both names run out together (only leading zeros differ, as in "a01" and "a1"), compare the two whole names character by character from the start by character code; the name whose first differing character has the smaller code comes first. Here too, a name that runs out first comes first ("a0" comes before "a00").
A number chunk can be up to 30 digits long.
Input
1 ≤ n ≤ 1000. Each name has 1 to 30 characters and consists only of English uppercase and lowercase letters, digits, and - . _. The same name may appear more than once
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
There are four traps. First, a plain sort uses character codes, so "file10" comes before "file9" (1 is smaller than 9). You must pass your own compare function: Python sorted(key=cmp_to_key(f)), JS/TS sort(f), Java list.sort(Main::f), C# List.Sort(f), C qsort, C++ std::sort with f(a, b) < 0, Craykon names.Sort(f) (a function returning negative, 0 or positive). Second, turning a number chunk into a number overflows. 30 digits exceed the 19 digits that C strtoll, C++ stoll, Java Long.parseLong and C# long.Parse handle. strtoll stops at LLONG_MAX, so different numbers become equal, while stoll, parseLong and long.Parse throw. JS/TS Number() and Craykon ToNumber() lose precision above 2^53, so different numbers become equal there too. Python int does not overflow. Removing leading zeros and comparing the digit count first, then the strings, never overflows in any language. Third, comparing digit counts without removing leading zeros makes "007" bigger than "10". Fourth, returning 0 when everything matched leaves the order of "a1" and "a01" depending on the input order. Comparing the whole names by character code at the end makes only identical names equal, so the answer is fixed even with sorts that are not stable, like C qsort, C++ std::sort and C# List.Sort. Comparing character codes is Python ord(c), JS/TS charCodeAt, subtracting chars in Java, C#, C and C++, and Craykon Str.Code(c). For whole strings C# must use string.CompareOrdinal; string.Compare follows culture rules, so case and symbols sort differently.
Pythonmain.py · 42 lines
import sysfrom functools import cmp_to_keydef is_digit(c): return "0" <= c <= "9"def digit_end(s, i): while i < len(s) and is_digit(s[i]): i += 1 return idef compare_natural(a, b): i = j = 0 while i < len(a) and j < len(b): if is_digit(a[i]) and is_digit(b[j]): ie, je = digit_end(a, i), digit_end(b, j) # 앞의 0을 떼면 자릿수가 많은 쪽이 큰 수다(수로 바꾸지 않아 넘치지 않는다) x, y = a[i:ie].lstrip("0"), b[j:je].lstrip("0") if len(x) != len(y): return len(x) - len(y) if x != y: return -1 if x < y else 1 i, j = ie, je else: if a[i] != b[j]: return ord(a[i]) - ord(b[j]) i += 1 j += 1 if i < len(a): return 1 # b가 먼저 끝났다 if j < len(b): return -1 # a가 먼저 끝났다 return -1 if a < b else (1 if a > b else 0) # "a01"과 "a1": 글자 코드 순data = sys.stdin.read().split("\n")n = int(data[0])names = data[1:1 + n]print("\n".join(sorted(names, key=cmp_to_key(compare_natural))))
JavaScriptmain.js · 32 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const names = lines.slice(1, 1 + n);const isDigit = (c) => c >= "0" && c <= "9";function compareNatural(a, b) { let i = 0, j = 0; while (i < a.length && j < b.length) { if (isDigit(a[i]) && isDigit(b[j])) { let ie = i, je = j; while (ie < a.length && isDigit(a[ie])) ie++; while (je < b.length && isDigit(b[je])) je++; // Number()로 바꾸면 2^53을 넘는 수에서 정밀도를 잃는다 — 문자열 그대로 비교 const x = a.slice(i, ie).replace(/^0+/, ""); const y = b.slice(j, je).replace(/^0+/, ""); if (x.length !== y.length) return x.length - y.length; if (x !== y) return x < y ? -1 : 1; i = ie; j = je; } else { if (a[i] !== b[j]) return a.charCodeAt(i) - b.charCodeAt(j); i++; j++; } } if (i < a.length) return 1; if (j < b.length) return -1; return a < b ? -1 : a > b ? 1 : 0; // < 는 글자 코드 순(localeCompare 아님)}console.log(names.sort(compareNatural).join("\n"));
TypeScriptmain.ts · 33 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const names: string[] = lines.slice(1, 1 + n);const isDigit = (c: string): boolean => c >= "0" && c <= "9";function compareNatural(a: string, b: string): number { let i = 0, j = 0; while (i < a.length && j < b.length) { if (isDigit(a[i]) && isDigit(b[j])) { let ie = i, je = j; while (ie < a.length && isDigit(a[ie])) ie++; while (je < b.length && isDigit(b[je])) je++; // Number()로 바꾸면 2^53을 넘는 수에서 정밀도를 잃는다 — 문자열 그대로 비교 const x: string = a.slice(i, ie).replace(/^0+/, ""); const y: string = b.slice(j, je).replace(/^0+/, ""); if (x.length !== y.length) return x.length - y.length; if (x !== y) return x < y ? -1 : 1; i = ie; j = je; } else { if (a[i] !== b[j]) return a.charCodeAt(i) - b.charCodeAt(j); i++; j++; } } if (i < a.length) return 1; if (j < b.length) return -1; return a < b ? -1 : a > b ? 1 : 0; // < 는 글자 코드 순(localeCompare 아님)}console.log(names.sort(compareNatural).join("\n"));
JavaMain.java · 52 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { static boolean isDigit(char c) { return c >= '0' && c <= '9'; } static String stripZeros(String s) { int k = 0; while (k < s.length() && s.charAt(k) == '0') k++; return s.substring(k); } static int compareNatural(String a, String b) { int i = 0, j = 0; while (i < a.length() && j < b.length()) { char p = a.charAt(i), q = b.charAt(j); if (isDigit(p) && isDigit(q)) { int ie = i, je = j; while (ie < a.length() && isDigit(a.charAt(ie))) ie++; while (je < b.length() && isDigit(b.charAt(je))) je++; // Long.parseLong은 19자리를 넘으면 예외 — 문자열 그대로 비교 String x = stripZeros(a.substring(i, ie)), y = stripZeros(b.substring(j, je)); if (x.length() != y.length()) return x.length() - y.length(); int c = x.compareTo(y); if (c != 0) return c; i = ie; j = je; } else { if (p != q) return p - q; i++; j++; } } if (i < a.length()) return 1; if (j < b.length()) return -1; return a.compareTo(b); // String.compareTo는 글자 코드 순 } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); List<String> names = new ArrayList<>(); for (int k = 0; k < n; k++) names.add(in.readLine()); names.sort(Main::compareNatural); System.out.println(String.join("\n", names)); }}
C#Main.cs · 47 lines
using System;using System.Collections.Generic;class Program{ static bool IsDigit(char c) => c >= '0' && c <= '9'; static int CompareNatural(string a, string b) { int i = 0, j = 0; while (i < a.Length && j < b.Length) { if (IsDigit(a[i]) && IsDigit(b[j])) { int ie = i, je = j; while (ie < a.Length && IsDigit(a[ie])) ie++; while (je < b.Length && IsDigit(b[je])) je++; // long.Parse는 19자리를 넘으면 OverflowException — 문자열 그대로 비교 string x = a.Substring(i, ie - i).TrimStart('0'); string y = b.Substring(j, je - j).TrimStart('0'); if (x.Length != y.Length) return x.Length - y.Length; int c = string.CompareOrdinal(x, y); if (c != 0) return c; i = ie; j = je; } else { if (a[i] != b[j]) return a[i] - b[j]; i++; j++; } } if (i < a.Length) return 1; if (j < b.Length) return -1; return string.CompareOrdinal(a, b); // string.Compare(a, b)는 문화권 규칙이라 다르다 } static void Main() { int n = int.Parse(Console.ReadLine()); var names = new List<string>(); for (int k = 0; k < n; k++) names.Add(Console.ReadLine()); names.Sort(CompareNatural); // 끝까지 같으면 완전히 같은 문자열이라 안정 정렬이 아니어도 된다 Console.WriteLine(string.Join("\n", names)); }}
C++main.cpp · 44 lines
#include <algorithm>#include <iostream>#include <string>#include <vector>bool isDigit(char c) { return c >= '0' && c <= '9'; }int compareNatural(const std::string& a, const std::string& b) { size_t i = 0, j = 0; while (i < a.size() && j < b.size()) { if (isDigit(a[i]) && isDigit(b[j])) { size_t ie = i, je = j; while (ie < a.size() && isDigit(a[ie])) ie++; while (je < b.size() && isDigit(b[je])) je++; // std::stoll은 19자리를 넘으면 out_of_range — 문자열 그대로 비교 while (i < ie && a[i] == '0') i++; while (j < je && b[j] == '0') j++; std::string x = a.substr(i, ie - i), y = b.substr(j, je - j); if (x.size() != y.size()) return x.size() < y.size() ? -1 : 1; if (x != y) return x < y ? -1 : 1; i = ie; j = je; } else { if (a[i] != b[j]) return (unsigned char)a[i] - (unsigned char)b[j]; i++; j++; } } if (i < a.size()) return 1; if (j < b.size()) return -1; return a.compare(b);}int main() { int n; std::string line; std::getline(std::cin, line); n = std::stoi(line); std::vector<std::string> names(n); for (auto& s : names) std::getline(std::cin, s); std::sort(names.begin(), names.end(), [](const std::string& a, const std::string& b) { return compareNatural(a, b) < 0; }); for (const auto& s : names) std::cout << s << '\n';}
Cmain.c · 52 lines
#include <stdio.h>#include <stdlib.h>#include <string.h>static char names[1000][40];static int isDigit(char c) { return c >= '0' && c <= '9'; }static int compareNatural(const char *a, const char *b) { int i = 0, j = 0; while (a[i] && b[j]) { if (isDigit(a[i]) && isDigit(b[j])) { int ie = i, je = j; while (isDigit(a[ie])) ie++; while (isDigit(b[je])) je++; /* 앞의 0을 건너뛴다. strtoll은 19자리를 넘으면 넘쳐서 쓰지 않는다 */ while (i < ie && a[i] == '0') i++; while (j < je && b[j] == '0') j++; int lx = ie - i, ly = je - j; if (lx != ly) return lx - ly; int c = strncmp(a + i, b + j, lx); if (c != 0) return c; i = ie; j = je; } else { if (a[i] != b[j]) return (unsigned char)a[i] - (unsigned char)b[j]; i++; j++; } } if (a[i]) return 1; if (b[j]) return -1; return strcmp(a, b); /* strcmp는 글자 코드 순 */}static int cmp(const void *p, const void *q) { return compareNatural((const char *)p, (const char *)q);}int main(void) { int n; char line[64]; if (!fgets(line, sizeof line, stdin)) return 0; sscanf(line, "%d", &n); for (int k = 0; k < n; k++) { if (!fgets(names[k], sizeof names[k], stdin)) break; names[k][strcspn(names[k], "\n")] = '\0'; } qsort(names, n, sizeof names[0], cmp); for (int k = 0; k < n; k++) puts(names[k]); return 0;}
Craykonmain.cray · 94 lines
n = Console.ReadLine().ToNumber();names = [];for (k = 0; k < n; k++){ names.Add(Console.ReadLine());}names.Sort(compareNatural);foreach (s in names){ Console.WriteLine(s);}// 숫자 글자인지: 글자 코드 48("0") ~ 57("9")isDigit(ch){ c = Str.Code(ch); return c >= 48 && c <= 57;}// 숫자 덩이에서 앞의 0을 뗀다stripZeros(s){ k = 0; while (k < s.Length && s[k] == "0") { k += 1; } return s.Substring(k);}compareNatural(a, b){ i = 0; j = 0; while (i < a.Length && j < b.Length) { if (isDigit(a[i]) && isDigit(b[j])) { ie = i; je = j; while (ie < a.Length && isDigit(a[ie])) { ie += 1; } while (je < b.Length && isDigit(b[je])) { je += 1; } // 수로변환은 2^53을 넘으면 정밀도를 잃는다 — 문자열 그대로 비교 x = stripZeros(a.Substring(i, ie - i)); y = stripZeros(b.Substring(j, je - j)); if (x.Length != y.Length) { return x.Length - y.Length; } if (x != y) { if (x < y) { return -1; } return 1; } i = ie; j = je; } else { if (a[i] != b[j]) { return Str.Code(a[i]) - Str.Code(b[j]); } i += 1; j += 1; } } if (i < a.Length) { return 1; } if (j < b.Length) { return -1; } if (a < b) { return -1; } if (a > b) { return 1; } return 0;}