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.
Nội dung trích xuất từ tài liệu:
Lecture Data Structures & Algorithms: Chapter 4 DONG NAI UNIVERSITY OF TECHNOLOGYData Structures & Algorithms 1 DONG NAI UNIVERSITY OF TECHNOLOGY SortingTechniques 2 DONG NAI UNIVERSITY OF TECHNOLOGY BUBBLE SORTSELECTION SORTINSERTION SORT QUICK SORT 3DONG NAI UNIVERSITY OF TECHNOLOGY 4 DONG NAI UNIVERSITY OF TECHNOLOGYWhy sort??? a) By keeping a data file sorted, we can dobinary search on it. b) Doing certain operations, like matchingdata in two different files, become muchfaster.There are various methods for sorting:Bubble sort, Insertion sort, Selection sort,Quick sort, Heap sort, Merge sort…. Theyhaving different average and worst casebehaviors. 5 DONG NAI UNIVERSITY OF TECHNOLOGY BUBBLE SORTIntroduction:Bubble sorting is a simple sortingtechnique in which we arrange theelements of the list by forming pairs ofadjacent elements. That means we formthe pair of the (i) th and (i+1)th element. Ifthe order is ascending, we interchange theelements of the pair if the first element ofthe pair is greater than the secondelement. 6 DONG NAI UNIVERSITY OF TECHNOLOGY1 Swap 1 1 5 4 80 7 5 1 No Swap 1 15 4 8 0 7 5 Swap 1 1 15 4 8 0 7 5 Swap 1 1 15 4 8 0 7 5 Bubble sort: end of First pass 7 DONG NAI UNIVERSITY OF TECHNOLOGY BUBBLE SORTvoid bsort(int arr[], int n){ for(int i=0;i DONG NAI UNIVERSITY OF TECHNOLOGY SELECTION SORTSelection sort is a simplicity sortingalgorithm. It works as its name as itis. Here are basic steps of selectionsort algorithm:1. Find the minimum element in thelist2. Swap it with the element in thefirst position of the list3. Repeat the steps above for allremainder elements of the liststarting at the second position. 9 DONG NAI UNIVERSITY OF TECHNOLOGYSELECTION SORT 10 DONG NAI UNIVERSITY OF TECHNOLOGYSELECTION SORT 11 DONG NAI UNIVERSITY OF TECHNOLOGY SELECTION SORTvoid 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; } } How to run by hand??? swap(&arr[i], &arr[min]); 12 DONG NAI UNIVERSITY OF TECHNOLOGY INSERTION SORTIntroduction:Basic Idea: Insert a record R into asequence of ordered records:R1,R2,.., Ri with keys K1 DONG NAI UNIVERSITY OF TECHNOLOGYINSERTION SORT 14 DONG NAI UNIVERSITY OF TECHNOLOGYINSERTION SORT 15 DONG NAI UNIVERSITY OF TECHNOLOGY INSERTION SORTvoid InsertionSort(int M[],int n) { for(int i=1;i DONG NAI UNIVERSITY OF TECHNOLOGY QUICK SORTDivide list into 3 sub lists:- The Pivot element near the centerof the list : Pivot=arr[(i+i)/2]- The left Sub list is smaller thanPivot element- The Right Sub list is greater thanPivot elementWe partition recursion the left sublist and then the right sub list 17 DONG NAI UNIVERSITY OF TECHNOLOGYQUICK SORT 18 DONG NAI UNIVERSITY OF TECHNOLOGYQUICK SORT 19 DONG NAI UNIVERSITY OF TECHNOLOGYQUICK SORT 20