[Algorithm] 정렬(기본)

🌼 정렬(Sort)

정렬은 n개의 원소를 순서대로 배열하는 것이다. 정렬 알고리즘은 매우 여러가지가 있는데 이 글에서는 기본적인 정렬 알고리즘에 대해서 알아보겠다.

• 기본적 정렬 알고리즘: O(n²)만큼의 시간 복잡도가 걸리는 알고리즘으로 선택(Selection), 버블(Bubble), 삽입(Insertion) 정렬이 이에 해당한다.

• 효율적 정렬 알고리즘: O(n log n)만 큼의 시간 복잡도가 걸리는 알고리즘으로 병함(Merge), 힙(Heap), 퀵(Quick) 정렬이 이에 해당한다.

• 고효율 정렬 알고리즘: 입력된 원소들이 특수한 성질을 만족하는 경우에 사용할 수 있는 알고리즘으로 O(n)만큼의 시간 복잡도가 걸린다. 기수(Radix), 계수(Counting) 정렬이 이에 해당한다.

🌼 기본적 정렬 알고리즘

• 선택 정렬: 정렬되지 않는 배열에서 가장 작은 데이터를 선택해서 맨 앞에서부터 순서대로 정렬해나가는 알고리즘이다.

  

const nums = [8, 31, 48, 73, 3];

function selectionSort(nums) {
  for (let i = 0; i < arr.length-1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      let swap = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = swap; 
    }
  }
  return arr;
}

//2021-10-10 update
function selectionSort(nums) {
  //선택 정렬: 가장 작은걸 선택해서 비교 위치의 값과 교체하여 정렬하는 방식
  let arr = [...nums];
  for (let i = 0; i < arr.length - 1; i++) {
    let idx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[idx] > arr[j]) idx = j;
    }
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
  }
  return arr;
}

• 버블 정렬: 서로 인접한 원소를 비교하여 제일 큰 원소를 맨 오른쪽으로 보내어 정렬해나가는 알고리즘이다. 큰 수를 뒤로 보내다보면 루프가 끝났을 때 맨 뒤에는 자연스레 정렬 중 가장 큰 숫자가 자리잡게 된다. 수면위에 거품이 떠오르는 것처럼 큰수가 오른쪽으로 떠오른다고해서 버블 정렬이라고 한다.

const nums = [8, 31, 48, 73, 3];

function bubbleSort(nums) {
  for (let i = arr.length-1; i > 0; i--) {
    let sorted = true; //이미 정렬이 완료되었다면 sorted가 false로 바뀌지 않음
    for (let j = 0; j < i; j++) {
      if (arr[j]  > arr[j+1]) {
        let swap = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = swap;
        sorted = false;
      }
    }
    if (sorted == true) return arr; //중간에 정렬이 완료됐을 때 루프 종료 목적
  };
  return arr; //마지막까지 원소 교환이 일어났을 경우, sorted가 false이므로 값을 리턴
}

//2021-10-10 update
function bubbleSort(nums) {
  //버블 정렬: 인접한 두 수를 비교하여 큰 수를 오른쪽으로 보내며 정렬하는 방식
  //루프가 1회 끝난 시점에는 맨 마지막 위치에 배열의 가장 큰 수가 자리잡게 된다.
  let arr = [...nums];
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - (i + 1); j++) {
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
  }
  return arr;
}

• 삽입 정렬: 이미 정렬되어 있는 i개짜리 배열에 원소를 하나 더하여 정렬된 i+1개의 배열을 만드는 과정을 반복하여 정렬해나가는 알고리즘이다.

const nums = [8, 31, 48, 73, 3];

function insertionSort(nums) {
  for (let i = 1; i < arr.length; i++) {
    let location = i-1;
    let pick = arr[i];

    while (location >= 0 && pick < arr[location]) {
      let swap = arr[location];
      arr[location] = pick;
      arr[location+1] = swap;
      location--;
    }
  }
  return arr;
}

//2021-10-11 update
function solution(nums) {
  let arr = [...nums];
  for (let i = 1; i < arr.length; i++) {
    let tmp = arr[i],
      j;
    for (j = i - 1; j >= 0; j--) {
      //arr[j]가 tmp보다 크면 tmp가 앞으로 가야하기 때문에 한자리식 뒤로 밀려난다.
      //여기서 j 위치에는 값이 없다고 생각하면 된다.
      if (arr[j] > tmp) arr[j + 1] = arr[j];
      //arr[j]의 값이 tmp보다 작을 경우에는 j+1 위치 즉, 전 루프에서 비워진 j 위치에 tmp를 넣어준다.
      else break;
    }
    arr[j + 1] = tmp;
  }
  return arr;
}