Sorting Linked Lists

Table of contents:

Projects

8.14

In the insertion sort algorithm, we repeatedly find the next element and insert it into the already sorted region of the array. The selection sort algorithm instead begins by finding the smallest element in the array and swapping it with the element at position 0. The second smallest element (that is, the smallest element besides the one now at position 0) is then found and swapped with element 1. The third smallest element is placed at position 2, and so on. Implement selection sort and analyze its best-, average-, and worst-case running time.

8.15

Modify SortableArrayList so that it implements Comparable. The order should be similar to the lexicographical order for Strings. Specifically, compare the elements at each position, starting with element 0. The first SortableArrayList to have a smaller element at some position is the smaller one. If one of them runs out of elements before a difference is found, the one that ran out is the smaller one, just as the String "gar" is less than "gargoyle".

8.16

Do Project 8.15, but with SortableLinkedList instead.


Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting

Recursion

Part IV: Trees and Sets

Trees

Sets

Part V: Advanced Topics

Advanced Linear Structures

Strings

Advanced Trees

Graphs

Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading

Index



Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net