CSC 345 Lecture 1: CSC 345 Sorting

• School: University of Arizona
• Department: Computer Science Main
• Course: CSC 345
• Professor: Lu

Document Summary

Definitions: sort stability: a sort is stable if it maintains the relative order of the records with the same key, ex: In: <1, 5, 6_1, 3, 6_2, 19, 0> Stable: out: <0, 1, 3, 5, 6_1, 6_2, 19> In: <1, 5, 6_2, 3, 6_1, 19, 0> For (j = i ; ( j > 0) && compare(list[j], list[j-1])<0; j--) Is o(n2 ) i: worst case: i =1. 2 i( ) n 1 i =1 n 1 i =1. Bubble sort: generally always slow, bubblesort(list), for ( i = 0; i < length(list) 1 ; i++){ For ( j = length(list) 1; j > i ; j--){ Selection sort is not stable: 6a, 1, 6b, 3, 1, 6a, 6b, 3, 1, 3, 6b, 6a. Selection (stable) (stable) (unstable) compare swap compare swap compare swap. Extra credit: use a binary search tree to order the elements.