Solidity로 배열의 요소를 오름차순으로 정렬하기 위해 가장 효율적 방법으로 삽입 정렬(Insertion Sort) 알고리즘을 사용하는 것입니다.
정렬의 회수가 많을 수록 사용되는 Gas가 많이 측정되지만, 회수가 적으면 적을수록 상당히 합리적인 가스가 소모되기에, 효율적으로 활용되는 Solidity 개발 방법중 하나입니다.
삽입 정렬(Insertion Sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나로, 데이터를 정렬된 상태로 유지하면서 새로운 요소를 적절한 위치에 삽입하는 방식으로 동작합니다. 특히, 데이터가 거의 정렬된 상태일 때 성능이 뛰어나며, 최선의 경우 시간 복잡도는 O(n)입니다.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;
contract RevertInsertSort {
function reverseSort(uint256[5] memory Numbers) public pure returns(uint256[5] memory result){
for(uint8 i = 0; i < Numbers.length; i++) {
uint256 current = Numbers[i];
uint8 j = i;
while (j > 0 && result[j - 1] > current) {
result[j] = result[j - 1]; // 이전 요소를 오른쪽으로 이동
j--;
}
result[j] = current; // 적절한 위치에 요소 삽입
}
}
}
이 스마트 컨트랙트에서는 삽입 정렬을 사용하여 5개의 숫자를 오름차순으로 정렬합니다. Solidity는 저장소 비용이 높기 때문에, 복잡한 정렬 알고리즘을 구현하는 것보다 가벼운 삽입 정렬을 활용하는 것이 적절합니다.
먼저 입력된 numbers 배열을 result에 복사합니다. for 루프를 사용하여 두 번째 요소부터 마지막 요소까지 순차적으로 삽입 정렬을 수행합니다. 각 요소(current)를 while 루프를 사용하여 적절한 위치로 이동시키며, 필요할 경우 왼쪽의 값을 오른쪽으로 이동시킵니다. 정렬이 완료된 배열을 반환합니다.
예를 들어, numbers = [45, 12, 78, 23, 56]가 주어졌을 때 정렬 과정은 다음과 같습니다.
단계현재 배열 상태
| 초기 | [45, 12, 78, 23, 56] |
| 1번째 패스 (12 삽입) | [12, 45, 78, 23, 56] |
| 2번째 패스 (78 유지) | [12, 45, 78, 23, 56] |
| 3번째 패스 (23 삽입) | [12, 23, 45, 78, 56] |
| 4번째 패스 (56 삽입) | [12, 23, 45, 56, 78] |
Solidity에서의 정렬 주의점
- 가스 비용: Solidity에서 for 및 while 루프를 사용할 때 가스 비용이 증가할 수 있습니다. 대량의 데이터를 정렬하는 경우 가스 비용이 비싸지므로, 일반적으로 온체인보다는 오프체인에서 정렬을 수행하는 것이 권장됩니다.
- 메모리 복사: 함수 내에서 memory 배열을 사용할 때 원본 배열을 수정하지 않도록 주의해야 합니다. Solidity에서는 memory 배열이 기본적으로 비어 있기 때문에 초기화가 필요합니다.
결론
위 코드는 Solidity에서 보다 정확하고 효율적인 삽입 정렬을 수행합니다. 특히, 배열 복사 및 올바른 조건문 사용을 통해 오류를 방지하고, 보다 명확한 네이밍을 적용하여 가독성을 향상시켰습니다. 하지만, Solidity에서 정렬을 구현할 때는 가스 비용을 고려해야 하므로, 가능하면 오프체인에서 처리하는 것이 바람직합니다.
댓글