[알고리즘] JS 자바스크립트 삽입정렬(Insertion Sort), 삽입정렬 알고리즘 코드

삽입정렬이란

삽입 정렬은 가장 큰 요소를 찾아 하나씩 이동하거나, 각 루프당 가장 작은 요소를 찾아 갱신하는 대신,

각 요소를 정렬된 배열에 삽입하는 방식이다.

 

삽입 정렬은 두 번째 자료부터 시작하여

그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후

자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

 

삽입 정렬은 루프당 하나의 키 값을 가진다

첫번째 루프의 키 값은 두번째 값이다 (그 다음 루프에서 키값은 세번째, 다음은 네번째 이렇게 된다)

그리고 키값을 앞의 값(첫번째 값)과 비교하여 삽입될 위치를 찾는다

첫 번째 값을 한칸 뒤로 이동시킨다

그리고 삽입될 위치인 첫 번째 위치에 키 값을 삽입한다

 

즉, 두번째 값은 첫번째와 비교,

세번째 값은 두번째와 첫번째 값과 비교,

네번째 값은 세번째 두번째 첫번째와 비교하여 정렬한다

삽입정렬 (Insersion Sort) 자바스크립트 JS 코드

이 코드는 삽입 정렬 (Insertion Sort) 알고리즘을 구현한 JavaScript 함수이다.

위에서 알아봤듯이 삽입 정렬은 배열을 정렬하는 간단한 방법으로,

주어진 배열을 순차적으로 탐색하면서 각 요소를 적절한 위치에 삽입하여 정렬을 수행한다

 

이 코드는 삽입 정렬 알고리즘을 사용하여 주어진 배열을 오름차순으로 정렬한다

코드 설명

함수 정의

insertionSort라는 이름의 화살표 함수를 정의하고, 정렬할 배열 arr을 매개변수로 받는다

const insertionSort = (arr) => {

 

첫 번째 for 루프

배열의 두 번째 요소(인덱스 1)부터 시작하여 마지막 요소까지 반복한다

i는 현재 삽입할 요소의 인덱스를 나타낸다

for (let i = 1; i < arr.length; i++) {

 

현재 값 저장

현재 인덱스 i의 값을 currentValue에 저장한다

이 값은 적절한 위치에 삽입될 것이다

let currentValue = arr[i];

 

두 번째 for 루프

j는 현재 인덱스 i의 이전 인덱스부터 시작하여 0까지 감소한다

이 루프는 currentValue보다 큰 요소를 찾기 위해 배열을 역방향으로 탐색한다.

for (j = i - 1; j >= 0 && arr[j] > currentValue; j--) {

 

요소 이동

currentValue보다 큰 요소를 발견하면, 그 요소를 오른쪽으로 한 칸 이동시킨다.

이는 currentValue가 삽입될 자리를 만들기 위함

arr[j + 1] = arr[j];

 

현재 값 삽입

currentValue를 적절한 위치에 삽입한다

j + 1은 currentValue가 들어갈 위치이다.

arr[j + 1] = currentValue;

 

정렬된 배열 반환

정렬이 완료된 배열을 반환한다

return arr;

 

예시 출력

• 첫 번째 호출에서는 [1, 2, 3, 4, 5, 6]가 출력된다
• 두 번째 호출에서는 [2, 4, 5, 6, 8]가 출력된다.

따라서 오름차순으로 잘 정렬된 것을 확인할 수 있다

 

삽입정렬 (Insersion Sort) 시간 복잡도

최선의 시간복잡도는 O(N), 최악은 O(N^2)으로 앞선 버블 정렬, 선택 정렬과 비슷하다

 

삽입정렬에서 최선의 상태는 이미 정렬된 배열에 요소를 추가하는 것이다

 

따라서

삽입 정렬이 활용적인 상황이 있는데, 바로 실시간 집계되는 데이터를 정렬해야 할 때이다.

이 경우 전체 배열을 다시 정렬할 필요 없이,

데이터가 수신되는 대로 해당 데이터 값을 기존 배열의 값과 비교하여 올바른 위치에 값을 삽입하면 되기 때문에

삽입 정렬이 매우 매우 유용하다.