[Algorithm] 3-1. 기본 정렬 알고리즘(selection, bubble, insertion sort) with JAVA

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

3-1. 정렬

• simple, slow

  • Bubble sort

  • Insertion sort

  • Selection sort

• fast

  • Quick sort

  • Merge sort

  • Heap sort

• O(n)

  • Radix sort

기본적인 정렬 알고리즘

Selection Sort

• 각 루프마다

  • 최대 원소를 찾는다

  • 최대 원소와 맨 오른쪽 원소를 교환한다.

  • 맨 오른쪽 원소를 제외한다.

• 하나의 원소만 남을 때까지 위의 루프를 반복한다.

• pseudocode

selectionSort(A[], n) {
  for last <- n downto 2 {                              == 1
    A[1,...,last] 중 가장 큰 수 A[k]를 찾는다;               == 2
    A[k] <-> A[last];  // A[k]와 A[last]의 값을 교환       == 3
  }
}

• 실행시간

  • 1의 for 루프는 n-1번 반복

  • 2에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, ... , 2, 1

  • 3의 교환은 상수시간 작업

• 시긴복잡도 T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n²)

  • 최악, 최선, 평균 항상 n(n-1) / 2번의 비교연산을 수행하게 되므로 O(n²)이다.

• 구현

public class Selection {
  private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};
​
  public static void main(String[] args) {
    selectionSortMin(input, input.length);
    for (int a : input) {
      System.out.print(a + " ");
    }
  }
​
  private static void selectionSortMin(int[] input, int length) {
    int min;
    int tmp;
    for (int i = 0; i < length - 1; i++) {
      min = i;
      for (int j = i + 1; j < length; j++) {
        if (input[j] < input[min])
          min = j;
      }
      tmp = input[i];
      input[i] = input[min];
      input[min] = tmp;
    }
  }
​
  private static void selectionSortMax(int[] input, int length) {
    int max;
    int tmp;
    for (int i = length - 1; i > 0; i--) {
      max = i;
      for (int j = i -1; j >= 0; j--) {
        if (input[j] > input[max])
          max = j;
      }
      tmp = input[i];
      input[i] = input[max];
      input[max] = tmp;
    }
  }
}

1 2 4 5 6 7 8 23 
Process finished with exit code 0

Bubble Sort

• 실행시간

  • (n-1) + (n-2) + … + 2 + 1 = O(n²)

• pseudocode

bubbleSort(A[], n) {
  for last <- n downto 2 {                    == 1
    for i <- to last-1                        == 2
      if (A[i] > A[i+1]) the A[i] <-> A[i+1]; == 3
  }
}

• 수행시간

  • 1의 for 루프는 n-1번 반복

  • 2의 for 루프는 각각 n-1, n-2, … , 2, 1번 반복

  • 3의 교환은 상수시간 작업

• T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n²)

  • 최악, 최선, 평균 항상 n(n-1) / 2번의 비교연산을 수행하게 되므로 O(n²)이다.

• 구현

public class Bubble {
  private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};
​
  public static void main(String[] args) {
    bubbleSort(input, input.length);
    for (int a : input) {
      System.out.print(a + " ");
    }
  }
​
  private static void bubbleSort(int[] input, int length) {
    int tmp;
    for (int i = length - 1; i > 0; i--)
      for (int j = 0; j < i; j++) {
        if (input[j] > input[j + 1]) {
          tmp = input[j];
          input[j] = input[j + 1];
          input[j + 1] = tmp;
        }
      }
  }
}

1 2 4 5 6 7 8 23 
Process finished with exit code 0

Insertion Sort

• 맨 처음 인덱스에 있는 원소를 정렬되어있는 상태라고 보고, 두번째 인덱스에 있는 데이터를 이 정렬된 배열에 삽입하면서, 두개의 데이터가 다시 정렬된 상태가 되도록 만드는 정렬 방법이다. 반복적으로.

• insertion의 일반적인 one step

  • k-1까지 정렬된 배열에 k번째 인덱스를 추가하는데, k번째 인덱스가 위치해야할 적절한 위치에 끼워 넣어서,

  • 배열의 k번째 까지 정렬되도록 하는 흐름을 가진다.

• 어떻게 k번째 인덱스가 들어갈 위치를 찾는가?

  • 앞에서 부터 비교하면서 찾는 방법, 뒤에서 부터 비교하면서 찾는 방법이 있다.

  • 얼핏 생각하면 같은 방법인것 처럼 보이나, 다른점이 있다.

  • 앞에서 부터 인덱스의 요소들을 비교하면서 자리를 찾는다면, k번째 인덱스보다 작은 값들을 일일히 검사를 해야한다. 이것은 뒤에서 부터 자리를 찾는 작업에서도 똑같이 이루어진다.

  • 하지만, 들어갈 위치를 찾았을 때, 배열이라는 자료구조의 특성상 해당 위치부터 k-1인덱스까지의 요소들을 한칸씩 shift 시키는 작업이 필요하다.

  • 결과적으로 앞에서부터 비교를 하면, 모든 데이터를 한번씩은 적어도 봐야된다.

  • 그러나, 뒤에서 부터 비교한다면 비교와 동시에 switch하는 작업을 행해줌으로써 자동으로 shift 작업을 수행한다.

  • 해당 데이터가 자리를 찾는 순간 앞의 데이터들은 비교할 필요가 없다. 따라서, 뒤에서 부터 비교해서 자리를 찾는 작업이 더 효율적인 작업이다.

• 비교와 동시에 switch 작업을 하기위해서 임시변수 tmp를 유지한다. 그리고 k-1 부터 0번 인덱스까지 compare작업과 shift작업을 반복적으로 수행한다.

• pseudocode

insertionSort(A[], n) { // 배열 A[1...n]을 정렬한다.
  for i <- 2 to n                       == 1
    A[1...i]의 적당한 자리에 A[i]를 삽입한다.  == 2
}

• 수행시간

  • 1의 for 루프는 n-1번 반복

  • 2의 삽입은 최악의 경우 i-1번 비교

• 최악의 경우

  • T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n²)

• 최선의 경우 = 즉, 배열이 정렬되어있는 경우에는 O(n)의 시간 복잡도를 가진다.

• 따라서, selection sort나 bubble sort와 비교했을때, 최악의 경우에는 차이가 없지만 평균적으로는 대략 절반 정도의 정렬 시간을 필요로 한다.

• 구현

public class Insertion {
  private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1, 44};
​
  public static void main(String[] args) {
    insertionSort(input, input.length);
    for (int a : input) {
      System.out.print(a + " ");
    }
  }
​
  private static void insertionSort(int[] input, int length) {
    int tmp;
    for (int i = 1; i < length; i++) {
      for (int j = i; j > 0; j--) {
        if (input[j - 1] > input[j]) {
          tmp = input[j - 1];
          input[j - 1] = input[j];
          input[j] = tmp;
        }
      }
    }
  }
}

1 2 4 5 6 7 8 23 44 
Process finished with exit code 0