Algorithm | 자바스크립트로 구현해본 선택 정렬과 삽입 정렬

정렬 알고리즘

: n개의 숫자가 입력으로 주어졌을때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력

선택정렬 & 삽입정렬

: 선택 정렬과 삽입 정렬은 시간복잡도가 𝑂(𝑁^2) 인 가장 간단한 형태의 정렬 알고리즘입니다.

📍선택정렬

:선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법입니다. 가장 작은 것을 선택하는 데에 𝑁번, 앞으로 보내는데에 𝑁번의 연산으로𝑂(𝑁^2) 의 시간복잡도를가집니다.

• 요소들이 들어갈 위치는 이미 정해져있다.

/*
* 선택정렬
*/
function selectionSort(arr=[]){
  //copy array
  let result = [...arr];
  for (let i=0; i<result.length-1; i++){
    // 현재 인덱스를 최소값이라고 가정, 찾아낸 가장 작은 값의 인덱스를 저장할 변수 정의
    // 시작 값으로 초기화
    let minNumPos = i;
    
    //오직 정렬되지 않은 배열에서만 탐색하기 위해서 -> 무조건 한바꾸 돌아야함
    for(let j= i+1; j< result.length; j++ ){
      if(result[minNumPos] > result[j]){
        minNumPos = j;
      }
    }
    
    //i가 가장 작은 값의 인덱스가 아닐 경우,swap
    // 인덱스i의 값과 인덱스 j의 값을 교화
    if(minNumPos !== i){
      // 1)
      //찾아낸 현재 최소의 값
      const temp = result[minNumPos];
      // switch
      // 찾아낸 최소값 인덱스 위치에 현재의 인덱스의 값을 넣고
      result[minNumPos] = result[i];
      // 현재의 위치에 찾아낸 최소값을 넣는다.
      result[i] = temp;
      
      // 2) 위의 과정을 ES6의 구조분해할당 을 이용하여 작성 
      //[result[minNumPos],result[i]]=[result[i],result[minNumPos]]
    }
    // 현재i에 대한 로직 끝
  }
  return result;
}

📍삽입정렬

:삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법입니다. 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번이므로 𝑂(𝑁^2) 의 시간복잡도를 가집니다.

• 정렬된 partial array를 유지하며, 한 칸씩 늘려가면서 정렬한다.
• 한 칸 늘릴 때 → 새로 삽입된 데이터를 정렬된 array에서 맞는 위치로 위치시킨다.

/*
* 삽입정렬
*/
function insertionSort(arr){
  let result = [...arr];
  
  for(let i=1; i<result.length; i++){
    let temp = arr[i] // 현재 값 저장
    let j=i-1;        // 비교인덱스 시작점 생성
    
    // partical array의 값이 현재 값 보다 클 때 swap
    while(j >= 0 && result[j] > temp){
     
      // 비교인데스 값을 한칸 뒤로 
      result[j+1] = result[j];
      // partical arrayd에서 칸을 한칸씩 내려서 확인하기 위해서 j--
      j-- ;
    };
     
    // partical array의 정렬된 부분에 <= 임시저장된 현재값
    result[j+1] = temp;
    
  };
  return result;
}

console.log(insertionSort([2,1,4,3,5])) // [1,2,3,4,5]