Skip to content

Latest commit

 

History

History
154 lines (129 loc) · 4.19 KB

til-example-2.md

File metadata and controls

154 lines (129 loc) · 4.19 KB
Raw

정렬

정렬 알고리즘

  • Simple, low
    • bubble
    • insertion
    • seletion
  • Fast
    • Quick sort
    • Merge sort
    • Heap sort
  • Radix sort

Selection Sort

  • 가장 큰 값을 계속 정렬하고픈 위치로 보냄
    • 모든 데이터 값에 대해 계속 반복한다
  • 최악,최선,평균 시간 복잡도는 O(n^2)
    • for 루프는 n-1번 반복
    • 가장 큰 수를 찾기 위한 비교 횟수
      • n-1,n-2,n-2 ... 2,1
      • 교환은 상수 작업임

Bubble sort

  • 실행 시간은 O(n^2)
  • 1 회전마다 검색할 인덱스 값 범위 내에서 인접한 값의 크기를 비교해서 계속 바꿔 나간다
  • 수행 시간 계산
    • for 루프는 n-1 번 반복
    • for 루프는 각각 n-1,n-2....2,1 번 반복
    • 교환은 상수 시간 작업

Insertion Sort

  • k-1이 미리 정렬되어 있는 상태에서 k 번째 인덱스를 추가했을 때도 정렬되게 하려면 어떻게 해야할까?

  • 인덱스가 하나라면 정렬된 상태라 생각하자

  • 인덱스가 2개 이상이 되었다.

    • 그러면 작은 인덱스를 앞에 삽입하면 인덱스는 정렬된 상태가 된다

  • 최악의 시간 복잡도는 O(n^2), 최선의 경우 O(n)이다.

    • 최악의 경우 자기 앞의 모든 인덱스와 비교를 해야한다.
    • 운이 좋다면 비교를 끝낼 수 있다.

분할 정복법

Merge Sort

  • 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
  • 정복 : 각각 작은 문제를 순환적으로 해결
  • 합병 : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함

데이터가 저장된 배열을 절반으로 나누고 각각을 순환적으로 정렬한다 정렬된 두 개의 배열을 합쳐 전체를 정렬하는 것이다.

mergeSort(A[],p,r){
  if(p<r) then{
    q= (p+q)/2;
    mergeSort(A,p,q) // 전반부 정렬
    mergeSort(A,q+1,r) // 후반부 정렬
    merge(A,p,q,r) // 합병
  }
}
merge(A[],p,q,r){
  //정렬되어 있는 두 배열을 합하여 정렬된 하나의 A[p~r]을 만든다
}
void merge(int data[],int q,int r){
  int i=p,j=q+1,k=p;
  int temp[data.length()];
  while(i<=q &&j<=r){
    if(data[i]<=data[j]){
      temp[k++] = data[i++]
    else
      temp[k++]=data[j++]
    }
    while(i<=q)
      tmp[k++]=data[i++];
    while(j<=r)
      tmp[k++]=data[j++]
    for (int i=p;i<=r;i++)
      data[i]=tmp[i];
  }
}
  • 합병 정렬에서는 추가로 정렬된 값들을 저장할 배열이 필요함
  • 시간 복잡도를 계산하기 어렵다
    • n == 1이면 0
    • n != 1이면 2T(n/2) + n

quick sort

  • 분할 정복법을 사용합니다 ( merge sort와 유사하다)

    • 분할 : 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다
    • 정복 : 각 부분을 순환적으로 정렬한다
    • 합병 : nothing to do
      • 이미 정렬되어서 할게 없음

  • quick sort는 피봇을 선정해서 피봇보다 큰 값과 피봇보다 작은 값으로 인덱스를 분할합니다.

    • merge sort는 반반으로 쪼개지지만, quick sort는 반반 쪼갠다는 것을 보장할 수 없다.

  • 쪼개진 인덱스를 각각 quick sort로 정렬한다.

quick sort(A[],P,R)
{
  if(p<r)then{
    q = partition(A,p,r);
    quickSort(A,p,q-1);
    quickSort(A,q+1,r);
  }
}
partition(A[],p,r){
  배열 A의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치(q)를 반환한다
}
  • 어떻게 파티션할 것인지가 핵심이다
if A[J]>= X
    j <- j+1;
else
    i-< i+1;
    exchange A[i] and A[j];
    j <- j+1;
  • i는 pivot보다 작은 값들 중 마지막 값
  • j는 지금 검사하려는 값
  • A[j]가 pivot 보다 크다면 딱히 할게 없음 그냥 j를 다음으로 넘김
    • 이 말은 i ~ j의 인덱스까지는 pivot 보다 크다는 것을 자동 증명
  • A[j]가 pivot 보다 작다면 A[j]를 A[i]와 바꾼다
    • i의 인덱스를 증가시키면 pivot 보다 작은 값이 추가되었음을 알려준다.
    • j의 인덱스를 증가시키면 다음 비교 대상으로 넘어간다.
Partition(A,p,r)
{
  x<-A[r]
  i<-p-1
  for j<-p to r-1
  if A[j]<= x then
    i <- i+1
    exchange A[i] and A[j];
  exchange A A[i+1] and A[r];
  return i+1
}

25:03