칸비

개발 찍어먹기

[Algorithm] - 정렬의 모든 것(Sort)

내용

모든 정렬에 대한 정리를 해보겠다.

코드는 ‘n개를 입력받아 오름차순으로 정렬함’을 기준으로 한다.

Quick-Sort [퀵정렬]

퀵정렬은 말그대로 빠른 정렬이다.

퀵정렬에는 기준을 잡는 값 pivot이 있다.

복잡도

  • 평균 시간 복잡도 : O(N*LogN)
  • 최악 시간 복잡도 : O(N^2)

퀵정렬이라는 이름답게 평균적으로 빠르고 자주쓰인다.

하지만 최악의 경우 엄청 오래 걸린다.

코드

#include <stdio.h>

void sort(int *arr, int start, int end){
    
    if(start>=end){//엇갈리면
        return;
    }
    
    int pivot = start;    //피봇
    int i = pivot+1;    //i는 피봇 다음원소
    int j = end;    //j는 마지막 원소
    int temp;
    
    while(i<=j){//i가 더 커지면 종료
        //피봇 보다 큰 값 만날 때 까지
        while(i<=end && arr[i]<=arr[pivot]){
            ++i;
        }
        //피봇 보다 작은 값 만날 때 까지
        while(j>start && arr[j]>=arr[pivot]){
            --j;
        }
        
        //위에서 계산된 i와 j가 만나거나 엇갈리면 종료
        if(i>=j) break;
        
        //두 원소 교환
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    //피봇 정렬 완료
    temp = arr[j];
    arr[j] = arr[pivot];
    arr[pivot] = temp;
    
    sort(arr, start, j-1);    //피봇 중심으로 왼쪽부분 분할
    sort(arr, j+1, end);    //피봇 중심으로 오른쪽부분 분할
}

int main(){
    
    int t;
    scanf("%d",&t);
    
    int arr[1001];
    for(int i=0;i<t;i++) scanf("%d",&arr[i]);
    
    sort(arr, 0, t-1);
    
    //출력
    for(int i=0;i<t;++i){
        printf("%d ", arr[i]);
    }
    
    return 0;
}

Merge-Sort [병합정렬]

병합정렬은 분할정복법을 사용한 알고리즘이다.

병합정렬은 배열을 작은크기로 줄이고 정렬하여 합치는 정렬방법이다.

복잡도

  • 평균 시간 복잡도 : O(N*LogN)
  • 최악 시간 복잡도 : O(N*LogN)

병합정렬은 최악의 경우에도 평균적인 시간복잡도를 가진다.

코드

# include <stdio.h>
# define MAX_SIZE 1000001
int sorted[MAX_SIZE];// 정렬된 값 담을 배열

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스

void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;//정렬될 인덱스

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){//왼쪽배열,오른쪽배열 인덱스들이 각 배열을 벗어나지 않을 경우
    if(list[i]<=list[j])//인덱스 i값이 작으면
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  if(i>mid){//왼쪽배열 인덱스가 왼쪽배열 벗어날 경우
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];//오른쪽배열 남은 값 복사
  }
  else{//오른쪽배열 인덱스가 오른쪽배열 벗어날 경우
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];//왼쪽배열 남은 값 복사
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
      mid = (left+right)/2; // 중간 위치를 계산
      
    merge_sort(list, left, mid); // 앞쪽 부분 나누기
    merge_sort(list, mid+1, right); // 뒤쪽 부분 나누기
      
    merge(list, left, mid, right);//정렬 후 배열 합하기
  }
}

int main(){
    int t;
    scanf("%d",&t);
    
    int list[MAX_SIZE];
    for(int i=0;i<t;i++) scanf("%d", &list[i]);
  
    merge_sort(list, 0, t-1);

    for(int i=0; i<t; i++){//출력
        printf("%d\n", list[i]);
    }
}

요약

  • 아직 더올릴거다.

참고