![]()
comparator는 comparable과 비교되는 자바의 인터페이스로 제가 이해하기엔 좀 어렵네요. 당장 자바로 알고리즘을 풀이할 것도 아니라서 과감히 패스하겠습니다! Stability 때로는 정렬 기준(key)이 여러 개가 될 수도 있습니다. 예를 들어 이름을 기준으로 정렬한 다음, 2번째 열의 숫자를 기준으로 정렬하고 싶을 수도 있다는 것이죠. 하지만 두 번째 열을 기준으로 정렬하는 순간 이름 기준의 정렬이 깨지는 것을 원하지 않을 수도 있습니다. 즉, 두 번째 정렬을 수행하더라도 기존의 정렬이 유지되길 원하는 경우 어떻게 이를 구현할 수 있을까요? Stability: insertion sort 삽입 정렬은 정렬이 수행되는 매 스텝(i)에서 이전에 정렬된 것들은 건드리지 않습니다. 비교 대상이 더 ..
![]()
Insertion sort demo 모든 값을 왼쪽에서부터 오른쪽으로 살펴보던 선택정렬과 달리, 삽입 정렬은 i의 값은 왼쪽에서 오른쪽으로 이동하지만, j의 값은 오른쪽에서 왼쪽으로 이동합니다. j는 0부터 i-1까지의 값이 되는데, 리스트에서 i 번째 값보다 큰 값이 있다면 교환하는 작업을 반복적으로 수행합니다. Insertion sort inner loop n = len(a) for i in range(n): for j in range(i-1,0,-1): if a[j] < a[j-1]: a[j],a[j-1] = a[j-1],a[j] else: break 삽입 정렬을 파이썬으로 구현한 것은 위와 같습니다. 중간에 더 작은 값을 만나게 되어 정렬이 보장되는 경우 break를 통해 반복문을 탈출합니다. I..
