PROBLEM STATEMENT
The Shell Sort, sometimes called the "diminishing increment sort," is an
algorithm that breaks a list of N elements into K segments such that each
element in each segment is exactly K elements apart in the original list, then
sorts each segment. K is then decreased, and the new segments are again
sorted. This process is repeated until the list is in order.
Here is an example list, and the resulting segments, with K = 3:
List: 8 2 3 9 1 4 7 5 0 6
Segment 0: 8 9 7 6
Segment 1: 2 1 5
Segment 2: 3 4 0
Create a class ShellSort that contains the method getSegment, which takes a
list of integers numList, the increment K, and a segment number segNum and
returns an int[] containing all of the integers in segment segNum, in the same
order in which they appear in numList.
DEFINITION
Class: ShellSort
Method: getSegment
Parameters: int[], int, int
Returns: int[]
Method signature (be sure your method is public): int[] getSegment(int[]
numList, int K, int segNum);
NOTES
- Segment number 0 corresponds to the first segment.
- A given segment numbered N will always begin with the element numbered N in
the original list.
- If the number of integers in numList is not evenly divisible by K, not all of
the segments will have an equal number of elements. For example, if numList =
{1, 2, 3, 4}, and K = 3, then the first segment is {1, 4}, the second segment
is {2}, and the third segment is {3}.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- numList contains between 1 and 20 integers, inclusive.
- Each integer in numList is between 1 and 20, inclusive
- K is between 1 and the number of integers in numList, inclusive.
- segNum is between 0 and K-1, inclusive.
EXAMPLES
=========
Example 1
=========
numList = {8, 2, 3, 9, 1, 4, 7, 5, 12, 6}
K = 3
segNum = 0
The method returns {8, 9, 7, 6}
=========
Example 2
=========
numList = {1, 8, 2, 9, 15, 16, 3, 10, 7, 4, 3}
K = 3
segNum = 1
The method returns {8, 15, 10, 3}
=========
Example 3
=========
numList = {9, 11, 19, 20, 1, 5, 9, 8, 7, 3, 5}
K = 2
segNum = 0
The method returns {9, 19, 1, 9, 7, 5}
=========
Example 4
=========
numList = {13, 15, 3}
K = 1
segNum = 0
The method returns {13, 15, 3}
=========
Example 5
=========
numList = {6}
K = 1
segNum = 0
The method returns {6}