intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Lecture Data Structures & Algorithms: Chapter 4

Chia sẻ: Na Na | Ngày: | Loại File: PPTX | Số trang:24

Thêm vào BST
Báo xấu
68
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Data Structures & Algorithms: Chapter 4

  1. DONG NAI UNIVERSITY OF TECHNOLOGY Data Structures & Algorithms 1
  2. DONG NAI UNIVERSITY OF TECHNOLOGY Sorting Techniques 2
  3. DONG NAI UNIVERSITY OF TECHNOLOGY BUBBLE SORT SELECTION SORT INSERTION SORT QUICK SORT 3
  4. DONG NAI UNIVERSITY OF TECHNOLOGY 4
  5. DONG NAI UNIVERSITY OF TECHNOLOGY 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. 5
  6. DONG NAI UNIVERSITY OF TECHNOLOGY 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. 6
  7. DONG NAI UNIVERSITY OF TECHNOLOGY 1 Swap 1 1 5 4 8 0 7 5 1 No Swap 1 1 5 4 8 0 7 5 Swap 1 1 1 5 4 8 0 7 5 Swap 1 1 1 5 4 8 0 7 5 Bubble sort: end of First pass 7
  8. DONG NAI UNIVERSITY OF TECHNOLOGY BUBBLE SORT void bsort(int arr[], int n) { for(int i=0;i
  9. DONG NAI UNIVERSITY OF TECHNOLOGY 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. 9
  10. DONG NAI UNIVERSITY OF TECHNOLOGY SELECTION SORT 10
  11. DONG NAI UNIVERSITY OF TECHNOLOGY SELECTION SORT 11
  12. DONG NAI UNIVERSITY OF TECHNOLOGY 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; } } How to run by hand??? swap(&arr[i], &arr[min]); 12
  13. DONG NAI UNIVERSITY OF TECHNOLOGY INSERTION SORT Introduction: Basic Idea: Insert a record R into a sequence of ordered records: R1,R2,.., Ri with keys K1
  14. DONG NAI UNIVERSITY OF TECHNOLOGY INSERTION SORT 14
  15. DONG NAI UNIVERSITY OF TECHNOLOGY INSERTION SORT 15
  16. DONG NAI UNIVERSITY OF TECHNOLOGY INSERTION SORT void InsertionSort(int M[],int n) { for(int i=1;i
  17. DONG NAI UNIVERSITY OF TECHNOLOGY QUICK SORT Divide list into 3 sub lists: - The Pivot element near the center of the list : Pivot=arr[(i+i)/2] - The left Sub list is smaller than Pivot element - The Right Sub list is greater than Pivot element We partition recursion the left sub list and then the right sub list 17
  18. DONG NAI UNIVERSITY OF TECHNOLOGY QUICK SORT 18
  19. DONG NAI UNIVERSITY OF TECHNOLOGY QUICK SORT 19
  20. DONG NAI UNIVERSITY OF TECHNOLOGY QUICK SORT 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2