| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 6192 | 3952 | 3707 | 64.695% |
It is common to compare sorting algorithms based on their asymptotic speeds. Some slower algorithms like selection sort take O(N2) time to sort N items, while comparison-based sorts like merge sort can go no faster than O(N log(N)) time, under reasonable assumptions. Bucket sort, which is not a comparison-based sort, can sort in O(N) time. This is because bucket sort assumes that the range of possible values is small relative to N. In general, the speed of a sorting algorithm depends on the assumptions it can make about the data it is sorting.
One sorting algorithm that is often overlooked, despite its speed, is The Fastest Sorting Algorithm In The World. It sorts in O(1), or constant, time. Of course, the algorithm assumes that the input is an array that is already in fast-access memory and that the input is already sorted. For this problem, implement The Fastest Sorting Algorithm In The World.
The input file contains multiple test cases, each of which describes an array to sort. Each array description starts with an integer 0 < N ≤ 100. N is followed by the N integers to sort, which will be given in non-decreasing order. All integers to sort are in the range of 0 to 100000. The last test case is followed by a line containing a single zero.
For each test case, print the case number (beginning with 1) followed by the text Sorting... done!
5 21 44 48 48 64 6 8 19 22 49 53 62 8 5 9 14 17 24 25 27 61 4 13 21 28 35 5 31 38 44 49 60 0
Case 1: Sorting... done! Case 2: Sorting... done! Case 3: Sorting... done! Case 4: Sorting... done! Case 5: Sorting... done!