정렬 1

정렬 1

기초 정렬

• 선택 정렬, 버블 정렬, 삽입 정렬 모두 O(N^2)

  // 버블 정렬
  #include<iostream>
  using namespace std;
  int main(void){
    int arr[5] = {13,-2,2,4,6};
    int n=5;
    for(int i=0;i<n;i++){
        for(int j=0;j<n-1-i;j++){
            if(arr[j]>arr[j+1]){
                int tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<arr[i]<<' ';
    }
    return 0;
  }
  

  Merge Sort

• 시간복잡도: O(NlogN)
• Stable Sort: 우선순위가 같은 원소가 여러개인 경우 처음 상태 그대로 가는 경우
• Merge Sort는 Stable Sort

  // Merge Sort
  #include<iostream>
  using namespace std;
  int n=10;
  int arr[1000001];
  int tmp[1000001];
  void merge(int st, int en){
    int mid = (st+en)/2;
    int lidx=st;
    int ridx=mid;
    for(int i=st;i<en;i++){
        if(ridx==en){
            tmp[i]=arr[lidx++];
        }
        else if(lidx==mid){
            tmp[i]=arr[ridx++];
        }
        else if(arr[lidx]<=arr[ridx]){
            tmp[i]=arr[lidx++];
        }
        else{
            tmp[i]=arr[ridx++];
        }
    }
    for(int i=st;i<en;i++){
        arr[i]=tmp[i];
    }
  }
  void mergesort(int st,int en){
    if(en==st+1){
        return;
    }
    int mid=(st+en)/2;
    mergesort(st,mid);
    mergesort(mid,en);
    merge(st,en);
  }
  int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    mergesort(0,n);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<' ';
    }
    return 0;
  }
  

  Quick Sort

• 일반적으로는 가장 빠름
• 그러나 코테에서 STL을 못쓰는 경우 merge sort 구현하기 (heap sort등 다른것도 사용 가능. Quick sort만 절대 구현X)
• pivot을 이용
• 추가적인 공간이 필요하지 않음(In-Place Sort)
• 배열 안에서의 자리 바꿈만으로 처리가 되기 때문에 cache hit rate가 높아서 속도가 빠름
• pivot이 항상 이상적인 위치에 있는 경우 시간복잡도는 O(NlogN)
• 거의 정렬이 된 경우에서 퀵소트를 사용하면 pivot이 계속 제일 앞에만 위치해서 단계가 N개가 되어 시간복잡도가 O(N^2)

  // Quick Sort
  #include<iostream>
  using namespace std;
  int n=10;
  int arr[1001]={6,-8,1,12,8,3,7,-7,5,2};
  void quicksort(int st,int en){
    if(en<=st+1){
        return;
    }
    int pivot=arr[st];
    int l=st+1;
    int r=en-1;
    while(1){
        while(l<=r && arr[l]<=pivot){
            l++;
        }
        while(l<=r && arr[r]>=pivot){
            r--;
        }
        if(l>r){
            break;
        }
        int tmp=arr[l];
        arr[l]=arr[r];
        arr[r]=tmp;
    }
    int tmp=arr[0];
    arr[0]=arr[r];
    arr[r]=tmp;
    quicksort(st,r);
    quicksort(r+1,en);
  }
  int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    quicksort(0,10);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<' ';
    }
    return 0;
  }
  

  Merge Sort vs Quick Sort

  Merge Sort

• 시간복잡도: O(NlogN)
• 추가적으로 필요한 공간: O(N)
• Stable Sort 여부: O

  Quick Sort

• 시간복잡도: 평균은 O(NlogN), 최악 O(N^2) 단 평균적으로 Merge Sort보다 빠름
• 추가적으로 필요한 공간: O(1)
• Stable Sort 여부: X