자료구조 - Sort(Insertion Sort)

Insertion Sort

정의 : 자신의 위치를 찾아 삽입하는 정렬 알고리즘.

• 정렬된 부분 (A[0]), 정렬 되지 않은 부분 (A[1] ... A[n-1])으로 구분하여 정렬.
• 시간복잡도 : O(n^2)

package javastudy;

public class insertSort {
  public static void is(int a[]) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
      int insertionKey = a[i]; // 삽입할 현재 요소
      int j = i - 1;

      while (j >= 0 && a[j] > insertionKey) {
        a[j+1] = a[j]; // 한칸 뒤로
        j = j-1; // 왼쪽 index로 이동
      }
      a[j+1] = insertionKey; // 현재 요소 삽입
    }
  }

  public static void printArray(int a[]) {
    for (int num : a) {
      System.out.print(num+ " ");
    }
  }

  public static void main(String[] args) {
    int A[] = {8, 5, 6, 2, 4};
    System.out.println("정렬 전");
    printArray(A);
    System.out.println("정렬 후");
    is(A);
    printArray(A);
  }
}