Псевдокод для алгоритма подсчета сравнений

Question

Я работаю над домашним заданием для своего класса алгоритмов, и я ошеломлен тем, как работает этот конкретный алгоритм. Я уже нашел ответ в сети, поэтому я не ищу ответов, просто помогаю работать через код шаг за шагом. Из того, что я могу понять до сих пор, алгоритм принимает массив неопределенной длины и через несколько итераций, сортирует числа, сравнивая отдельный элемент с меньшими элементами в массиве. В конце итераций он присваивает каждому элементу индекс местоположения, который указывает, в каком порядке должны быть упорядочены элементы, чтобы быть в неубывающем порядке. Но я не могу понять, как второй цикл for-do запускает итерацию после завершения первого цикла? Любая помощь будет принята с благодарностью

Вопрос: Рассмотрим алгоритм для задачи сортировки, которая сортирует массив путем подсчета, для каждого из его элементов, число мелких элементов, а затем использует эту информацию, чтобы поместить элемент его подходящее положение в сортированном массиве. Сортировка следующий список номеров, (60, 35, 81, 98, 14, 47):

Algorithm ComparisonCountingSort(A[0..n − 1], S[0..n − 1]) 
//Sorts an array by comparison counting 
//Input: Array A[0..n − 1] of orderable values 
//Output: Array S[0..n − 1] of A’s elements sorted in nondecreasing order 

for i ← 0 to n − 1 do 
    Count[i] ← 0 

for i ← 0 to n − 2 do 
    for j ← i + 1 to n − 1 do 
      if A[i] < A[j] 
       Count[j] ← Count[j] + 1 
      else 
       Count[i] ← Count[i] + 1 

for i ← 0 to n − 1 do 
    S[Count[i]] ← A[i] 

return S 

Answer 1

Суть этого алгоритма сортировки является осознание того, что, если число x в массиве имеет ровно n элементы массив, который меньше, то в отсортированном массиве он должен быть n '-й элемент (в массиве с нулевой индексацией).

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

Второй цикл, который является двойной цикл можно визуализировать следующим образом, для случая, когда длина N составляет 4:

1st outer loop | i -> [0] 
       | j -> [1] [2] [3] 

2nd outer loop | i -> [1] 
       | j -> [2] [3] 

3rd outer loop | i -> [2] 
       | j -> [3] 

Здесь i и j ваши итераторы цикла и значения в скобках являются значениями индекса, который они принимают. Теперь вы можете ясно видеть, что при этой конструкции каждая пара сравнивается один раз

Answer 2

спасибо за любую помощь, которая была предоставлена, но я смог разобраться с ней после некоторого времени. С точки зрения мирянина вы начинаете с первого столбца, который является текущим i, и сравнивайте его с каждым последующим столбцом (который был бы j в сравнении), а если i больше j, тогда я получаю 1. Если j выше, j получает 1. После первой строки, которая состоит из всех нулей, вторая строка итерируется. Используя 60 как i, вы сравниваете его с 35, который является текущим j, так как 60 больше 35, 60 получает 1 (отметьте отметку, если хотите). Затем вы сравниваете 60 - 81, так как это становится новым j. Поскольку 81 больше 60, 81 получает отметку о счете. Это продолжается до тех пор, пока остальная часть строки не будет завершена. В следующей итерации следующий столбец становится новым i, и следующее станет новым j один за другим. Промойте и повторите до тех пор, пока все столбцы и строки не будут завершены, и у вас есть новое значение индекса для каждого элемента, который вы затем упорядочиваете.