비교 계산 알고리즘 용 의사 코드

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이고 경우에 대해, 가시화 될 수 루프 이중을 제 2 루프 :

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보다 크면 i는 1을 얻습니다. j j가 1이됩니다. 모든 0으로 구성된 첫 번째 행 뒤에 두 번째 행이 반복됩니다. 60을 i로 사용하면 35를 현재 j로, 60을 35보다 크고 60을 1로 계산합니다 (집계표). 그런 다음 새로운 j가되기 때문에 60에서 81까지를 비교합니다. 81이 60보다 높기 때문에 81은 탈리표를 얻습니다. 이 작업은 나머지 행이 완료 될 때까지 계속됩니다. 다음 반복에서는 다음 열이 새로운 i가되고 다음 열은 새로운 j가됩니다. 린스하고 모든 열과 행이 끝날 때까지 반복하고 순서대로 놓은 각 요소에 대한 새 색인 값을 갖습니다.