Quick sort (퀵소트, 퀵정렬) / merge sort(머지소트, 병합정렬)

퀵소트란? 

정렬계의 레전드라며..

분할정복 알고리즘의 일부

피봇을 정한뒤, 피봇이 위치를 확정해가며 정렬

 

Pivot? <= 피봇. 기준점을 잡아야하는것

피봇을 중심으로 좌우측을 나눈다.

수도코드?

1. 기준, 기준보다 작은 수는 기준의 좌측, 기준보다 큰 수는 기준의우측으로 배열을 정렬한다.
2. 그 좌측 우측에다 재귀를 1번을 적용한다.

기준을 정한다 0번째인덱스가 국룰.

 

출처 :&amp;nbsp;https://im-developer.tistory.com/135

 

const quickSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length <=1){
    return arr;
  }
  let pivot = arr[0]
  let left = [];
  let right = [];
  for(let i=1; i<arr.length;i++){
    if(arr[i]<=pivot){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  let lRecursive = quickSort(left)
  let rRecursive = quickSort(right)

  return [...lRecursive,pivot,...rRecursive]
};

 

 

 

머지소트란?

 

레퍼런스에 첨부해둔 블로그에서 정리를 너무 잘해주셔서 이해하기가 수월했다. 

 

 

수도코드

• 좌우를 기준으로 재귀적으로 나눈다.
• 좌우에다 정렬된 두 함수를 합치는 함수를 적용한다.

 

1. 좌우를 기준으로 재귀적으로 나누기. 

출처 : https://sleepybird.tistory.com/133?category=913100

 

2. 오름차순으로 정렬된 두 배열을 비교하고 합치는 함수 :결코 아무배열이나 합쳐지는것이 아님을 명심

크기를 비교해가며 결과배열에 푸쉬해줄거다.

둘다 배열의 길이가 0이 아닐동안

각 배열의 0번째 인덱스를 비교한다.

 

 

 

 

function merge (arr1, arr2){
  // 결과배열을 선언한다.
  // 두 배열모두 길이가 0이 아닐동안  
    // 각배열의 0번째 인덱스를 비교한다.  
    // 더 작은값을 *꺼내서 (shift해야됨) 결과배열에 푸쉬한다.  
  
  // arr1의 길이가 0이 아닐동안  
    // 각 배열의 0번째 인덱스를 꺼내서 결과배열에 푸쉬한다.
 
  // arr2의 길이가 0이 아닐동안
    // 마찬가지로 각 배열의 0번째 인덱스를 꺼내서 결과배열에 푸쉬한다.
  
  // 합쳐진 결과배열을 리턴한다.  
 
  const result = [];
  while(arr1.length && arr2.length){
    if(arr1[0] < arr2[0]){
      result.push(arr1.shift())
    }else{
      result.push(arr2.shift())
    }
  }
 
  while(arr1.length){
    result.push(arr1.shift())
  }
 
  while(arr2.length){
    result.push(arr2.shift())
  }
 
  return result;
}


function mergeSort (arr){
  // 만약 배열의 길이가 1이면 배열을 리턴한다.
  if(arr.length === 1)return arr;
  // 배열을 두동강 내서 좌 우로 구분시킨다.  
  const standard = parseInt(arr.length / 2);
  const left = arr.slice(0, standard);
  const right = arr.slice(standard);
  // 좌 우 각각 mergeSort시키고 merge한 값을 리턴한다.
  return merge(mergeSort(left), mergeSort(right));
}

 

 

 

 

 

 

 

 

 

 

 

 

레퍼런스 : https://sleepybird.tistory.com/134?category=913100 

[111일차]퀵정렬 알고리즘(Quick sort)

 

https://sleepybird.tistory.com/133?category=913100

[110일차]병합정렬 알고리즘(merge-sort)