[알고리즘] 간단한 정렬 알고리즘(Bubble, Insertion, Selection)

정렬 알고리즘 중 Bubble, Insertion, Selection Sort 의 개념 및 코드로 어떻게 표현하는지 공유드립니다.

Bubble sort

Bubble Sort은 두 인접한 원소를 검사하여 정렬하는 방법입니다.
냇가에서 물고기 잡을 때 물고기 몰이 하는 것처럼 앞에서부터 마지막 항목까지 인접한 두 항목을 비교해서 정렬하는 방법입니다.

• 수도코드

  bubbleSort(A[], n)      배열 A[1..n] 을 정렬한다.
  {
  for last <- n down to 2                           //[1]
      for i <- 1 down to last-1                     //[2] 가장 큰 수 A[k]를 찾는다.
          if (A[i]>A[i+1]) then A[i] <-> A[i+1]       //[3] A[k]와 A[last] 교환
  }

• 실행 시간 :
  [1] for 루프 n-1 반복,
  [2] for 루프는 각각 n-1, n-2 ... 2, 1 번 반복
  [3] 교환 상수 시간 작업

• 시간 복잡도
  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)
  T(n) = n(n-1)/2 = O(n^2)

 

• 소스코드
  bubble.Java

  public static void bubbleSort(int[] arr) {
      for(int i = 0; i<arr.length; i++) {
          for(int j = 1; j<arr.length - i; j++) {
              if(arr[j] <  arr[j-1]) {
                  int temp = arr[j];
                  arr[j] = arr[j-1];
                  arr[j-1] = temp;
              }
          }
      }
  }

Insertion Sort

Insertion Sort는 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.

정렬 방법은 temp 공간에 가장 마지막 항목을 이동시킨다음 Size - 1 항목부터 비교하여 정렬 합니다.

• 수도코드

  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^2)
  T(n) = n(n-1)/2 = O(n^2)

• 소스코드
  insertionSort.Java

  public static void insertSort(int[] arr) {
      for(int i = 1 ; i< arr.length; i++) {
          int temp = arr[i];
          int aux = i - 1;
          while(aux>=0 && arr[aux] > temp) {
              arr[aux+1] = arr[aux];
              --aux;
          }
          arr[aux +1] = temp;
      }
  }

Selection Sort

Selection Sort는 제자리 정렬로 알려져있는 선택정렬은 다음과 같은 순서로 이뤄집니다.

1. 주어진 리스트 중에 최소 값을 찾느다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.( 패스(pass))
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

또는 가장 큰 값을 찾고 가장 끝자리 있는 값과 바꾸는 형태

• 수도코드

  selectSort(A\[\], n) 배열 A\[1..n\] 을 정렬한다.  
  {  
  for last <- n down to 2 //\[1\]  
  S\[1..last\] //\[2\] 가장 큰 수 A\[k\]를 찾는다.  
  A\[k\] .. A\[last\] //\[3\] A\[k\]와 A\[last\] 교환  
  }  

• 실행 시간 :
  [1] for 루프 n-1 반복,
  [2] 가장 큰 수 찾기 위한 비교 횟수 n-1, n-2 ... 2, 1
  [3] 교환 상수 시간 작업

• 시간 복잡도
  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)
  T(n) = n(n-1)/2 = O(n^2)

• 소스코드
  selectionSort.java

  // 끝자리 기준 정렬
  public static void selectionSort(int[] arr) {
      for(int i = 0; i<arr.length; i++){
          int max = arr[arr.length - i - 1] ;
          int position = arr.length - i - 1;
          for(int j = 0; j < arr.length - i; j++){
              if(max < arr[j]){
                  max = arr[j];
                  position = j;
              }
          }
          int temp = arr[arr.length - i - 1];
          arr[arr.length - i - 1] = arr[position];
          arr[position] = temp;
      }
  }
  
  // 첫 자리 값 기준 정렬
  public static void selectionSortFromLowValue(int[] arr) {
      for(int i = 0; i<arr.length; i++){
          int min = arr[i];
          int position = i;
          for( int j = i; j < arr.length; j++){
              if(min > arr[j]){
                  min = arr[j];
                  position = j;
              }
          }
          int temp = arr[i];
          arr[i] = min;
          arr[position] = temp;
      }
  }

정리

기본적인 정렬 알고리즘에 대해서 정리하였습니다.
소개한 Bubble Sort, Insertion Sort, Seletion Sort의 시간 복잡도는 O(n)이지만 간단한 정렬 알고리즘 구현 시 도움이 될 것으로 생각됩니다.