정렬 알고리즘

개요

버블 정렬(Bubble Sort)

1. 정렬되지 않은 영역을 루프 범위로 설정한다.

2. 인접한 두 값을 비교한다.

3. swap 조건에 부합하는 경우 swap을 수행한다.

4. 루프 범위 내에서 2~3번을 반복한다.

5. 비교 대상이 없을 때까지 1~4를 반복한다.

void bubbleSort(int[] arr) {
  int temp = 0;
  for (int i = 0; i < arr.length; i++) { // 루프 범위에서 제외할 원소 개수
    for (int j = 1; j < arr.length - i; j++) {
      if (arr[j - 1] > arr[j]) {
	      // swap 연산
        temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  System.out.println(Arrays.toString(arr));
}

선택 정렬(Selection Sort)

1. 주어진 배열에서 최솟값을 찾는다.

2. 배열 맨 앞의 요소와 1번의 최솟값을 swap 한다.

3. 맨 앞 위치를 뺀 나머지 영역을 1~2번을 반복하며 교체한다.

void selectionSort(int[] arr) {
  int minIndex, temp;
  // 최솟값 찾기
  for (int i = 0; i < arr.length - 1; i++) {
    minIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // swap 연산 수행(최솟값 요소와 맨 앞 요소)
    temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

삽입 정렬(Insertion Sort)

1. 2번째 index의 값을 temp에 저장한다.

2. temp와 temp 앞에 있는 요소들과 비교하며 shift 연산을 수행한다.

3. 선택할 데이터가 더 이상 없을 때까지, 1번으로 돌아가 다음 index값을 temp에 저장하고 반복한다.

void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) { // 삽입할 위치 지정
    int temp = arr[i];
    int prev = i - 1;
    while ((prev >= 0) && (arr[prev] > temp)) { // shift 연산
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

퀵 정렬(Quick Sort)

1. 배열에서 기준값(pivot)을 선정한다.

2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 배열을 두 개로 나눈다(분할). 분할을 마친 후, 피벗은 더 이상 이동하지 않는다.

3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

 

public void quickSort(int[] array, int left, int right) {
  if (left >= right) return;
  
  int pivot = partition(); // 분할

  // 피벗 제외한 2개의 부분 배열을 대상으로 재귀 호출
  quickSort(array, left, pivot - 1); // 피벗 왼쪽 부분
  quickSort(array, pivot + 1, right); // 피벗 오른쪽 부분
}

public int partition(int[] array, int left, int right) {
  int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
  int i = left, j = right;

  while (i < j) {
	  // 오른쪽 끝에서부터 피벗보다 작거나 같은 값을 찾을 때까지 j를 왼쪽으로 이동
    while (pivot < array[j]) { 
      j--;
    }
    // 왼쪽 끝에서부터 피벗보다 큰 값을 찾을 때까지 i를 오른쪽으로 이동
    while (i < j && pivot >= array[i]) {
      i++;
    }
    swap(array, i, j); // 찾은 두 값을 교환
  }
  // 피벗을 자신의 위치로 이동
  array[left] = array[i];
  array[i] = pivot;

  return i; // 피벗의 최종 위치를 반환
}

private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

병합 정렬(Merge Sort)

public void mergeSort(int[] array, int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;

    mergeSort(array, left, mid); //중간값 포함 왼쪽 영역
    mergeSort(array, mid + 1, right); // 중간값 오른쪽 영역
    merge(array, left, mid, right); // 그룹 합치기
  }
}

public static void merge(int[] array, int left, int mid, int right) {
  int[] L = Arrays.copyOfRange(array, left, mid + 1);
  int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);

  int i = 0, j = 0, k = left;
  int ll = L.length, rl = R.length;

  // 두 배열을 병합하는 동안 요소를 비교하여 결과 배열에 추가
  while (i < ll && j < rl) {
    if (L[i] <= R[j]) {
      array[k] = L[i++];
    } else {
      array[k] = R[j++];
    }
    k++;
  }

  // 왼쪽 배열에 남아있는 모든 요소를 결과 배열에 추가
  while (i < ll) {
    array[k++] = L[i++];
  }
  // 오른쪽 배열에 남아있는 모든 요소를 결과 배열에 추가
  while (j < rl) {
    array[k++] = R[j++];
  }
}

힙 정렬(Heap Sort)

힙(Heap)

1. 최대 힙을 구성한다.

2. 현재 힙 루트(가장 위 노드)는 가장 큰 값이 존재한다. 루트의 값을 마지막 요소와 바꾸고, 힙의 사이즈를 하나 줄인다(마지막 요소 제거). 이 때, 큰 수부터 제거되므로 이를 저장해두면 정렬이 가능하다.

3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.

public void heapSort(int[] array) {
  int n = array.length;

  // 최대 힙 초기화
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(array, n, i); // 일반 배열을 최대 힙으로 구성
  }

  // extract 연산
  for (int i = n - 1; i > 0; i--) {
    swap(array, 0, i); // 루트와 마지막 요소 교환
    heapify(array, i, 0); // 요소 하나 제거 후 다시 최대 힙 구성
  }
}

public void heapify(int array[], int n, int i) {
    int p = i;
    int l = i*2 + 1;
    int r = i*2 + 2;

    //왼쪽 자식노드
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //오른쪽 자식노드
    if (r < n && array[p] < array[r]) {
        p = r;
    }

    //부모노드 < 자식노드
    if(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

기수 정렬(Radix Sort)

public static void radixSort(int[] array) {
  // 최대 자릿수를 구하기 위한 최대값 찾기
  int max = getMax(array);

  // 자릿수별로 정렬
  for (int exp = 1; max / exp > 0; exp *= 10) {
    countingSortByDigit(array, exp);
  }
}

private static int getMax(int[] array) {
  int max = array[0];
  for (int num : array) {
    if (num > max) {
      max = num;
    }
  }
  return max;
}

private static void countingSortByDigit(int[] array, int exp) {
  int n = array.length;
  int[] output = new int[n];
  int[] count = new int[10]; // 자릿수는 0부터 9까지

  // 해당 자릿수의 개수 세기
  for (int i = 0; i < n; i++) {
    int digit = (array[i] / exp) % 10;
    count[digit]++;
  }

  // 위치 계산 (누적합 구하기)
  for (int i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  // 출력 배열에 정렬된 값 배치 (계수 정렬(counting sort) 과정)
  for (int i = n - 1; i >= 0; i--) {
    int digit = (array[i] / exp) % 10;
    output[count[digit] - 1] = array[i];
    count[digit]--;
  }

  // 정렬된 배열을 원래 배열에 복사
  for (int i = 0; i < n; i++) {
    array[i] = output[i];
  }
}