정렬 알고리즘 (Sorting Algoritm) 개념 정리

⛳ Big O : 알고리즘 효율성 단위

⛳ 선택 정렬 (Selection Sort)

● 배열을 계속 순환하면서 적절한 값을 찾게 되면 현재 인덱스에 있는 값과 교환해줌

● 배열 전체를 비교하므로 시간 복잡도는 O(N^2) 이다.

● 단 하나의 배열로 정렬을 하는 것이기 때문에 공간복잡도는 O(N) 이다.

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

⛳ 삽입 정렬 (Insertion Sort)

● 자신보다 이전의 인덱스 값을 비교하면서 적절한 위치를 찾아가는 알고리즘

● 최악의 경우인 역으로 정렬되있을 때는 시간 복잡도가 O(N^2) 이지만, 이미 정렬 되있는 경우 시간 복잡도가 O(N) 이다.

● 단 하나의 배열로 정렬을 하는 것이기 때문에 공간복잡도는 O(N) 이다.

 

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){
      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux + 1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

⛳ 버블 정렬 (Bubble Sort)

● 자신의 앞쪽에 있는 인덱스하고 비교하면서 적잘한 위치를 찾아가는 알고리즘

● 선택 정렬과 마찬가지로 시간 복잡도가 O(N^2) 이다.

● 단 하나의 배열로 정렬을 하는 것이기 때문에 공간복잡도는 O(N) 이다.

void Bubble_Sort(int arr[], int len) {
  int i, j, tmp;
  for (i = 0; i < len - 1; ++i) {
    for (j = 0; j < len - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
}

⛳ 합병 정렬 (Merge Sort) ★

● 배열을 반씩 나누면서 더 이상 분할 할 수 없을 때까지 분할하고, 그 안에서 정렬을 진행한다. 그 다음 다시 배열을 합치면서 정렬이 된 배열끼리 다시 정렬을 하는 알고리즘

● 성능은 전반적으로 퀵 정렬보다 떨어지고 추가적인 메모리를 필요로 하지만, 데이터 상태에 크게 영향을 받지 않음

● 시간 복잡도는 O(NlogN), 공간 복잡도는 2n개

void mergeSort(int A[], int low, int high, int B[]){
    if(low >= high) return;

    int mid = (low + high) / 2;

    mergeSort(A, low, mid, B);
    mergeSort(A, mid+1, high, B);

    int i=low, j=mid+1, k=low;
    for(;k<=high;++k){
        if(j > high ) B[k] = A[i++];
        else if(i > mid) B[k] = A[j++];
        else if(A[i] <= A[j]) B[k] = A[i++];
        else B[k] = A[j++];
    }

    // 5. copy
    for(i=low;i<=high;++i) A[i] = B[i];
}

⛳ 퀵 정렬 (Quick Sort) ★

● 인덱스 한개를 기준(Pivot)으로 두고, Left는 기준으로 둔 값보다 작은 값, Right는 기준으로 둔 값보다 큰 값으로 정렬하는 알고리즘

● Pivot의 값을 잘못 선택하는 최악의 경우, 시간 복잡도는 O(n^2) 이기 때문에 데이터 상태에 따라 알고리즘 성능이 달라지긴 하나, 메모리의 제약을 받지 않음

● 일반적인 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int pivot = arr[(left + right) / 2];
      int temp;
	  
      while (i <= j)
      {
        while (arr[i] < pivot)	i++;
        while (arr[j] > pivot)	j--;
		
        if (i <= j)
        {
			// SWAP(arr[i], arr[j])
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
			
            i++;
            j--;
        }
      } 

    if (left < j)	quickSort(arr, left, j);
    if (i < right)	quickSort(arr, i, right);
}