[Java / 알고리즘] 대표적인 정렬 알고리즘. 버블 정렬, 삽입 정렬, 선택 정렬

정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.
예를 들어 n개의 숫자가 저장되어있는 배열을, 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다.
정렬 알고리즘은 정말 다양한데, 이에 따라 각각의 수행시간도 천차 만별이다.

 

1. 버블 정렬(Bubble Sort)

두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 방식이다.

 

[ 코드 ]

static void bubbleSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        boolean swap = false;

        for (int j = 0; j < n - i - 1; j++) {
            // 현재 원소와 다음 원소를 비교하여 순서가 잘못되었다면 교환
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap = true;
            }
        }

        if(!swap) {
            break;
        }
    }
}

 

시간 복잡도

코드에서 보이는 것처럼 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.

 

 

2. 삽입 정렬(Insertion Sort)

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

 

[ 코드 ]

static void insertionSort(int[] arr) {
  int n = arr.length;

  for (int i = 1; i < n; i++) {
      int key = arr[i];
      int j = i - 1;

      // key보다 큰 원소들을 오른쪽으로 이동
      while (j >= 0 && arr[j] > key) {
          arr[j + 1] = arr[j];
          j = j - 1;
      }

      // key를 올바른 위치에 삽입
      arr[j + 1] = key;
  }
}

 

 

시간 복잡도

최악의 경우 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.

 

 

3. 선택 정렬(Selection Sort)

다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중, 최소값을 찾음
  2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

 

 

[ 코드 ]

static void selectionSort(int[] arr) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
      // 현재 인덱스를 최소값으로 가정
      int minIndex = i;

      // 현재 인덱스 이후의 원소들 중에서 최소값 찾기
      for (int j = i + 1; j < n; j++) {
          if (arr[j] < arr[minIndex]) {
              minIndex = j;
          }
      }

      // 최소값과 현재 위치의 원소 교환
      int temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
  }
}

 

 

시간 복잡도

최악의 경우 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.