Bubble Sort

  • 앞에서부터 두개씩 비교하며 더 큰거를 뒤로 보내가면서 제일 큰 숫자먼저 맨뒤로 보내면서 정렬하는 방식(뒤부터 자리가 픽스됨 )
function solution(arr) {

  for(let i = arr.length; i > 0; i--) {

    let j = 0;

    while(j < i) {
      if(arr[j] > arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp
      }
      j++;
    }

  }

  return arr
}

console.log(solution([3, 4, 5, 2, 6, 7, 9, 1, 8, 0]))

Selection Sort

  • 앞에서부터 한개씩 체크하면서 제일 작은것을 찾아서 맨앞자리로 보내면서 정렬하는 방식 (앞부터 자리가 픽스됨)
function solution(array) {
  for(let i = 0; i < array.length; i++) {

    let tmpMinIdx = i;

    for(let j = i + 1; j < array.length; j++) {
      if(array[j] < array[tmpMinIdx]) {
        tmpMinIdx = j
      }
    }

    let tmp = array[i];
    array[i] = array[tmpMinIdx];
    array[tmpMinIdx] = tmp;
  }

  return array

}

console.log(solution([3, 4, 5, 2, 6, 7, 9, 1, 8, 0]));

Inserstion Sort

* 8,4,2,3 ⇒ 4,8,2,3
	    4,8,2,3 ⇒ 4,2,8,3 ⇒ 2,4,8,3
    		                2,4,8,3 ⇒ 2,4,3,8 ⇒ 2,3,4,8
  • curIdx = 인덱스 1부터 시작해서 앞의 원소와 비교해서 curIdx가 더 작으면 자리 바꿔나나는 방식
function solution(arr) {

  for (let i = 1; i < arr.length; i++) { // i 가 위 예시의 빨간색역할

    let curIdx = i;
    let isTrue = true;

    while (isTrue) {
      let tmpIdx = curIdx - 1; // tmpIdx가 위 예시의 파란색 역할 

      if (arr[curIdx] < arr[tmpIdx]) { // 빨간색이 더 작으면 앞으로 보내기(파란색과 자리 바꾸기)
        let tmp = arr[curIdx];
        arr[curIdx] = arr[tmpIdx];
        arr[tmpIdx] = tmp;
        curIdx--;
      } else {
        isTrue = false; // 파란색이 더 작으면 앞에는 이미 정렬된 상태이므로 더이상 검사를 안해도된다.(while을 멈춰도된다)
      }
    }
  }
  return arr
}

console.log(solution([4, 2, 7, 1, 3]));
console.log(solution([8, 4, 2, 3]));

Quick Sort

  • 퀵정렬을 구현하는 방법의 첫번째는 왼쪽(피벗보다 작은값들)과 오른쪽(피벗보다 큰 값들)으로 쪼개서 배열을 만들고 각각 배열에 재귀를 타면 쪼개짐이 반복되면서 결국 left와 right의 길이가 1개로 되는시점이 온다. 그 지점에 다다랐을떄 모든 재귀들은 리턴값을 내면서 정렬이 되는 것 이다. 하지만 이 방법은 코드구현은 수월하지만 메모리 낭비가 심하다는 단점이 있다.
    두번째 방법은 swap으로 구현하는것인데. 이것은 메모리가 전혀 필요가없다. 일단은 첫번쨰 방법만 이해했는데 내일은 두번째 방법도 이해해서 꼭 구현해봐야겠다.! 재귀는 너무 어렵당..

  • 도움됬던 참고자료

방법1. 메모리공간 만들면서 구현

function quickSort(array) {
  if (array.length < 2) { // 재귀를 계속 돌다보면 결국 left와 right의 길이는 1이될것이다. 그것을 상상하면서 난 그저 현재 배열에서 left와 right를 쪼개는 것 이다.
    return array;
  }

  const pivot = [array[0]];
  const left = [];
  const right = [];

  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else if (array[i] > pivot) {
      right.push(array[i]);
    } else {
      pivot.push(array[i]);
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
}

방법2. swap으로 메모리 효율높이면서 구현

  • 가운데 원소를 피벗으로 설정하고 가장처음(왼쪽), 가장끝(오른쪽) 을 계속비교하면서 = [0,50,6,3,5,2,1,2] 이었다면
    • 피벗을 기준으로 작은애들은 왼쪽으로 두고 큰애들은 오른쪽으로 몰기 = [0,2,1,2,3,5,6,50] 가되고 리턴은 마지막 왼쪽인덱스인 5가리턴된다.
    • 인덱스5를 기준으로 위 로직을 왼쪽과 오른쪽에 재귀로 던짐 (그럼 그 재귀들도 피벗을 기준으로 왼쪽은 더 작은수들 오른쪽은더 큰수들을 두면서 반복해 나갈 것이다.)
    • 재귀니까 너무 끝까지 파고들어 상상하려하지말자. 일단 피벗을기준으로 왼쪽과 오른쪽을 가르기에 성공했다면 그 담부터는 인자만 정확히 주면서 재귀에게 맡기는것이다.)
//연습할 코드

function quickSort(array, left = 0, right = array.length - 1) {
  if (left >= right) {
    return;
  }

  const mid = Math.floor((left + right) / 2);
  const pivot = array[mid];
  const partition = divide(array, left, right, pivot);
  quickSort(array, left, partition - 1);
  quickSort(array, partition, right);

function divide(array, left, right, pivot) {
    while (left <= right) { // 왼쪽이 오른쪽보다 작거나 같을때까지만 반복
      while (array[left] < pivot) { // 왼쪽의 원소가 피벗보다 작으면 왼쪽++
        left++;
      }
      while (array[right] > pivot) { // 오른쪽원소작 피벗보다 크면 오른쪽--
        right--;
      }
      if (left <= right) { // 현재 왼쪽 오른쪽 자리 바꾸기 (같다면 그냥 그대로 겠지?)
        let swap = array[left];
        array[left] = array[right];
        array[right] = swap;
        left++;
        right--;
      }
    }
    return left;
  }

  return array;
}
profile
프론트엔드 개발자 블레어의 개인 블로그 입니다. 개발공부를 하며 나누고 성장하고 싶습니다 :)

0개의 댓글