[알고리즘] 버블 정렬, 선택 정렬, 삽입 정렬

이번 시간에는 정렬방법 중 가장 구현하기 쉬운 방법인 버블 정렬, 선택 정렬, 삽입 정렬을 알아보겠습니다.

BubbleSort

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
  • 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환합니다.
• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네번째를, ... 이런 식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬합니다.
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 자료까지는 정렬에서 제외됩니다.
  이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어갑니다.

Bubblesort 알고리즘 구현 예제

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

• 1회전
  • 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
• 2회전
  • 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
• 3회전
  
  • 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
• 4회전
  • 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

참고 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

BubbleSort Typescript 구현 예제

export class Sort {
  private arr: number[];
  constructor(arr: number[]) {
    this.arr = arr;
  }

  bubbleSort(): number[] {
    const startTime = Date.now();
    // 최대값을 구하는 알고리즘을 arr 크기 - 1 만큼 반복한다.
    const iters = this.arr.length - 1;
    for (let i = 0; i < iters; i++) {
      // 이미 구한 최대값은 범위에서 제외한다.
      // 예를 들어 1회차에서는 1~4번 반복
      let wall = iters - i;
      //
      for (let j = 0; j < wall; j++) {
        if (this.arr[j] > this.arr[j + 1]) {
          [this.arr[j], this.arr[j + 1]] = [this.arr[j + 1], this.arr[j]];
        }
      }
    }
    const endTime = Date.now();
    console.log(endTime - startTime, "ms");
    return this.arr;
  }
}

BubbleSort 알고리즘의 특징 및 시간 복잡도

장점

• 구현이 매우 간단합니다.

단점

• 순서에 맞지 않는 요소를 인접한 요소와 교환합니다.
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 합니다.
• 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어납니다.

일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE) 보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구 하고 거의 사용되지 않습니다.

 

시간복잡도

• 비교 횟수
  • Best, Avg, Worst 모두 일정하다.
  • n(n-1)/2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
  • 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않습니다.
• O(N^2)

SelectionSort

• 제자리 정렬(in-place sorting) 알고리즘의 하나
  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬방법입니다.
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.
  • 첫번째 순서는 첫 번쨰 위치에 가장 최솟값
  • 두번째 순서에는 두 번째 위치에 남는 값 중에서의 최솟값을 넣습니다.
• 과정 설명
  
  1. 주어진 배열 중에서 최솟값을 찾습니다.
  2. 그 값을 맨 앞에 위치한 값과 교체합니다(패스(pass)).
  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체합니다.
  4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복합니다.
• 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행합니다.
• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞으로 오게 되므로, 그 다음 회전에서는 두 번째 자료를 가지고 비교합니다.

선택 정렬 알고리즘의 구체적인 개념

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

• 1회전
  • 첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.
• 2회전
  
  • 두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다.
• 3회전
  
  • 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다.
• 4회전
  
  • 네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

참고 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

SelectionSort Typescript 구현 예제

export class Sort {
  private arr: number[];
  constructor(arr: number[]) {
    this.arr = arr;
  }

  selectionSort(): number[] {
    const startTime = Date.now();
    // 배열 크기 - 1 만큼 반복합니다.
    const iters = this.arr.length - 1;
    for (let i = 0; i < iters; i++) {
      // 0번째 인덱스 부터 최솟값 삽입을 진행합니다.
      // minimum 초기 인덱스는 i로 설정합니다.
      let minimum = i;
      // minimum 부터 시작하는 반복문 수행
      // 최솟값을 찾습니다.
      for (let j = minimum; j < this.arr.length; j++) {
        if (this.arr[j] < this.arr[minimum]) {
          minimum = j;
        }
      }
      // 최솟값 인덱스와 삽입할 인덱스가 같지 않다면 변경 진행
      if (minimum != i) {
        [this.arr[minimum], this.arr[i]] = [this.arr[i], this.arr[minimum]];
      }
    }
    const endTime = Date.now();
    console.log(endTime - startTime, "ms");
    return this.arr;
  }
}

SelectionSort 알고리즘의 특징 및 시간 복잡도

장점

• 자료 이동 횟수가 미리 결정되어 있습니다.

단점

• 안정성을 만족하지 않습니다. 즉, 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있습니다.

시간복잡도

• 비교 횟수
  • 두 개의 for 루프의 실행 횟수
  • 외부 루프 : (n-1)번
  • 내부 루프 : n-1, n-2, ... , 2, 1번
• 교환 횟수
  • 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
  • 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)
• O(N^2)

 

InsertionSort

• 손 안의 카드를 정렬하는 방법과 유사합니다.
  • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입합니다.
  • 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬됩니다.
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣습니다.
• 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입합 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.
• 즉, 두번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째는 3~1번째 자료와 비교한 후 자료가 삽입될 위치를 찾습니다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한칸씩 뒤로 이동시킵니다.

삽입 정렬 알고리즘의 구체적인 개념

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

• 1회전: 두 번째 자료인 5를 Key로 해서 그 이전의 자료들과 비교한다.
  
  • Key 값 5와 첫 번째 자료인 8을 비교한다. 8이 5보다 크므로 8을 5자리에 넣고 Key 값 5를 8의 자리인 첫 번째에 기억시킨다.
• 2회전: 세 번째 자료인 6을 Key 값으로 해서 그 이전의 자료들과 비교한다.
  
  • Key 값 6과 두 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 6이 있던 세 번째 자리에 기억시킨다.
  • Key 값 6과 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 작으므로 Key 값 6을 두 번째 자리에 기억시킨다.
• 3회전: 네 번째 자료인 2를 Key 값으로 해서 그 이전의 자료들과 비교한다.
  • Key 값 2와 세 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 2가 있던 네 번째 자리에 기억시킨다.
  • Key 값 2와 두 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 세 번째 자리에 기억시킨다.
  • Key 값 2와 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 두 번째 자리에 넣고 그 자리에 Key 값 2를 기억시킨다.
• 4회전: 다섯 번째 자료인 4를 Key 값으로 해서 그 이전의 자료들과 비교한다.
  
  • Key 값 4와 네 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 다섯 번째 자리에 기억시킨다.
  • Key 값 4와 세 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 네 번째 자리에 기억시킨다.
  • Key 값 4와 두 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 세 번째 자리에 기억시킨다.
  • Key 값 4와 첫 번째 자료인 2를 비교한다. 2가 Key 값보다 작으므로 4를 두 번째 자리에 기억시킨다.

참조 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

InsertionSort Typescript 구현 예제

  insertionSort1(): number[] {
    const startTime = Date.now();
    // 0번째 요소는 이미 정렬되어 있으니, 1번째 ~ Array.length - 1 번째를 정렬하면 된다.
    for (let cur = 1; cur < this.arr.length; cur++) {
      // 비교 지점이 cur-1 ~ 0(=cur - cur)까지 내려간다.
      for (let delta = 1; delta < cur + 1; delta++) {
        let cmp = cur - delta;
        // 만약 해당 해당하는 위치의 index보다 그 다음값이 작은 경우
        // 값을 switching 해준다.
        if (this.arr[cmp] > this.arr[cmp + 1]) {
          [this.arr[cmp], this.arr[cmp + 1]] = [
            this.arr[cmp + 1],
            this.arr[cmp],
          ];
        } else {
          break;
        }
      }
    }
    const endTime = Date.now();
    console.log(endTime - startTime, "ms");
    return this.arr;
  }

  insertionSort2(): number[] {
    const startTime = Date.now();

    for (let idx = 1; idx < this.arr.length; idx++) {
      let val = this.arr[idx];
      let cmp = idx - 1;
      while (this.arr[cmp] > val && cmp >= 0) {
        this.arr[cmp + 1] = this.arr[cmp];
        cmp -= 1;
      }
      this.arr[cmp + 1] = val;
    }
    const endTime = Date.now();
    console.log(endTime - startTime, "ms");
    return this.arr;
  }

InsertionSort 알고리즘의 특징 및 시간 복잡도

장점

• 안정한 정렬 방법
• 레코드 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있습니다.
• 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있습니다.

단점

• 비교적 많은 레코드들의 이동이 포함됩니다.
• 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않습니다.

시간복잡도

• 최선의 경우
  
  • 비교 횟수
    
    • 이동 없이 1번의 비교만 이루어진다.
      
      • 외부 루프: (n-1)번
    • Best T(n) = O(n)
• 최악의 경우(입력 자료가 역순일 경우)
  
  • 비교 횟수
    
    • 외부 루프 안의 각 반복마다 i번의 비교 수행
    • 외부 루프: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
  • 교환 횟수
    
    • 외부 루프의 각 단계마다 (i+2)번의 이동 발생
    • n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)
  • Worst T(n) = O(n^2)

정렬 알고리즘 시간 복잡도

참조

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog