정렬 알고리즘

1. 선택 정렬

• 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법이다.
• 앞으로 보내진 원소는 더 이상 위치가 변경되지 않는다.
• 시간 복잡도로 O(n^2)로 비효율적인 정렬 알고리즘이다.

각 단계에서 가장 작은 원소를 선택하고 처리되지 않은 원소중 가장 앞에 있는 원소랑 자리를 교체함.

이해가 안가서 하나하나 배열을 쳐보면서 따라가 보았다.

const arr = [2, 4, 3, 1, 9, 6, 8, 7, 5];

function selecttoinSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i; // 0 
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    // temp = arr[0]  temp = 2
    let temp = arr[i];

    // arr[0] = arr[3], 2 = 1
    arr[i] = arr[minIndex];

    // arr[3] = 2 
    // 스왑이 일어나서 (1,이랑 2 랑 자리 바꾸게 됨)
    // 1 4 3 2 9 6 8 7 5 
    // 다음 for 루프에서는 i = 1일꺼고 minindex도 1부터 시작해서 한 번 바꾼 자리는 고정이다.
    arr[minIndex] = temp;
  }
}

2. 버블 정렬

• 단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경한다.
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름이다.
• 시간 복잡도 O(n^2)로 비효율적인 정렬 알고리즘이다.

• 각 단계에서는 인접한 두 개의 원소를 비교하여, 필요시 위치를 변경한다.
• 첫째ㅔ와 둘째를 비교, 둘째와 셋째를 비교, 셋째와 넷째를 비교하는 방식이다.
• 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동한다.
• 따라서, 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬이 끝난거다.

const arr = [1, 5, 2, 3, 6, 7];

function bublleSort(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      // 여기 등호만 바꿔주면 오름차순, 내림차순 정렬을 할 수 있다.
      if (arr[j] > arr[j + 1]) {
        // temp = arr[0] => temp = 1
        let temp = arr[j];

        // arr[0] = arr[1] => 5
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
      // 1
    }
  }
}

• 신기한건 선택정렬보다 소요시간이 더 크다. 훨씬 비효율적이란 말.
• 선택정렬 이해하고 나니까 버블정렬 이해는 꽤 쉬웠다.
• 구현 자체는 선택보다 더 쉬운듯.
• 데이터가 클때는 쓰면 안된다.

삽입 정렬

• 삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다.

1. 각 단계에서 현재 원소가 삽입될 위치를 찾는다.
2. 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동한다.

O(n^2) 으로 비효율적임.

• 삽입 정렬을 수행할 때는 처음에 첫 번째 원소는 정렬이 되어 있다고 고려한다.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        let temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      } else {
        // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        break;
      }
    }
  }
}

• 선택, 버블 보다는 빠르다. 어느 정도 정렬이 되어있는 상태라면 효율적이다.

병합 정렬

• 현존하는 정렬알고리즘 중 빠르게 동작하는 알고리즘 중 하나다.
• nlogn을 보장함. -> 10만개가 넘어가면 적절한 알고리즘이다.
• 전형적인 분할 정복!! 알고리즘이다.

분할 정복

• 분할 : 큰 문제를 작은 부분 문제로 분할한다.
• 정복 : 작은 부분 문제를 각각 해결한다.
• 조합 : 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결한다.
  큰 문제를 작은 문제로 분할 하는 방식이 재귀함수의 동작 방식과 유사하다. 더 이상 쪼갤 수 없는 크기가 될 때까지 계속하여 분할한다.

단점

• 재귀 함수를 사용해서 함수 호출 횟수가 많이 발생한다.
• 메모리가 많이 사용될 수 있다.(스택)
• 이는 오버헤드로 이어진다.

다시 돌아와서 병합정렬은?

• 분할 정복을 사용하는 알고리즘이다.
• 정렬할 배열을 같은 크기의 배열 2개로 분할한다. (분할)
• 부분 배열을 정렬한다. (정복)
• 정렬된 부분 배열을 하나의 배열로 다시 병합한다. (조합)

• 원소가 한개가 남게 된다면 정렬이 완료되었다고 본다
• 두 개의 부분 배열을 정렬이 완료된 하나의 배열로 만든다. (정복)

• 원소가 100만개 라고 했을 때 2로 나누어간다면 20번이면 원소가 하나만 남게 된다.
• 즉 그래서 nlogn이다.

const arr = [8, 4, 6, 1, 2, 5, 7, 3];

// 병합 수행함수

function merge(arr, left, mid, right) {
  let i = left;
  let j = mid + 1;
  let k = left; // 결과 배열의 인덱스
  while (i <= mid && j <= right) {
    if (arr[i] < arr[j]) sorted[k++] = arr[i++];
    else sorted[k++] = arr[j++];
  }
  // 왼쪽 배열에 대한 처리가 다 끝난 경우
  if (i > mid) {
    for (; j <= right; j++) sorted[k++] = arr[j];
    // 오른쪽 배열에 대한 처리가 다 끝난 경우
  } else {
    for (; j <= mid; i++) sorted[k++] = arr[i];
  }
  // 정렬된 배열 결과를 원본 배열에 반영하기
  for (let x = left; x <= right; x++) {
    arr[x] = sorted[x];
  }
}

function mergeSort(arr, left, right) {
  if (left < right) {
    let mid = parseInt((left + right) / 2);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

Sort 함수 쓰기

• 숫자에 대해서 sort 함수를 쓰는 것은 너무 쉽기 때문에 문자열에 대하여 내림차순 정렬을 하는법을 적어놓도록 하겠다.

arr.sort(function(a,b){
	if( a> b) return -1
    else if (a < b) return 1
    else return 0
})

• 대소문자 구분없이 toUpperCase()메소드를 사용할 수 있다.

function compare(a,b){
  let upperCaseA = a.toUpperCase()
  let upperCaseB = b.toupperCase()
  if(upperCaseA < upperCaseB) return -1
  else if(upperCaseA > upperCaseB) return 1
  else return 0
}

arr.sort(compare)

• 객체도 가능 하다

let test = [
  { name: "김호준", score: 97 },
  { name: "김땡댕", score: 87 },
  { name: "홍길동", score: 90 },
];

function compare (a,b){
  return b.score -a.score
}
arr.sort(compare)