linearSelect (A, p, r, i)
▷ 배열 A[p ... r]에서  i 번째 작은 원소를 찾는다 
{ 
    ① 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 
    ② 전체 원소들을 5개씩의 원소를 가진           개의 그룹으로 나눈다. 
        (원소의 총수가 5의 배수가 아니면 이중 한 그룹은 5개 미만이 된다.) 
    ③ 각 그룹에서 중앙값을 (원소가 5개이면 3번째 원소) 찾는다. 
         이렇게 찾은 중앙값들을  m1, m2, …, m      이라 하자. 
    ④ m1, m2, …, m     들의 중앙값 M을 재귀적으로 구한다. 원소의 총수가          
        홀수면 중앙값이 하나이므로 문제가 없고, 원소의 총수가 짝수일 
        경우는 두 중앙값 중 아무거나 임의로 선택한다.▷ call linearSelect( ) (여기서의 중앙갑 출력)
    ⑤ M을 기준원소로 삼아 전체 원소를 분할한다(M보다 작거나 같은 것은 
         M의 왼쪽에, M보다 큰 것은 M의 오른쪽에 오도록). 
    ⑥ 분할된 두 그룹 중 적합한 쪽을 선택하여 단계 ①~⑥을 재귀적으로 
         반복한다.                    ▷ call linearSelect( ) 
} 

intput : 33(총 개수)  5(찾고자 하는값)

intput : 1 2 55 41 69 85 32 68 20 7 45 54 86 99 102 31 22 77 44 50 52 89 61 37 6 9 78 46 28 23 94 56 11 (배열에 들어가는 수)

output : 28 41 44 11 (중앙값들)

설명하자면.. 위에 규칙에 따라서 출력값이 밑에 4개 숫자가 나와야 된다는 간단한 알고리즘인데...
(최악의 경우 선형시간 선택 알고리즘)

제 논리로 머가 틀린지 모르겠습니다..

좀 봐주세요..

1 2 55 41 69          1 2 41 55 69 (정렬)   (41 (중앙값))                          

85 32 68 20 7         7 20 32 68 85 (정렬)   (32  (중앙값))

45 54 86 99 102       45 54 86 99 102 (정렬)  (86  (중앙값)) 

31 22 77 44 50        22 31 44 50 77 (정렬)  (44  (중앙값)) 

52 89 61 37 6         6 37 52 61 89 (정렬)   (52  (중앙값)) 

9 78 46 28 23         9 23 28 46 78 (정렬)   (28 (중앙값)) 

94 56 11              11 56 94 (정렬)       (56 (중앙값)) 


41 32 86 44 52 28 56 (정렬)

28  32  41  44  52  56  86   //44//(중앙값에 중앙값) <-------------제 생각이 맞다면 여기서 28이 나와야 합니다. 계속 해도 44는 나올지 몰라도

 

나머지 숫자가 어차피 안나옵니다.


1 2 41 32 20 7 31 22 37 6 9 28 23 11 //44// 55 69 85 68 45 54 86 99 102 77 50 52 89 61 78 46 94 56 

1 2 41 32 20   1 2 20 32 41    20

7 31 22 37 6    6 7 22 31 37     22

9 28 23 11     9 11 23 28     11