Algorithm

정렬 : sort

• 여러 개의 데이터로 구성된 리스트가 주어졌을 때, 데이터들을 값의 크기 순서대로 재배치하는 것
  • 내부정렬
    • 정렬할 데이터 전체를 주기억장치에 저장한 후 정렬
  • 외부정렬
    • 데이터의 양이 너무 많아 보조기억장치에 저장해 두고 일부 데이터만을 반복적으로 주기억장치로 옮겨와 정렬을 수행
• 안정적 정렬
  • 리스트내에 같은 값을 가지고 있는 데이터가 존재할 경우 상대적 순서 유지가 보정이 되는 정렬
• 불안정적 정렬
  • 리스트내에 같은 값을 가지고 있는 데이터가 존재할 경우 상대적 순서가 유지 되는것이 보장이 안됨.

선택 정렬 : selection sort

• 주어진 데이터 내에서 가장 작거나, 큰 값을 선택해 차례대로 정렬하는 방법

public class SortTest {

  public int[] selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
      int min = array[i];   //  미정렬 부분의 첫 번쨰 원소를 최솟값으로 지정.
      for (int j = i; j < array.length; j++) {  //   최솟값 찾기.
        if (min > array[j]) {
          min = array[j];
          switchingHelper(array, i, j); //  위치 교환.
        }
      }
    }
    return array;
  }

  public void switchingHelper(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }

}

• 시간 복잡도 : O(n²)
• 입력 데이터의 순서에 민감하지 않다.
  • 입력 데이터가 오름차순인지, 내림차순인지, 임의로 나열되었는지와는 무관
• 제자리 정렬 알고리즘이다.
  • 입력 배열 이외에 별도의 저장 공간이 상수개를 넘지 않음.
• 안정적인 정렬 알고리즘이 아니다.

버블 정렬 : bubble sort

• 인접한 두 데이터를 차례대로 비교해서 왼쪽 데이터와 오른쪽 데이터의 자리를 바꾸는 과정을 반복.

public class SortTest {

  public int[] bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
      boolean sort = true;    //  최적화를 위한 변수 선언
      for (int j = i; j < array.length; j++) {
        if (array[i] > array[j]) {
          switchingHelper(array, i, j);
          sort = false;
        }
      }
      if (sort) break;
    }
    return array;
  }

  public void switchingHelper(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }

}

• 시간 복잡도 : O(n²)
• 안정적인 정렬 알고리즘이다.
• 제자리 정렬 알고리즘이다.
• 입력 데이터의 상태에 따라 성능이 달라진다.
• 선택 정렬에 비해 데이터의 교환이 많이 발생한다.

삽입 정렬 : insertion sort

• 주어진 데이터를 하나씩 뽑은 후 이미 나열된 데이터가 항상 정렬된 형태를 유지하더록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식

public class SortTest {

  public int[] insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      for (int j = i; j > 0 && array[j - 1] > temp; j--) {
        switchingHelper(array, j, j - 1);
      }
    }
    return array;
  }

  public void switchingHelper(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }

}

• 시간 복잡도 : O(n²)
• 안정적인 정렬 알고리즘이다.
• 제자리 정렬 알고리즘이다.
• 입력 데이터의 원래 순서에 민감하다.

셸 정렬 : shell sort

• 삽입 정렬을 보완하기 위한 정렬 알고리즘
  • 멀리 떨어진 데이터와의 비교, 교환으로 한번에 이동할 수 있는 거리를 늘려 처리 속도를 향상시킴

public class SortTest {

    public int[] shellSort(int[] array) {
        for (int i = array.length / 2; i > 0; i /= 2) {
            for (int j = i; j < array.length; j++) {
                int temp = array[j];
                for (int k = j; k >= i && array[k - i] > temp; k -= i) {
                    switchingHelper(array, k, k - i);
                }
            }
        }
        return array;
    }

    public void switchingHelper(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

}

• 전체 배열을 나누는 값에 따라 성능이 달라진다.
  • 사용하는 순열에 따라 성능이 달라진다.
• 안정적이지 않은 정렬 알고리즘이다.
• 제자리 정렬 알고리즘이다.