요약

• 주어진 배열에서 스왑을 통해 정렬(값의 idx로 이동)

동작 구조

(인덱스 = idx, 저장된 값 = value)

1. 배열을 처음부터 순회

2. idx와 맞지 않는 값이 있을 경우(배열[idx] ≠ value), 해당 값을 idx로 하는 곳의 값과 스왑

   

3. 스왑 이후, 다시 2 진행

   

4. value가 배열의 크기를 벗어나는 경우 무시

   

특징/강점

• 공간 복잡도 O(1) → in-place
• 빠른 속도 → 시간 복잡도 O(n)
• 양의 정수에 대한 존재 유무 확인에서 좋은 성능을 보임

한계

• 완벽한 정렬 X → 배열의 크기를 벗어나는 경우 무시 ⇒ 정렬보다는 제자리 찾기 ⇒ value가 들어갈 자리를 다시 순회를 통해 찾는 방식으로 정렬 가능하지만 O(n^2)
• 양의 정수 및 주어진 범위 안에서만 정렬 가능
• 불안정(unstable) 정렬

사용 유형

• 원소의 범위가 제한된 배열에서 (주로 양의 정수)
  • 반복되는 수 찾기
  • 빠진 수 찾기

고찰

• HashMap이나 배열을 통해 값의 존재 여부를 체크하는 방식과 결과적으로 동일한 성능 ⇒ 동작 구조 또한 결과적으로 동일 ⇒ 하지만 추가적인 메모리 사용X