Xem mẫu
- Lecture No.45
Data Structures
Dr. Sohail Aslam
- Divide and Conquer
What if we split the list into two parts?
10 12 8 4 2 11 7 5
- Divide and Conquer
Sort the two parts:
10
4 12
8 10
8 12
4 2 11
5 7 11
5
- Divide and Conquer
Then merge the two parts together:
24 48 10
5 12
7 82 10
5 11
7 11
12
- Analysis
To sort the halves (n/2)2+(n/2)2
To merge the two halves n
So, for n=100, divide and conquer takes:
= (100/2)2 + (100/2)2 + 100
= 2500 + 2500 + 100
= 5100 (n2 = 10,000)
- Divide and Conquer
Why not divide the halves in half?
The quarters in half?
And so on . . .
When should we stop?
At n = 1
- Divide and Conquer
Recall: Binary Search
Search
Search
Search
- Divide and Conquer
Sort
Sort Sort
Sort Sort Sort Sort
- Divide and Conquer
Combine
Combine Combine
- Mergesort
Mergesort is a divide and conquer algorithm
that does exactly that.
It splits the list in half
Mergesorts the two halves
Then merges the two sorted halves together
Mergesort can be implemented recursively
- Mergesort
The mergesort algorithm involves three steps:
• If the number of items to sort is 0 or 1, return
• Recursively sort the first and second halves
separately
• Merge the two sorted halves into a sorted
group
- Merging: animation
4 8 10 12 2 5 7 11
2
- Merging: animation
4 8 10 12 2 5 7 11
2 4
- Merging: animation
4 8 10 12 2 5 7 11
2 4 5
- Merging
4 8 10 12 2 5 7 11
2 4 5 7
- Mergesort
Split the list in half. Mergesort the left half.
10 4 8 12 11 2 7 5
Split the list in half. Mergesort the left half.
10 4 8 12
Split the list in half. Mergesort the left half.
10 4
Mergesort the right.
10 4
- Mergesort
10 4 8 12 11 2 7 5
10 4 8 12
Mergesort the right half. Merge the two halves.
10
4 10
4 8 12
Merge the two halves.
8 12
- Mergesort
10 4 8 12 11 2 7 5
Merge the two halves.
10
4 84 10
8 12
Mergesort the right half. Merge the two halves.
10
4 10
4 8 12
- Mergesort
Mergesort the right half.
4 8 10 12 11 2 7 5
11 2 7 5
11 2
11 2
- Mergesort
Mergesort the right half.
4 8 10 12 11 2 7 5
11
2 11
2 7 5
11
2 11
2
nguon tai.lieu . vn
