TAILIEUCHUNG - Lecture Data Structures: Lesson 44

Lecture Data Structures: Lesson 44 provide students with knowledge about sorting; sorting integers; elementary sorting algorithms: selection sort, insertion sort, bubble sort; selection sort; swap action (selectionsorting); selection sort analysis; lighter bubbles rise to the top; . | Sorting Lecture Data Structure Dr. Sohail Aslam Sorting Integers How to sort the integers in this array 20 8 5 10 7 5 7 8 10 20 Elementary Sorting Algorithms Selection Sort Insertion Sort Bubble Sort Selection Sort Main idea find the smallest element put it in the first position find the next smallest element put it in the second position And so on until you get to the end of the list Selection Sort Example a 19 5 7 12 00 11 22 33 a 5 19 7 12 0 1 2 3 a 5 7 19 12 0 1 2 3 a 5 7 12 19 0 1 2 3 a 5 7 12 19 0 1 2 3 Selection Sort Code void selectionSort int arr int N int posmin count tmp for count 0 countSelection Sort Code int findIndexMin int arr int start int N int posmin start int index for index start index lt N index if arr index Swap Action SelectionSorting 20 8 5 10 7 5 8 20 10 7 5 7 20 10 8 5 7 8 10 20 5 7 8 10 20 Selection Sort Analysis What is the time complexity of this algorithm Worst case Best case Average case Each iteration performs a linear search on the rest of the array first element N second element N 1 penultimate element 2 last element 1 Total N N 1 2 N2 N 2 Insertion Sort Basic idea sorting cards Starts by considering the first two elements of the array data if out of order swap them Consider the third element insert it into the proper position among the first three elements. Consider the forth element insert it into the proper position among the first four elements. Insertion Sort Example a 19 12 5 7 0 1 2 3 a 12 19 5 7 0 1 2 3 a 5 12 19 7 0 1 2 3 a 5 7 12 19 0 1 2 3 Insertion Sort Code void insertionSort int arr int N int pos count val for count 1 count lt N count val arr count for pos count-1 pos gt 0 pos- if arr pos gt val arr pos 1 arr pos else break arr pos 1 val Insertion Sort animation count val pos a 19 12 5 7 1 12 0 0 1 2 3 a 19 12 19 5 7 1 12 1 0 1 2 3 a 19 12 19 5 7 0 1 2 3 a 12 19 5 7 0 1 2 3 Insertion Sort animation cont count val pos a 12 19 5 7 2 5 1 0 1 2 3 a 12 19 19 5 7 2 5 0 0 1 2 3 a 12 19 12 19 7 2 5 1 0 1 2 3 a 12 5 12

• Cơ sở dữ liệu
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Data structures
• Sorting integers
• Elementary sorting algorithms
• Selection sort analysis
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Programming assignments
• Data structures organize data
• Resource constraints
• Abstract data types
• Tree data structure
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Fundamental data structures
• Computational complexity
• Complexity of algorithms
• Data structure
• Pointers to structures
• Pointers to classes
• Josephus problem
• List data structures
• Doubly linked list
• Circularly linked list
• Code for simulation
• Priority queue
• Tree data structures
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming