<jupyter_start><jupyter_text>Challenge Notebook  Problem: Implement shell sort.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Code](Code)* [Unit Test](Unit-Test)  Constraints* Is a naive solution sufficient (ie not in-place)?    * Yes* Are duplicates allowed?    * Yes* Can we assume the input is valid?    * No* Can we assume this fits memory?    * Yes  Test Cases* None -> Exception* Empty input -> []* One element -> [element]* Two or more elements  Code<jupyter_code>class ShellSort(object):

    def sort(self, data, gap_type='ciura'):
        # TODO: Implement me
        pass<jupyter_output><empty_output><jupyter_text>Unit Test**The following unit test is expected to fail until you solve the challenge.**<jupyter_code># %load test_quick_sort.py
from nose.tools import assert_equal, assert_raises


class TestShellSort(object):

    def test_shell_sort(self):
        shell_sort = ShellSort()

        print('None input')
        assert_raises(TypeError, shell_sort.sort, None)

        print('Empty input')
        assert_equal(shell_sort.sort([]), [])

        print('One element')
        assert_equal(shell_sort.sort([5]), [5])

        print('Two or more elements')
        data = [5, 1, 7, 2, 6, -3, 5, 7, -1]
        assert_equal(shell_sort.sort(data, "hibbard"), sorted(data))
        print('Success hibbard: test_shell_sort\n')
        
        data = [5, 1, 7, 2, 6, -3, 5, 7, -1]
        assert_equal(shell_sort.sort(data, "ciura"), sorted(data))
        print('Success ciura: test_shell_sort\n')


def main():
    test = TestShellSort()
    test.test_shell_sort()


if __name__ == '__main__':
    main()<jupyter_output>None input
Empty input
One element
Two or more elements
Success hibbard: test_shell_sort

Success ciura: test_shell_sort
{'fraction_non_alphanumeric': 0.1243640474844545, 'fraction_numerical': 0.011305822498586773, 'mean_word_length': 3.5974025974025974, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '400852', 'license': 'Apache-2.0', 'n_tokens_mistral': 588, 'n_tokens_neox': 557, 'n_words': 162, 'path': 'sorting_searching/shell_sort/shell_sort_challenge.ipynb', 'repo_name': 'lvwuyunlifan/interactive-coding-challenges', 'size': '1769'}