Merge Sort/퀵 정렬

Merge Sort란 ?

길이가 n인 배열을 정렬할 수 있으면 2n인 배열도 정렬할 수 있다는 재귀적인 마인드에서 시작

길이 n인 배열을 n/2 - 또 n/2 - ..... 해서 한개까지 쪼갠다음 , 이를 다시 1 2 .... n까지 합쳐나가는 식으로 정렬할 수 있음

쪼개는 함수 / 정렬하는 함수를 두개로 나눠서 구현해줌

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
   	
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //어차피 남은게 없으면 넣어도 변화가 없기때문에 그냥 넣어줌
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  //계속 절반씩 나눠주다가 길이가 1이 되면 return하면서 merge(한개,한개)가 실행
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
   
  return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);

간단하게 보면 재귀함수를 이용해서 길이가 1이 될때까지 쪼갠 뒤 길이 1인 배열 두개를 통해 길이가 2인 정렬된 배열을 두쌍 만들고 이 두쌍를 또 정렬해서 4개를 만들고 ....를 반복하면서 다시 처음으로 올라감

왼쪽/오른쪽을 둘 다 재귀함수를 쓰기 때문에 왼쪽먼저 1개까지 쪼개졌다가 n/2 길이의 정렬된 배열을 갖고, 그 다음 오른쪽이 1개까지 쪼개졌다가 똑같이 n/2 배열을 갖고 , 이 두개를 최종적으로 merge하면서 함수가 끝나게 됨

최초로 mergeSort([7,4,3,2,1,6,5]) 실행 - return merge(mergeSort([7,4,3,2]) , mergeSort([1,6,5]))
mergeSort([7,4,3,2]) 실행 - return merge(mergeSort([7,4]),mergeSort([3,2])
- mergeSort([7,4]) 실행
- return merge(mergeSort([7]),mergeSort([4]) 

mergeSort([7]) 이 [7]로 리턴, 그 다음 오른쪽에 있는 mergeSort([4]) 실행해서 [4]로 리턴

4번째 줄인 merge([7],[4])가 실행되면서 [4,7]이 리턴됨 // mergeSort([7,4])의 리턴값으로 [4,7]을 남기고 이 함수는 종료
이후 오른쪽에 있던 mergeSort([3,2]) 실행 - return merge(mergeSort([3],mergeSort([2])) 하고 리턴값으로 [2,3] 남기고 함수 종료
이후 merge([4,7],[2,3]) 실행하고 [2,3,4,7] 이 리턴되면서 mergeSort([7,4,3,2]) 종료

이후 mergeSort([1,6,5]) 실행 (과정은 위와 동일하게 한번 더 하는거임)
- return merge(mergeSort([1,6],mergeSort([5]))
mergeSort([1,6]) 실행 - return merge(mergeSort([1],mergeSort([6])) //return [1,6]
이후 mergeSort([5]) //return [5]
merge([1,6],[5]) 실행 // return [1,5,6]
이제 마지막으로 merge([2,3,4,7],[1,5,6]) 실행하면서 함수 종료

퀵 정렬

퀵 정렬은 배열의 요소 하나를 원래 있어야할 자리로 돌려놓는 것을 반복하는 정렬

보통 배열의 제일 앞 요소를 기준으로 삼음

[3, 4, 1, 26, -10, -23, 23, 5] 
여기서 3을 기준으로 잡고 3이 원래 있어야할 곳으로 집어넣어야 하는데 이때 포인터 두개가 필요
L=Index 1부터 시작하면서 기준값보다 큰 수가 있을 때까지 L++
R=Index 7부터 시작해서 기준값보다 작은 수가 있을때까지 R--
//L>R일때 break
이 경우에는 L이 4에서 멈추고, R이 -23에서 멈춤 -> 그러면 두 포인터가 가르키는 값을 스왑해줌
arr = [3,-23,1,26,-10,4,23,5] 로 바뀌었고, L은 여전히 1, R은 5
다시 L과 R을 이동시키면서 L은 26에서 , R은 -10에서 멈췄으니 두개를 바꿔줌
다시 L은 26에서 멈추고, R은 -10에서 멈췄는데 이때 L>R이기 때문에 멈추고 R자리의 값과 기준값을 스왑해줌
arr = [-10,-23,1,3,26,4,23,5] 
여기서 이제 3은 제자리를 찾았으니 3을 기준으로 두 배열을 다시 이런 방식으로 계속해서 해주면 됨

코드

const arr = [3, 4, 1, 26, -10, -23, 23, 5];

function quickSort(min = 0, max = arr.length) {
//함수의 인자로는 시작 Index,끝 Index+1이 들어감
  if (max <= min + 1) {
    return;
  }//배열의 길이가 1일때 return
  const pivot = arr[min];
  let L = min + 1;
  let R = max - 1;
  while (true) {
    while (arr[L] <= pivot) {
      L++;
    }
    while (arr[R] >= pivot) {
      R--;
    }
    if (L > R) {
      break;
    }
    let number = arr[R];
    arr[R] = arr[L];
    arr[L] = number;
  }
  let change = arr[R];
  arr[R] = pivot;
  arr[min] = change;
  
  //기준값을 기준으로 왼쪽 , 오른쪽으로 나누어서 재귀
  quickSort(min, R);
  quickSort(R + 1, max);
}
quickSort();
console.log(arr);