알고리즘에서 '삽입 정렬(Insertion Sort)'이 다른 O(n²) 정렬보다 실전에서 유리한 경우는?

Q: 알고리즘에서 '삽입 정렬(Insertion Sort)'이 다른 O(n²) 정렬보다 실전에서 유리한 경우는?

데이터가 거의 정렬되어 있을 때 최선 O(n)의 시간 복잡도를 가지며, 소규모 데이터에서 오버헤드가 적다 삽입 정렬은 새 요소를 이미 정렬된 부분의 적절한 위치에 삽입하는 방식입니다. 데이터가 거의 정렬된 경우 비교/이동 횟수가 적어 O(n)에 가깝게 동작합니다. 또한 제자리(in-place), 안정(stable) 정렬이며 구현이 단순하여, 소규모 배열에서는 퀵 정렬보다 빠를 수 있습니다.

보통 freeCodeCamp

보기 및 정답

A 데이터가 거의 정렬되어 있을 때 최선 O(n)의 시간 복잡도를 가지며, 소규모 데이터에서 오버헤드가 적다

B 데이터가 완전히 역순으로 정렬되어 있을 때 비교 횟수가 최소화되어 가장 효율적으로 동작한다

C 추가 메모리 사용량이 O(n)이어서 다른 O(n²) 정렬보다 많은 메모리를 사용하지만 속도가 빠르다

D 병렬 처리에 특화된 정렬 알고리즘으로, 멀티코어 환경에서 각 코어에 작업을 분배하여 성능을 극대화하는 방식이다

해설

삽입 정렬은 새 요소를 이미 정렬된 부분의 적절한 위치에 삽입하는 방식입니다. 데이터가 거의 정렬된 경우 비교/이동 횟수가 적어 O(n)에 가깝게 동작합니다. 또한 제자리(in-place), 안정(stable) 정렬이며 구현이 단순하여, 소규모 배열에서는 퀵 정렬보다 빠를 수 있습니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

로그인

추가 정보 입력

회원가입

비밀번호 찾기

알고리즘에서 '삽입 정렬(Insertion Sort)'이 다른 O(n²) 정렬보다 실전에서 유리한 경우는?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

모두를 위한 진짜 쎈 바이브코딩