인프런 커뮤니티 질문&답변
작성한 질문수
정렬 질문
해결된 질문
작성
·
81
·
수정됨
0
안녕하세요! 정렬 -2 (3-3)과 관련해서 아래처럼 sort를 이용하면 안되는건가요? for문 두번을 이용해서 설명해주신 방법대로 해야하는 것이 맞는지 궁금하고, 아래 방법대로 하면 O(N) 연산량이 되는 것인지도 궁금합니다! 감사합니다.
input = [4,6,2,9,1]
###내가 한것###
def insertion_sort(array):
n = len(array)
for i in range(1,n):
if array[i]<array[i-1]:
a = array[:i+1]
a.sort()
array[:i+1]=a
return array
insertion_sort(input)
답변 1
0
안녕하세요 snoapple3님!! 좋은 질문 감사합니다 ㅎㅎ
연휴에도 공부하시다니 넘 멋집니다!!! 😍
제안하신 방법은 굉장히 창의적인 접근법입니다! 매 단계에서 현재까지의 부분 배열을 정렬하는 아이디어를 사용하셨네요. 하지만 몇 가지 고려할 점이 있습니다.
def insertion_sort(array):
n = len(array)
for i in range(1,n):
if array[i]<array[i-1]:
a = array[:i+1]
a.sort() # Python의 내장 정렬
array[:i+1]=a
return array이 코드의 시간 복잡도는 O(N^2log N)입니다. 왜냐하면:
외부 루프는 O(N) 번 실행됩니다
내부에서 Python의 내장
.sort()는 O(KlogK) 시간이 걸립니다 (여기서 K는 i+1이므로 최대 N)최악의 경우(역순 정렬된 배열) 매 단계마다
.sort()가 호출되므로 O(N^2logN)이 됩니다
표준 삽입 정렬은 O(N^2)의 시간 복잡도를 가집니다.
일반적인 삽입 정렬의 경우 현재 원소를 이미 정렬된 부분에 적절한 위치로 삽입합니다 정렬된 부분 배열을 순회하며 비교하는 과정에서 최적화가 가능합니다 (더 작은 원소를 만나면 중단되기 때문입니다.)
그런데 제안하신 방법은 매 단계마다 전체 부분 배열을 재정렬합니다 따라서 이미 정렬되어 있음에도 모든 원소를 보고 정렬하는 과정을 거치기 때문에 더 많은 시간 복잡도를 사용하게 됩니다. 따라서 성능적으로 기존 삽입 정렬이 더 효율적입니다(O(N^2) vs O(N^2log N)).
제안하신 방법도 분명 동작하지만, 아무래도 python 의 내장 sort 함수의 시간 복잡도를 놓치셨던 것 같습니다! 새로운 방식을 시도해보고, 풀이해보는 점 너무 너무 훌륭하십니다! 언제든 새로운 방법으로 풀이해보시고, 질문해주시면 좋을 것 같습니다. 오늘 하루도 즐거운 하루 되시길 바랍니다!!
감사합니다!!