Insertion Sort

본 문서는 2021년 12월 28일 에 작성되었습니다.
본 문서는 2022년 1월 2일 에 수정되었습니다.
본 코드는 2022년 3월 28일 에 추가되었습니다.

Insertion Sort 는 규모가 작은 데이터 집합에서 사용하기 좋은 알고리즘입니다.

List, ArrayList, LinkedList 에 대해서 모르신다면
List, ArrayList, LinkedList 를 봐주세요.

Code

Idx 1 인 곳 부터 선택하여 Idx-- 를 진행하며 정렬을 진행합니다.

function insertionSort([length, numbers]) {
    const nums = [...numbers];

    for (let idx = 1; idx < length; idx++) {
        for (let jdx = idx; jdx > 0; jdx--) {
            if (nums[jdx] < nums[jdx-1])
              	[nums[jdx-1], nums[jdx]] = [nums[jdx], nums[jdx-1]]
        }
    }
    return nums;
}

---

Insertion Sort 란?

Insertion Sort (오름차순) 은 다음과 같습니다.

각 열의 원소 A[ j ]를 좌측의 원소 A[ j -1 ]와 비교하여
A[ j ] 가 A [ j -1 ] 보다 작으면 좌측으로 1칸 이동한다.
즉, 더 작은 갓이 좌측에 있도록 정렬한다.

이를 의사코드로 확인해보면 다음과 같습니다.

for j = 2 to A.length
   key=A[j] // A[j] 를 임시 저장소에 저장
   i=j-1  // A[j] 의 비교대상은 한 칸 앞인 A[j-1] 을로 지정
   
   while i>0 AND A[i]>key
      A[i+1] = A[i]
      i=i-1
   A[i+1]=key

---

Java 에서 적용하려면?

Java 에서는 데이터의 집합을 배열(이하 Array)의 형태로 다룬다.
알고리즘에서는 이러한 연속적인 형태를 가진 배열을 List 라고 부른다.

그래서일까?
Java(jdk 1.8~) Collection Framework 에서도 List 라는 인터페이스와 이를 상속받아 만들어진 2개의 클래스가 존재한다.

1. ArrayList 구조 사용 (index + 배열)
2. LinkedList 구조 사용 (Node + 배열)

# ArrayList + Insertion Sort 분석

설명에 앞서,
Insertion Sort 에 대해서 생각을 해보자
Insertion Sort 는 두 값을 비교하여 위치를 바꾸는 정렬이다.

정렬가정에서,
하나의 값을 저장할 임시 공간만 있다면 손쉽게 자리를 찾을 수 있다.

그렇다면 ArrayList 라는 자료 구조를 사용해야할 이유가 있을까?

나는 대상 타입 배열을 사용하는 것이 좋다고 생각하며,
나는 다음과 같은 이유를 제시한다.

1. ArrayList 는 Generics Array 가 아니라 Object Array 를 사용하므로 모든 대상 객체가 업캐스팅이 된다.
2. 단순한 Insertion Sort 만 구현하는데에는 ArrayList 의 메서드를 사용하지 않아도 된다. 사용하지 않는 메서드들이 굳이 생성된다

// 1. ArrayList 
ArrayList<User> userList=new ArrayList<>();

// 2. User[]
User[] users=new User();

# LinkedList + Insertion Sort 분석

그렇다면 삽입 및 삭제에 강한 LinkedList 는 어떨까?

알고리즘에서의 LinkedList 는 Pointer 를 이용한 개념이다.
Java 에서의 LinkedList 는 Pointer 를 대체할 Node 객체 를 이용하여 구현이 가능하다. Pointer 를 사용할 수 없기 때문

Likned List 의 종류에 따라 다르겠지만
단방향 Linked List 의 경우 하나의 Node 는 다음을 포함한다.

1. Node.value 내가 보관할 값
2. Node.next 내 다음 번의 Node 객체 주소값

따라서 Insertion Sort 를 실행하였을 때,
길이 n의 배열 중 k 번째의 값이 k+1 와 교체된다면,
총 세개의 Node.next 를 변경해야 한다.

1. key-1.next
2. key.next
3. key+1.next

이에 따라 이 next 주소값을 저장할 임시 Node 를 만들어야 한다.
만약 양방향 Linked List 이거나 순환성이 추가되어 순환 양방향 Linked List 등으로 이를 구현하려면 더욱 복잡해질 것이다.

따라서 나는 일반 배열을 사용하는 것이 낫다고 생각하며,
그 이유는 다음과 같다.

1. LinkedList 는 Generics Array 가 아니라 Node 클래스 안에 Object 타입으로 값을 찢어서 넣는 개념이므로, 결과적으로 업캐스팅이 된다.
2. 단순한 Insertion Sort 만 구현하는데는 Linked List를 사용하지 않아도 된다. 사용하지 않는 메서드들과 Node 구조가 발생한다.
3. Linked List 의 종류에 따라서 제한되는 것들이 많이 생겨서 오히려 구현 난이도가 올라간다.
   3.1. 단방향 Linked List 의 한 Node 의 이전 Node 를 찾는 과정은 매우 비효율적인 결과를 도출한다.
   3.2. 앙방향 Linked List 는 Node 주소값 저장이 2배가 되어서 공간 낭비가 심해지며, 정렬 시 수정해야 할 Node 주소값이 2배로 늘어난다.
   3.3. 단방향 및 양방향 Linked List 에 순환성을 추가할 경우 배열의 경계 처리에 대한 복잡성이 생겨난다.

// 1.LinkedList
LinkedList<User> userList=new LinkedList<>();

// 2. User[]
User[] user=new User();

---

분석

0. 안정성 : 보장
1. 최적 상황 : O(n)
2. 평균 상황 : O(n^2)
3. 최악 상황 : O(n^2)
4. 공간복잡도 : O(n)

---

Ref

[알고리즘] 삽입정렬이란?
Insertion Sort - The Sorting Algorithm Family Reunion