기본 정렬(버블정렬, 선택정렬, 삽입정렬)

1. 버블정렬(bubble sort)

• (오름차순 기준)인접한 두 데이터를 비교하여 앞의 데이터가 뒤의 데이터보다 크다면 자리를 바꿈
• 정렬 1턴을 수행할 때마다 해당 턴의 맨 마지막 위치에 정렬이 완료된 데이터가 배치됨
• 각 턴의 마지막은 턴을 수행할 때마다 한 칸씩 앞으로 옴
• 어느 특정 턴에서 swap이 일어나지 않은 경우는 더 이상 정렬할 것이 없다는 의미이므로 이 경우 전체 정렬을 중단함

https://en.wikipedia.org/wiki/Bubble_sort

function bubbleSort(data) {
  for (let i = 0; i < data.length; i++) {
    let swap = false;
    for (let j = 0; j < data.length - 1 - i; j++) {
      if (data[j] > data[j + 1]) {
        [data[j], data[j + 1]] = [data[j + 1], data[j]]
        swap = true;
      }
    }
    if (!swap) break;
  }
  return data;
}

 

2. 선택정렬(selection sort)

• 정렬 수행시 한 턴에서 데이터들 중 가장 작은 값을 찾고 각 턴에서 선택된 최소값을 턴의 맨 앞 데이터와 교체함
• 각 턴의 맨 앞 데이터는 이미 정렬이 완료된 상태이므로 다음 턴에서는 그 다음 데이터부터 마지막 데이터까지 동일한 작업을 수행

https://en.wikipedia.org/wiki/Selection_sort

function selectionSort(data) {
  for (let i = 0; i < data.length - 1; i++) {
    let lowest = i;
    for (let j = i + 1; j < data.length; j++) {
      if (data[lowest] > data[j])
        lowest = j;
    }
    [data[lowest], data[i]] = [data[i], data[lowest]];
  }
  return data;
}

 

3. 삽입정렬(insertion sort)

• 두 번째 인덱스부터 시작함
• 해당 인덱스 값(key)의 앞에 있는 데이터(target)부터 비교, key 값이 더 작으면 target 값을 뒤 인덱스로 복사, 이를 target 값보다 key 값이 더 큰 경우까지 반복하여 해당 target 위치 바로 뒤에 key 값을 이동시킴
• 맨 처음 턴에서 첫 번째 값이 target이 되고 두 번째 값이 key값이 됨
• key값은 차례로 앞의 값들끼리 비교하면서 앞부분 값 중 key보다 작은 target값이 있다면 검사를 멈추고 해당 target 다음 위치에 key 값을 배치함

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

function insertionSort(data) {
  for (let i = 1; i < data.length; i++) {
    let tmp = data[i];
    let j = i - 1;
    while (j >= 0) {
      if (data[j] > tmp) {
        data[j + 1] = data[j];
      } else {
        break;
      }
      j--;
    }
    data[j + 1] = tmp;
  }
  return data;
}