6
: :.
(Internal sort) (External sort) (main memory). :,,..
6.1 (Bubbble Sort).,,.
1 (pass). 1 pass, 1. (, ), 90 (, ).
2 40-50 50-90, 50 10. 50 90. 40 50 10 비교 40 50 10 비교 40 50 10 40 10 50 40 10 50 90 90 90 90 90
40 10, 40-50 50-90. 40 50. 40 10 비교 40 10 10 40 10 40 50 50 50 50 90 90 90 90
n (n-1). BubbleSort : n A : A 1. for pass = 1 to n-1 2. for i = 1 to n-pass 3. if (A[i-1] > A[i]) // 4. A[i-1] A[i] //. 5. return A
Line 1: for- (n-1). Line 2 for- A[0] A[npass]. (n-pass) pass=1 A[n-1], pass=2 A[n-2], pass=1 A[n-1] A[n-2]. pass=3, 2 A[n-2] A[n-3]. Line 3~4: if- (A[i-1] > A[i]),,, A[i-1] A[i]. if- i.
for- for-, pass=1 (n-1), pass=2 (n-2), pass=n-1 1. : (n-1) + (n-2) + + 1 = n(n-1)/2 for- if- O(1). : n(n-1)/2xo(1) = O(n 2 )xo(1) = O(n 2 )
6.2 (Selection Sort) 0, 0, 1. 2.
40 70 60 30 10 50 최솟값 40 70 60 30 10 50 10 70 60 30 40 50 최솟값 10 70 60 30 40 50 10 30 60 70 40 50
최솟값 10 30 60 70 40 50 10 30 40 70 60 50 최솟값 10 30 40 70 60 50 10 30 40 50 60 70 최솟값 10 30 40 50 60 70
10. 10 40. 10 30. 30 70..
SelectionSort : n A : A 1. for i = 0 to n-2 { 2. min = i 3. for j = i+1 to n-1 { // A[i]~A[n-1]. 4. if (A[j] < A[min]) 5. min = j } 6. A[i] A[min] // min } 7. return A
Line 1 for- i 0 (n-2), A[i] A[n-1] (n-1) (n-1) line 3 j i+1 = (n-1)+1 = n Line 2: A[i],, min = i Line 3 for- A[i+1] 1 A[min], A[min] min = j, A[n-1] min. Line 6: line 3~5 for- A[min] A[i]. Line 7: line 1~6 for-, A.
line 1 for- (n-1), i=0 line 3 for- (n-1), i=1 line 3 for- (n-2),, 1 line 4~5 : (n-1)+(n-2)+(n-3)+ +2+1 = n(n-1)/2 if- O(1), : n(n-1)/2 x O(1) = O(n 2 )
,,,., (input insensitive).
6.3 (Insertion Sort) ( ) ( ),.
, 1, 1.,,.,.
InsertionSort 1. for i = 1 to n-1 { 2. CurrentElement = A[i] // 3. j i 1 // 4. while (j >= 0) and (A[j] > CurrentElement) { 5. A[j+1] = A[j] // 6. j j -1 } 7. A [j+1] CurrentElement } 8. return A
A[0], line 1 CurrentElement i for- 1 (n-1). Line 2: A[i] CurrentElement. Line 3: j=i-1 j.
Line 4~6: CurrentElement. while- (j >= 0) j, 2 (A[j] > CurrentElement) A[j] CurrentElement A[j] 1. line 5. Line 6 j 1 while-
Line 7: A[j+1] CurrentElement. while- A[j] CurrentElement A[j] (, A[j+1]) CurrentElement.
line 1 for- (n-1), i=1 while- 1, i=2 2,, (n-1) line 5~6 : 1 + 2 + 3 + + (n-2) + (n-1) = n(n-1)/2 O(1), : n(n-1)/2 x O(1) = O(n 2 )
., CurrentElement, while-. (n-1). O(n)..
( ) O(n 2 )..
6.4,., ( ).,,, 1.
(Shell sort),,.
. 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80 (gap) 5. 15, 30, 5 80, 80 5 50.
, [30, 80, 50]. 2 [60, 40, 30], [90, 20, 40], [10, 10, 90], [40, 60, 80]. 1. 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80
5, 80 90, 20 30.
5,, 3, 3. 5. 1.., 1,.
ShellSort 1. for each gap h = [ h 0 > h 1 >... > h k =1] // gap 2. for i = h to n-1 { 3. CurrentElement=A[i]; 4. j = i; 5. while (j>=h) and (A[j-h]>CurrentElement) { 6. A[j]=A[j-h]; 7. j=j-h; } 8. A[j]=CurrentElement; } 9. return A
InsertionSort 1. for i = 1 to n-1 { 2. CurrentElement = A[i] // 3. j i 1 // 4. while (j >= 0) and (A[j] > CurrentElement) { 5. A[j+1] = A[j] // 6. j j -1 } 7. A [j+1] CurrentElement } 8. return A
[ h 0 > h 1 > > h k =1]. h 0 line 2~8. h k 1.,.
Line 2~8 for- h,.
, line 2 for- i h 1 CurrentElement A[i]. Line 5~7 while- CurrentElement. while- (j>=h) j h (j-h),. 2 (A[j-h] > CurrentElement) (j-h) CurrentElement A[j-h] line 6 A[j-h] h (, A[j]=A[j-h]).
while- line 8 CurrentElement A[j]. while- (j-h), A[j]. A[j-h] CurrentElement. line 8 CurrentElement A[j].
5,
h=5. 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80 h=3, 3. 1 0, 3, 6, 9, 12, 2 1, 4, 7, 10, 13, 3 2, 5, 8, 11, 14.,
1 2 3 1 2 3 30 30 20 10 30 10 10 40 50 30 40 2 0 40 40 1 0 40 40 50 60 80 60 60 80 6 0 90 90 80 90 90 80., h=3. 10 30 10 30 40 20 40 40 50 60 80 60 90 90 80
h=1. h=1 1 (, 1 ),. 10 10 20 30 30 40 40 40 50 60 60 80 80 90 90. : 1, 4, 10, 23, 57, 132, 301, 701 701.
O(n 2 ). (Hibbard) : 2 k -1 (, 2 k -1,, 15, 7, 5, 3, 1), O(n 1.5 ). O(n 1.25 )..
. (Embedded), H/W.
6.5 (heap) (Complete Binary Tree).. (priority). ( )..
n, log 2 n,..
A, A[0], A[1] A[n]. 90 A[1], 60 80 A[2] A[3], 50, 30, 70, 10 A[4] A[7], 20 40 A[8] A[9].
A[i] = A[i/2], i, i/2., A[7] A[7/2] = A[3]. A[i] = A[2i] A[i] = A[2i+1] A[4] A[2i] = A[2x4] = A[8], A[2i+1] = A[2x4+1] =A[9].
(Heap Sort). (maximum heap).,.,., 1...
HeapSort : A[1] A[n] A : A 1. A. 2. heapsize = n // 3. for i = 1 to n-1 4. A[1] A[heapSize] // 5. heapsize = heapsize -1 // 1 6. DownHeap() //. 7. return A
Line 1: A[1..n]. Line 2: heapsize n. Line 3~6 for- (n-1), A[1],. Line 4:.,. Line 5: 1.
Line 4. Line 6 DownHeap. DownHeap: r. r r. r, r..
DownHeap Line 4 40 90, (heapsize) 1.
40 (60 80) 80 40.
40 (70 10) 70, 70 40. DownHeap.
DownHeap HeapSort 80 20 DownHeap ( ) 70 10 DownHeap ( )
60 20 DownHeap ( ) 50 20 DownHeap ( )
40 10 DownHeap ( ) 30 10 DownHeap ( )
1. for-, 1.
Line 1: O(n) Line 2: O(1) Line 3~6 for- (n-1), line 4~5 O(1) DownHeap, log 2 n O(logn). : O(n) + (n-1) x O(logn) = O(nlogn)
6.6,,,,,,. (Comparison Sort). (Radix Sort). ( ).
(lower bound). [ ]..
n?. (n-1) n 1., (n-1).
n,,. 3 x, y, z,.
2,, ( ). (Decision Tree). 3! = 6. (binary tree)..
3! 3 3!. 1.,. 3 3. 3.
n. 3 3. 2, 4 3. n. k logk. n! log(n!).
log(n!) = O(nlogn), O(nlogn)., O(nlogn). Ω(nlogn).
6.7 (Radix Sort),. (radix)., 10 (radix) 0, 1, 2,, 9, 2 (radix) 0, 1...
5 3, 1. 10.. 10 3 131 035, 10 131 035. 10 035 131? 1.
, (stability). 2 10, (stable sort),.
RadixSort : n r k : 1. for i = 1 to k 2. i. 3. return A
Line 1 for- 1 k. Line 2 i. r, i 0 1 (r-1) i 0 (r-1).
i=1, 1, 9, 0, 5, 1, 0, 1 0 2, 1 1, 5 1, 9 1. 1 0 070 910, 1 131, 5 035, 9 089.
for- k., k. n i, r, O(n+r). O(k(n+r)). k r n, O(n).
, 4, n=2 32, r=2 4,, 16, k=8,, 8 16. O(k(n+r)) = O(8x(2 32 +16)). 8 16 2 32, O(2 32 ) = O(n). RadixSort 1 k, Least Significant Digit (LSD) RL (Rightto-Left). k 1 Most Significant Digit (MSD) LR (Left-to-right).
,,, 128 (, ),. (Parallel). -( )
6.8 (External Sort). (Internal Sort), ( )., 1GB, 100GB,.
,., 100GB 1GB,,., 100.
(100GB ). (merge).,,..
1GB 2 2GB 1
98 49, 2GB 50. 2GB 2 25, 4GB 25., 2 1/2 100GB 1.
..., M.. HDD.
ExternalSort : HDD : HDD 1. HDD M HDD. HDD HDD, HDD HDD. 2. while ( HDD > 1 ) 3. HDD 2,. HDD., HDD HDD. 4. HDD. 5. return HDD
Line 1: HDD M HDD. N, N/M., N M. HDD HDD, HDD HDD. Line 2 while- HDD 2, line 3~4. Line 3: HDD 2,.
line 3, HDD 2M. line 3 4M., line 3 2 HDD. Line 4: HDD., HDD HDD, HDD HDD.
128GB 1GB ExternalSort. Line 1: 1GB 128 HDD. Line 3: 2GB 64 HDD. Line 3: 4GB 32 HDD. Line 3: 8GB 16 HDD. Line 3: 64GB 2 HDD. Line 3: 128GB 1 HDD, while- line 5 HDD.
( ). (pass). line 3 HDD HDD., 1. while-.
N, M, line 3 2M, 4M,, 2 k M (2 ). 1 2 k M, 2 k M = N. k while-. 2 k = N/M, k = log 2 (N/M). O(log(N/M)).
tape driver https://www.youtube.com/watch?v=cel8wnw5uvs
ExternalSort 2. 2., (Tape Drive), 2. 1 [10 30 60 70], 2 [20 40 50 80], 2 1 10, 2 20.
, 2 20 1 30. ExternalSort line 3 2 2. 8 (TD) 0 1 4 2, 1.
Pass 1 TD 0 TD 1 1 TD 2 3. Pass 2 TD 2 TD 3 1 TD 0 1. Pass 3 TD 0 TD 1 1 TD 2.
ExternalSort 2 2- way (merge). 2-way (Multi-way p- way Merge), O(log p (N/M)). 2p. (p+1) p-way (Polyphase Merge).
/ DB, DB /, IP, DB
(Internal sort) (External sort). (main memory),,,. (Bubble Sort), O(n 2 ).
(Selection Sort), O(n 2 ). (Insertion Sort), O(n 2 ). O(n), O(n 2 ). (Shell Sort),. O(n 2 ).
(Heap Sort), O(nlogn). (Lower Bound) O(nlogn). (Radix Sort). O(k(n+r))., k, r (radix, ). (External Sort). (p-way Merge) (Polyphase Merge).
#9 : 6 1, 5, 6, 7, 9, 10, 13,. : 5 30