TAILIEUCHUNG - Lecture Data Structures & Algorithms: Chapter 4

Lecture Data Structures & Algorithms: Chapter 4 (Sorting Techniques) presented bubble sort, selection sort, insertion sort, quick sort and other content. Invite you to read the lecture. | Data Structures & Algorithms 1 Sorting Techniques BUBBLE SORT INSERTION SORT SELECTION SORT QUICK SORT Why sort??? a) By keeping a data file sorted, we can do binary search on it. b) Doing certain operations, like matching data in two different files, become much faster. There are various methods for sorting: Bubble sort, Insertion sort, Selection sort, Quick sort, Heap sort, Merge sort . They having different average and worst case behaviors. BUBBLE SORT Introduction: Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent elements. That means we form the pair of the (i) th and (i+1)th element. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element. 10 5 17 4 8 15 5 10 17 4 8 15 5 10 17 4 8 15 5 10 4 17 8 15 Swap Swap Swap No Swap Bubble sort: end of First pass void bsort(int arr[], int n) { for(int i=0;i arr[j]) swap(&arr[i],&arr[j]); } BUBBLE SORT How to run by hand??? SELECTION SORT Selection sort is a simplicity sorting algorithm. It works as its name as it is. Here are basic steps of selection sort algorithm: 1. Find the minimum element in the list 2. Swap it with the element in the first position of the list 3. Repeat the steps above for all remainder elements of the list starting at the second position. SELECTION SORT SELECTION SORT SELECTION SORT void selection_sort(int arr[], int n) { for (int i = 0; i < n ; i++) { int min = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[min]) { min = j; } } swap(&arr[i], &arr[min]); } } How to run by hand??? INSERTION SORT Introduction: Basic Idea: Insert a record R into a sequence of ordered records: R1,R2,, Ri with keys K1 <= K2 <= . <= Ki , such that, the resulting sequence of size i+1 is also ordered with respect to key values. INSERTION SORT INSERTION SORT INSERTION SORT void InsertionSort(int M[],int n) { for(int .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cơ sở dữ liệu
• Lecture Data Structures
• Data Algorithms
• Công nghệ thông tin
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp