Page 1
goupee.vn goupee.com Sorting applications Sorting algorithms are essential in a broad variety of applications Organize an MP3 library. Display Google PageRank results. Advanced Topics in Sorting List RSS news items in reverse chronological order. Find the median. Find the closest pair. Binary search in a database. anhtt-fit@mail.hut.edu.vn Identify statistical outliers. Find duplicates in a mailing list. dungct@it-hut.edu.vn Data compression. Computer graphics. Computational biology. Supply chain management. Load balancing on a parallel computer. http://www.4shared.com/file/79096214/fb2ed224/lect01.html . . . Sorting algorithms Which algorithm to use? Many sorting algorithms to choose from Applications have diverse attributes Stable? Internal sorts Multiple keys? Insertion sort, selection sort, bubblesort, shaker sort. Quicksort, mergesort, heapsort, samplesort, shellsort. Deterministic? Solitaire sort, red-black sort, splaysort, Dobosiewicz sort, psort, ... Keys all distinct? External sorts Multiple key types? Poly-phase mergesort, cascade-merge, oscillating sort. Linked list or arrays? Radix sorts Large or small records? Distribution, MSD, LSD. 3-way radix quicksort. Is your file randomly ordered? Parallel sorts Need guaranteed performance? Bitonic sort, Batcher even-odd sort. Smooth sort, cube sort, column sort. Cannot cover all combinations of attributes. GPUsort. fb.com/goupee.vn 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 2
goupee.vn goupee.com Case study 1 Case study 2 Problem Problem Sort a huge randomly-ordered file of small Sort a huge file that is already almost in records. order. Example Example Process transaction records for a phone Re-sort a huge database after a few company. changes. Which sorting method to use? Which sorting method to use? 1. Quicksort: YES, it's designed for this problem 1. Quicksort: probably no, insertion simpler and faster 2. Insertion sort: No, quadratic time for randomly- 2. Insertion sort: YES, linear time for most definitions ordered files of "in order" 3. Selection sort: No, always takes quadratic time 3. Selection sort: No, always takes quadratic time Case study 3 Duplicate keys Problem: sort a file of huge records with tiny keys. Often, purpose of sort is to bring records with duplicate keys Ex: reorganizing your MP3 files. together. Sort population by age. Which sorting method to use? Finding collinear points. 1. Mergesort: probably no, selection sort simpler and Remove duplicates from mailing list. faster Sort job applicants by college attended. 2. Insertion sort: no, too many exchanges 3. Selection sort: YES, linear time under reasonable Typical characteristics of such applications. assumptions Huge file. Ex: 5,000 records, each 2 million bytes with 100-byte Small number of key values. keys. Mergesort with duplicate keys: always ~ N lg N compares Cost of comparisons: 100 x 50002 / 2 = 1.25 billion Quicksort with duplicate keys Cost of exchanges: 2,000,000 x 5,000 = 10 trillion algorithm goes quadratic unless partitioning stops on equal keys! Mergesort might be a factor of log (5000) slower. 1990s Unix user found this problem in qsort() fb.com/goupee.vn 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 3
goupee.vn goupee.com Exercise: Create Sample Data 3-Way Partitioning Write a program that generates more than 1 3-way partitioning. Partition elements into 3 million integer numbers. These number are in parts: range of 40 different discrete values. Elements between i and j equal to partition element v. No larger elements to left of i. No smaller elements to right of j. Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method Equal to pivot, push to left 1 10 5 13 10 2 17 10 3 10 19 10 1 10 5 13 10 2 17 10 3 10 19 10 Pivot Pivot fb.com/goupee.vn 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 4
goupee.vn goupee.com Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method 10 1 5 13 10 2 17 10 3 10 19 10 10 1 5 13 10 2 17 10 3 10 19 10 Pivot Pivot Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method Equal to pivot, push to right 10 1 5 13 10 2 17 10 3 10 19 10 10 1 5 13 10 2 17 10 3 10 19 10 Stop moving from left, an element greater than pivot is found Pivot Pivot fb.com/goupee.vn 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 5
goupee.vn goupee.com Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method 10 1 5 13 10 2 17 10 3 19 10 10 10 1 5 13 10 2 17 10 3 19 10 10 Stop moving from right, an element less than than pivot is found Pivot Pivot Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method 10 1 5 13 10 2 17 10 3 19 10 10 10 1 5 3 10 2 17 10 13 19 10 10 Exchange Pivot Pivot Repeating the process till red & blue arrows crosses each other… fb.com/goupee.vn 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 6
goupee.vn goupee.com Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method 10 10 5 3 1 2 17 19 13 10 10 10 10 10 5 3 1 2 17 19 13 10 10 10 Pivot Pivot We reach here……… Exchange the pivot with red arrow content, we get… Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method Moving left to the pivot Moving right to the pivot 10 10 5 3 1 2 10 19 13 10 10 17 1 2 5 3 10 10 10 19 13 10 10 17 Pivot Pivot fb.com/goupee.vn 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 7
goupee.vn goupee.com Scope for improvements- duplicate keys Scope for improvements- duplicate keys A 3-way partitioning method A 3-way partitioning method Partition- 1 Partition- 2 Partition- 3 Partition- 1 Partition- 2 Partition- 3 1 2 5 3 10 10 10 10 10 19 13 17 1 2 5 3 10 10 10 10 10 19 13 17 • Apply Quick sort to partition-1 and partition-3, recursively…… • What if all the elements are same in the given array?????????? • Try to implement it…. Implementation solution Code 3-way partitioning (Bentley- void sort(int a[], int l, int r) { if (r <= l) return; McIlroy): Partition elements int i = l-1, j = r; v into 4 parts: int p = l-1, q = r; while(1) { l r no larger elements to left of i while (a[++i] < a[r])); while (a[r] < a[--j])) if (j == l) break; no smaller elements to right if (i >= j) break; of j exch(a, i, j); v if (a[i]==a[r]) exch(a, ++p, i); i r equal elements to left of p if (a[j]==a[r]) exch(a, --q, j); j } equal elements to right of q exch(a, i, r); j = i - 1; Afterwards, swap equal keys i = i + 1; into center. for (int k = l ; k <= p; k++) exch(a, k, j--); for (int k = r-1; k >= q; k--) exch(a, k, i++); sort(a, l, j); sort(a, i, r); < v = v > v } l r fb.com/goupee.vn 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 8
goupee.vn goupee.com Demo Quiz 1 demo-partition3.ppt Write two quick sort algorithms 2-way partitioning 3-way partitioning Create two identical arrays of 1 millions randomized numbers having value from 1 to 10. Compare the time for sorting the numbers using each algorithm Guide Demand memory Fill an array by random numbers For 1000000 elements const int TOPITEM = 1000000; void fill_array(void) { int i; int *w=(int *)malloc(1000000); float r; srand(time(NULL)); for (i = 1; i < TOPITEM; i++) { r = (float) rand() / (float) RAND_MAX; data[i] = r * RANGE + 1; } } fb.com/goupee.vn 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 9
goupee.vn goupee.com CPU Time Inquiry Generalized sorting #include <time.h> In C we can use the qsort function for sorting void qsort( clock_t start, end; void *buf, size_t num, double cpu_time_used; size_t size, int (*compare)(void const *, void const *) ); start = clock(); ... /* Do the work. */ The qsort() function sorts buf (which contains num items, each of size size). end = clock(); The compare function is used to compare the items in buf. compare should return negative if the first argument is less than cpu_time_used = ((double) (end - start)) / the second, zero if they are equal, and positive if the first CLOCKS_PER_SEC; argument is greater than the second. Example Function pointer int int_compare(void const* x, void const *y) { Declare a pointer to a function int m, n; int (*pf) (int); m = *((int*)x); n = *((int*)y); Declare a function if ( m == n ) return 0; int f(int); return m > n ? 1: -1; Assign a function to a function pointer } void main() pf = &f; { Call a function via pointer int a[20], n; ans = pf(5); // which are equivalent with ans = f(5) /* input an array of numbers */ /* call qsort */ qsort(a, n, sizeof(int), int_compare); In the qsort() function, compare is a function } pointer to reference to a compare the items fb.com/goupee.vn 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 10
goupee.vn goupee.com Quiz 2 Solution Write a function to compare strings so that it #include <stdio.h> #include <stdlib.h> can be used with qsort() function #include <string.h> Write a program to input a list of names, then int cstring_cmp(const void *a, const void *b) { use qsort() to sort this list and display the const char **ia = (const char **)a; result. const char **ib = (const char **)b; return strcmp(*ia, *ib); } void print_cstring_array(char **array, size_t len) { size_t i; for(i=0; i<len; i++) printf("%s | ", array[i]); putchar('\n'); } Solution Solution: You can get strings from input also int main() int main() { { char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" }; char strings[20]; size_t strings_len = sizeof(strings) / sizeof(char *); char *strings_array[20]; int i = 0; puts("*** String sorting..."); int n; print_cstring_array(strings, strings_len); printf("\n Number of strings to sort:"); scanf("%d",&n); fflush(stdin); qsort(strings, strings_len, sizeof(char *), cstring_cmp); while(i<n){ gets(strings); print_cstring_array(strings, strings_len); strings_array[i++] = strdup(strings); } return 0; print_cstring_array(strings_array, n); } puts("*** String sorting..."); qsort(strings_array, n, sizeof(char *), cstring_cmp); print_cstring_array(strings_array, n); return 0; } fb.com/goupee.vn 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 11
goupee.vn goupee.com Quiz 3: Using qsort with array of structure Solution Create an array of records, each record is in Create on your own function to compare two type of: float numbers struct st_ex { char product[16]; int struct_cmp_by_price(const void *a, const void float price; *b) }; { Write a program using qsort to sort this array struct st_ex *ia = (struct st_ex *)a; by the price and by product names. struct st_ex *ib = (struct st_ex *)b; return (int)(100.f*ia->price - 100.f*ib->price); } Solution Solution: function for Output And by product names void print_struct_array(struct st_ex *array, size_t len) int struct_cmp_by_product(const void *a, const { void *b) size_t i; { for(i=0; i<len; i++) struct st_ex *ia = (struct st_ex *)a; printf("[ product: %s \t price: $%.2f ]\n", struct st_ex *ib = (struct st_ex *)b; array[i].product, array[i].price); return strcmp(ia->product, ib->product); } puts("--"); } fb.com/goupee.vn 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 12
goupee.vn goupee.com Solution: And test Quiz 4 void main() How to use qsort() to sort an array in { struct st_ex structs[] = {{"mp3 player", 299.0f}, {"plasma tv", 2200.0f}, descendant order? {"notebook", 1300.0f}, {"smartphone", 499.99f}, {"dvd player", 150.0f}, {"matches", 0.2f }}; Write your own generalized quick sort function (using 3-way partitioning algorithm). size_t structs_len = sizeof(structs) / sizeof(struct st_ex); Then, use this function to sort different kinds of puts("*** Struct sorting (price)..."); print_struct_array(structs, structs_len); data (integer numbers, phone number records, etc.) qsort(structs, structs_len, sizeof(struct st_ex), struct_cmp_by_price); print_struct_array(structs, structs_len); puts("*** Struct sorting (product)..."); qsort(structs, structs_len, sizeof(struct st_ex), struct_cmp_by_product); print_struct_array(structs, structs_len); } Generalized sorting Exercise We can use also heap sort and merge sort Using the grade data file of your class last semester. void heapsort( void *buf, You write a compare function that takes the size_t num, pointers to struct of student as parameters to size_t size, int (*compare)(void const *, void const *) use qsort to sort the student list. ); Change from qsort to heapsort void mergesort( void *buf, size_t num, size_t size, int (*compare)(void const *, void const *) ); fb.com/goupee.vn 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Affichage des 12 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !