Сортировка большого списка результатов тестов

Question

У вас есть большой список (скажем, N > 10000) результатов тестов, которые вы хотели бы отсортировать.Баллы за тест составляют от 1 до 100.Какой самый быстрый способ отсортировать список?

Первая мысль.У нас есть привязка O(N log N), но у нас также есть дополнительная информация о величинах в массиве, поэтому я думаю, что мы могли бы сделать лучше.

Вторая мысль:должны ли мы использовать хэш-таблицы, заботимся ли мы о дубликатах?Не могу понять, как использовать хэш-таблицы.

Третья мысль:имеет ли это какое-то отношение к сортировке по основанию?без понятия.

Четвертая мысль:Могли бы мы отсортировать этот список, создав другой список, а затем пройти через исходные частоты подсчета встречающихся элементов?Но нужен ли нам еще один проход, чтобы создать больший отсортированный список, который был бы O(N ^ 2).т.е. слишком большой.

Это очень простой вопрос или очень сложный?

Answer 1

Это очень простой вопрос, если предположить, что все оценки являются целыми числами.

Вот простейший алгоритм, изложенный простыми словами.Мы будем инициировать count, целочисленный массив из 100 нулей.За каждый балл s, мы добавим 1 к count[s].Чтобы получить желаемые отсортированные баллы, мы выведем count[1] 1с, count[2] 2 секунды, ..., и, наконец count[100] 100-е годы.

Такой алгоритм сортировки называется счетной сортировкой.

В случае более чем $N>10000$ результаты тестов, которые находятся в диапазоне от 1 до 100, являются основным способом подсчета сортировки.Временная сложность составляет $O(N)$ а пространственная сложность ограничена некоторой небольшой константой, кратной 100.

Возможно, вы захотите проверить подсчет сортировки для получения дополнительной информации.

Answer 2

Да, используя алгоритмы сортировки, такие как сортировка слиянием, мы можем достичь этого с помощью O (N * logN). Здесь мы можем добиться большего.Здесь очень полезна дополнительная информация, касающаяся границы результатов тестов.

заботимся ли мы о дубликатах ?

если мы имеем дело только с оценками и не заботимся о другой информации, такой как student_name или subject_info, и нам просто нужны оценки в отсортированном формате, вы можете использовать этот алгоритм.

     maintain a int table[101] = {0}   - hash table with key as score
                        //all elements are initialised to 0

    array contains all scores
    for score in array
         table[score] = table[score] +1
         //above in O(N) time and O(1) space.

    sorted_list = {} // initially empty
    for (score= 0; score < 101;i++)
      for(count = 0; count < table[i]; count++)
          sorted_list.add(score)
          //the above runs in O(N) time and O(N) space.

Теперь, если мы заботимся об информации, нравится ли оценка студенту / предмету, к которому она принадлежала, используйте приведенный ниже подход.я предполагаю, что вы сохраните оценку и связанную с ней информацию в структуре c / c ++ или любом объектном формате.

Теперь поддерживайте хэш-таблицу размером 100 (диапазон результатов теста) ключ = оценка значение = список объектов или экземпляров с такой результат (если вы не сортировка списка студентов, список студентов с этим результат )

если вы знакомы с c / c ++, то эта структура данных может быть реализована с использованием массива связанных списков.Здесь используется следующий метод хеширования отдельное хеширование.

функциональность структуры данных выглядит следующим образом DS[оценка] содержит указатель / ссылку на связанный список используя другую хэш-карту для определения хвостов каждого вложенного списка в DS, мы можем вставить новый элемент за O (1) раз.

итак , за один проход от i = 0 до i

после вставки мы можем создать новый список с помощью одного прохода по DS, который мы создали.

алгоритм примерно такой.

пусть массив содержит все объекты с их соответствующими оценками

    for (i = 0; i< n; i++)
      key = array[i].score
      DS[key].insert(array[i]) //the tail part can be used for O(1) insertion.

     //the above loop runs in O(N)

     sorted_list = {} // empty_list
     for(score = 1; score<=100;score++)
       for each (obj in DS[score]) 
          sorted_list.add(obj)

      //the above loop runs in O(N).

     //the N refers to the size of original list here.

этот подход волшебным образом основан на основе очереди, что-то вроде базы 100.Узнайте больше о сортировке по радиусу и подсчете сортировки с реализацией очереди.

из вопроса :- Четвертая мысль:Могли бы мы отсортировать этот список, создав другой список, а затем пройти через исходные частоты подсчета встречающихся элементов?Но понадобится ли нам еще один проход для создания большего отсортированного списка, который был бы O (N ^ 2).т.е. слишком большой."

я думаю , вы ошибочно полагаете , что другой проход изменил бы N на Nˆ2 .если вы не помещаете "другой проход" в цикл, этого не произойдет.

надеюсь, я ответил на все ваши вопросы.