C Programming
C Programming
Basic – week 10
Basic – week 10
2
Nội dung
Nội dung
•Các giải thuật sắp xếp cơ bản
–Sắp xếp chèn
–Sắp xếp lựa chọn
•Sắp xếp vun đống
3
Sắp xếp chèn
Sắp xếp chèn
•Kĩ thuật xếp bài
•Quy tắc
–Tìm phần tử chưa sắp xếp đầu tiên
–Đưa nó đến vị trí đúng
–Độ phức tạp: O(n2)
4
23 78 45 8 32 56
unsorted
Original
List
23 78 45 8 32 56
unsorted
Apter
step 1
23 78
45 8 32 56
unsorted
Apter
step 2
sorted
832 56
23 78
45
unsorted
832 56
unsorted
23 78
45
sorted
Apter
step 3
832 56
unsorted
23 78
45
sorted
Apter
step 4
Apter
step 5
5
Insertion Sort
Insertion Sort
void insertion_sort(element list[], int n)
{
int i, j;
element next;
for (i=1; i<n; i++) {
next= list[i];
for (j=i-1;j>=0 && next.key<
list[j].key;
j--)
list[j+1] = list[j];
list[j+1] = next;
}
}