상대적 순위로 변환 최적화 | Optimizing by relative ranking transformation

상대적 순위로 변환 최적화 ❘ Optimizing by relative ranking transformation

 

indexing 함수는 원본 리스트의 값들을 그들의 순위(인덱스)로 변환하는 작업을 수행합니다. 이 함수를 단계별로 상세히 설명하겠습니다:

함수 선언:
t_var *stacks를 매개변수로 받습니다. 이는 리스트와 관련 정보를 포함하는 구조체입니다.

 

변수 선언:
idx_list: 새로운 인덱스 값들을 저장할 정수 배열 포인터
idx: 루프 카운터 및 순위 할당에 사용될 변수
max_idx: find_list_max 함수의 반환값을 저장할 변수

 

메모리 할당:
idx_list에 stacks->list_size 만큼의 정수 배열 공간을 동적 할당합니다.
할당 실패 시 ps_error() 함수를 호출합니다.

 

인덱싱 과정:
idx를 stacks->list_size - 1로 초기화합니다 (가장 큰 순위부터 시작).
루프를 통해 모든 요소에 대해 다음 작업을 수행합니다:
a. find_list_max(stacks)를 호출하여 현재 최대값의 인덱스를 찾습니다.
b. idx_list[max_idx] = idx로 해당 위치에 현재 순위를 할당합니다.
c. idx를 감소시킵니다.

 

메모리 관리:
원본 stacks->list의 메모리를 해제합니다.
stacks->list에 새로 생성한 idx_list를 할당합니다.
이 함수의 주요 목적과 효과:
원본 값들을 그들의 상대적 순위로 변환합니다.
가장 큰 값은 가장 높은 인덱스(n-1)를 받고, 가장 작은 값은 0을 받습니다.
이 과정은 정렬 알고리즘을 단순화하고 최적화하는 데 도움이 됩니다.
결과적으로, 원본 값들 대신 0부터 n-1까지의 고유한 인덱스를 사용하여 정렬 작업을 수행할 수 있게 됩니다.
이 접근 방식은 그리디 알고리즘의 특성을 보여주며, 각 단계에서 최대값을 찾아 적절한 순위를 부여합니다.

 

 

The indexing function converts the values in the original list to their ranks (indices). Here's a detailed explanation of the function step by step:

Function Declaration:
Takes t_var *stacks as a parameter, which is a structure containing the list and related information.

 

Variable Declaration:
idx_list: A pointer to an integer array that will store the new index values.
idx: A variable used as a loop counter and for rank assignment.
max_idx: A variable to store the return value of the find_list_max function.

 

Memory Allocation:
Dynamically allocates space for an integer array of size stacks->list_size to idx_list.
Calls ps_error() function if allocation fails.

 

Indexing Process:
Initializes idx to stacks->list_size - 1 (starting from the highest rank).
Loops through all elements performing the following:
a. Calls find_list_max(stacks) to find the index of the current maximum value.
b. Assigns the current rank to that position with idx_list[max_idx] = idx.
c. Decrements idx.

 

Memory Management:
Frees the memory of the original stacks->list.
Assigns the newly created idx_list to stacks->list.
Main Purpose and Effects of this Function:
Converts original values to their relative ranks.
The largest value receives the highest index (n-1), and the smallest value receives 0.
This process helps simplify and optimize the sorting algorithm.
As a result, sorting operations can be performed using unique indices from 0 to n-1 instead of the original values.
This approach demonstrates characteristics of a greedy algorithm, finding the maximum value at each step and assigning it an appropriate rank.