Algorithm|JavaScriptによる選択ソートと挿入ソート


ソートアルゴリズム
: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を保持し、1つずつ追加して並べ替えます.
  • グリッドを追加すると→新しく挿入したデータを整列した配列から正しい位置に位置決めします.
  • /*
    * 삽입정렬
    */
    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]