오늘은 선택정렬과 삽입정렬에 대해서 공부해보았다. 모든 정렬을 한번에 정리하고 싶었지만 다른것도 공부할게 많고, 코드로 이해해보려해서 선택정렬 하나 해보는데 몇시간이 걸리는 아주 슬픈 상황이다...ㅠㅠ

유형

1. 선택정렬 (Selected Sort)

• 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있음

선택정렬 과정

1. 선택 배열 중 최소값을 찾는다
2. 최소값을 맨 앞에 위치한 값의 위치와 교환한다
3. 맨 처음 위치를 제외한 나머지 값들을 대상으로 위 루틴을 통해 하나의 원소가 남을 때 까지 반복한다

위 그림의 정렬 과정

1. idx 1번째 값 60과 나머지 값들의 크기 비교 -> 20이 최소값이므로 위치 교환
2. idx 2번째 값 55와 나머지 값들의 크기 비교 -> 25가 최소값이므로 위치 교환
3. idx 3번째 값 100과 나머지 값들의 크기 비교 -> 45가 최소값이므로 위치 교환
4. idx 4번째 값 100과 나머지 값들의 크기 비교 -> 55가 최소값이므로 위치 교환
5. idx 5번째 값 65와 나머지 값들의 크기 비교 -> 57이 최소값이므로 위치 교환
6. idx 6번째 값 65와 나머지 값들의 크기 비교 -> 60이 최소값이므로 위치 교환
7. idx 7번째 값 65와 나머지 값의 크기 비교 -> 100이 최소값이므로 위치 유지

Code

const selectedSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    let idx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[idx] > arr[j]) {
        idx = j;
      }
    }
    if (idx !== i) {
      const temp = arr[idx];
      arr[idx] = arr[i];
      arr[i] = temp;
    }
  }
  return arr;
}

2. 삽입정렬

• 삽입 정렬은 배열의 모든 값을 앞에서부터 차례대로 이미 정렬된 배열의 값과 비교 하여, 자신의 위치를 찾아 삽입하는 알고리즘이다.
• 삽입 정렬은 두번째 값 부터 시작한다.!

삽입 정렬 과정

• 두번 째 값부터 시작해서 그 앞의 값들과 비교하여 삽입할 위치를 지정하고 삽입할 위치에 있는 값과 교환한다.
• 두번 째는 첫번 째 값, 세번 째는 두번째, 첫번째 값 순으로 자신의 보다 적은 위치값을 가진 값들과 전부 비교한다.

위 그림의 정렬 과정

1. 첫번째 대상인 55와 첫번째에 위치한 60을 비교해서 값이 더 작은 55가 앞으로 가게 된다.
2. 두번째 대상인 100과 첫번째, 두번째 값을 비교해보니 대상의 값이 더 크므로 현재 위치에 자리한다.
3. 세번째 대상인 45와 첫번째, 두번째, 세번째 값을 비교해보니 45가 앞에 위치한 값들보다 작아서 맨 처음 index에 삽입된다.
4. 네번째 대상인 65와 앞의 값들을 비교해보니 4번째에 위치한 100보다 작고 1,2,3번째 위치한 값들보단 커서 100과 위치를 변경한다.
5. 다섯번째 대상인 57과 앞의 값들을 비교해보니 3,4,5번째 위치한 값보다 작아서 3번째 자리에 위치하게 된다.
6. 여섯번째 대상인 20은 앞의 값들과 비교하면 가장 최소값이 되므로 1번째 위치에 자리한다.
7. 마지막 대상인 25는 첫번째에 위치한 20보다 크고 두번째에 위치한 45보다는 작으므로 2번째 자리에 위치하고 삽입정렬이 완료된다.

Code

function insertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j + 1] < arr[j]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}