Book contents
- Frontmatter
- Contents
- Preface
- Chapter 1 An Introduction to Collections, Generics, and the Timing Class
- Chapter 2 Arrays and ArrayLists
- Chapter 3 Basic Sorting Algorithms
- Chapter 4 Basic Searching Algorithms
- Chapter 5 Stacks and Queues
- Chapter 6 The BitArray Class
- Chapter 7 Strings, the String Class, and the StringBuilder Class
- Chapter 8 Pattern Matching and Text Processing
- Chapter 9 Building Dictionaries: The DictionaryBase Class and the SortedList Class
- Chapter 10 Hashing and the Hashtable Class
- Chapter 11 Linked Lists
- Chapter 12 Binary Trees and Binary Search Trees
- Chapter 13 Sets
- Chapter 14 Advanced Sorting Algorithms
- Chapter 15 Advanced Data Structures and Algorithms for Searching
- Chapter 16 Graphs and Graph Algorithms
- Chapter 17 Advanced Algorithms
- References
- Index
Chapter 3 - Basic Sorting Algorithms
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Chapter 1 An Introduction to Collections, Generics, and the Timing Class
- Chapter 2 Arrays and ArrayLists
- Chapter 3 Basic Sorting Algorithms
- Chapter 4 Basic Searching Algorithms
- Chapter 5 Stacks and Queues
- Chapter 6 The BitArray Class
- Chapter 7 Strings, the String Class, and the StringBuilder Class
- Chapter 8 Pattern Matching and Text Processing
- Chapter 9 Building Dictionaries: The DictionaryBase Class and the SortedList Class
- Chapter 10 Hashing and the Hashtable Class
- Chapter 11 Linked Lists
- Chapter 12 Binary Trees and Binary Search Trees
- Chapter 13 Sets
- Chapter 14 Advanced Sorting Algorithms
- Chapter 15 Advanced Data Structures and Algorithms for Searching
- Chapter 16 Graphs and Graph Algorithms
- Chapter 17 Advanced Algorithms
- References
- Index
Summary
The two most common operations performed on data stored in a computer are sorting and searching. This has been true since the beginning of the computing industry, which means that sorting and searching are also two of the most studied operations in computer science. Many of the data structures discussed in this book are designed primarily to make sorting and/or searching easier and more efficient on the data stored in the structure.
This chapter introduces you to the fundamental algorithms for sorting and searching data. These algorithms depend on only the array as a data structure and the only “advanced” programming technique used is recursion. This chapter also introduces you to the techniques we'll use throughout the book to informally analyze different algorithms for speed and efficiency.
SORTING ALGORITHMS
Most of the data we work with in our day-to-day lives is sorted. We look up definitions in a dictionary by searching alphabetically. We look up a phone number by moving through the last names in the book alphabetically. The post office sorts mail in several ways—by zip code, then by street address, and then by name. Sorting is a fundamental process in working with data and deserves close study.
As was mentioned earlier, there has been quite a bit of research performed on different sorting techniques. Although some very sophisticated sorting algorithms have been developed, there are also several simple sorting algorithms you should study first. These sorting algorithms are the insertion sort, the bubble sort, and the selection sort.
- Type
- Chapter
- Information
- Data Structures and Algorithms Using C# , pp. 42 - 54Publisher: Cambridge University PressPrint publication year: 2007