Selection algorithms

• Definition
  • 주어진 도메인 안에서 i번째 작은 수(또는 큰 수)를 찾는 것.
• Quick sorting시 pivot 선정에서 worst case avoidance로 쓰임 (n시간 안에 정확히 중간 값을 찾기 때문에)
• types
  • Average linear time
    • 알고리즘 복잡도, 평균 O(n), worst case O(n²)
  • Guarantee average linear time in worst case.
    • O(n)

     

     

Average linear time selection

• How to
  • endIdx를 pivot으로 하여 파티션을 나눔
  • 파티션 때 pivot의 랭킹(몇 번 째 순위의 숫자인가)이 정해짐.
  • 랭킹이 적절하지 않으면 해당 값의 좌 우로 recursion
• Pseudo

  //

  //        array, 입력배열

  //        startIdx, 배열의 시작 index

  //        endIdx, 배열의 끝

  //        i, i번째 작은 인덱스를 찾음.

  //

  Select(array, startIdx, endIdx, i)

  if startIdx = endIdx

  return array[p]

     

  //

  //        quick sorting과 마찬가지로 partition을 나눔.

  //

  partIdx := partition(array, startIdx, endIdx)

  rankNum := partIdx - startIdx + 1

  if i = rankNum

  return array[partIdx]

  else if i < rankNum

  return Select(array, startIdx, partIdx - 1)

  else

  return Select(array, partIdx + 1, endIdx)

     

     

• Example
  • 2번째 작은 값을 찾을 때.
  • 

Median finding algorithms

• Deterministic Selection algorithms
• K번째 작은 값을 O(n)안에 찾아냄.
• Divide and Conquer 전략을 사용하며 작은 단위로 구분하여 런 타임 시간을 현저하게 줄임
• How to
  • 주어진 배열의 사이즈가 특정 숫자 크기(주로 5를 사용)보다 작은 경우면 단순히 sorting 하고 K번째 값을 return.
  • 주어진 숫자만큼의 element를 가지는 배열로 그룹화.
  • 각 그룹을 sorting하고 각 그룹의 median 값을 찾음.
  • 그 중에서 median 값을 구함.
  • 전체 element를 뒤지면서 찾은 median값 보다 작은 set을 L로 큰 set은 R로 구분하여 정리.
  • 정리된 set의 사이즈를 k와 비교하여 k원소가 있을 set에서 다시 recursion
• Pseudo

  FindingMedian(array, k)

          if array.size < k

                  sort(array)

                  return array[k]

            

          group(array, subsets)

            

          loop i := [0, array.size / 5)

                  medianSets[i] := FindingMedian(subsets[i], 3)

            

          //

          //        group.size = array.size / 5

          //        median of median group.size / 2

          //

          medianVal = FindingMedain(medianSets, array.size / 10)

            

          partition(array, LSet, Rset, medianVal)

          if k < LSet.size

                  return FindingMedian(LSet, k)

          else if k LSet.size + 1

                  return FindingMedean(RSet, k - LSet.size - 1)

          else

                  retrun medianVal

   

• Example
  • Element를 5이하로 가지는 그룹을 생성하는 step
     
  • 
  • Sorting후 median들을 정리 하는 단계
     
  • 
  • Median중에서 median을 선택한 단계.
     
  • 
  • Median of median으로 구분된 배열을 형성하는 단계
     
  •