알고리즘(Algorithm) 정리

Sort 알고리즘

- Bubble Sort

   서로 인접한 두 개의 원소를 비교하고, 조건을 만족하지 않는다면 서로 swap해 가며 정렬하는 알고리즘입니다. Stable sort 입니다. 모든 경우에 대해서 O(n^2)의 시간복잡도를 가집니다.

 

- Selection Sort

  위치가 이미 정해져 있고, 어떤 원소를 넣을 지 선택해가며 정렬하는 알고리즘입니다. Unstable sort 입니다. 모든 경우에 대해서 O(n^2)의 시간복잡도를 가집니다.

 

- Insertion Sort

  2번째 원소부터 시작하여, 앞에 있는 원소들과 비교해가며 삽입할 위치를 지정한 후, 원소들을 뒤로 옮기고 그 자리에 삽입하여 정렬하는 알고리즘입니다. Stable sort입니다. 최적의 경우 O(n), 최악의 경우O(n^2)의 시간 복잡도를 가집니다.

 

- Quick Sort

  분할정복을 사용해 정렬하는 알고리즘입니다. 배열 중 임의로 피벗 원소를 정합니다. 정한 피벗 원소 앞에는 피벗 원소의 값보다 모두 작게 하고, 뒤에는 피벗 원소의 값보다 모두 크게 하여, 피벗을 기준으로 두 개의 배열로 분할합니다. 분할된 두 개의 작은 배열에 대해서 이 작업을 재귀적으로 반복합니다.

 

  Unstable sort입니다. 평균 시간 복잡도는 O(nlgn)이며, 이미 정렬되어 있는 것과 같이 최악의 경우 분할이 잘 이루어 지지 않아서 시간 복잡도는 O(n^2)입니다.

 

1) 정복

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    
    // 분할 
    int pivot = partition(); 
    
    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

 

2) 분할

 public static index partition(index low, index high) {
 	index i, j, pivotPoint ; keytype pivotItem ;
	pivotItem = S[low] ;
    j = low ;
    
	for ( i = low + 1; i <= high; i++ ) {
      if (S[i] < pivotItem) {
      	exchange S[i] and S[++j] ; 
      }
    }
	pivotPoint = j ;
	exchange S[low] and S[pivotPoint] ;
    
	return pivotPoint;
}

 

- Merge Sort

  분할 정복을 사용해 정렬하는 알고리즘입니다. 배열의 각 원소가 하나가 될 깨까지 두 개로 계속 분할합니다. 이후 병합하는 과정을 거치며 정렬을 수행합니다. Stable sort입니다. 최적, 평균, 최악의 경우 시간 복잡도가 O(nlgn)입니다.

 

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    mergeSort(array, 0, array.length - 1);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static 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

  Complete binary tree를 기본으로하는 Heap 자료구조를 기반으로 합니다. 첫 번째로, max 힙을 구성합니다. 루트에는 가장 큰 값이 있으므로, 이를 꺼내고 힙의 맨 마지막 요소를 루트에 넣습니다. 힙의 크기가 1보다 크면 이를 반복하여 정렬을 수행합니다.

 

  Unstable sort입니다. 최적, 평균, 최악 시간복잡도의 경우 O(nlogn)입니다.

 

 

 

출처 : https://gyoogle.dev