Sorting a list without using the Collection methods

How do I sort a l开发者_StackOverflow社区ist without using the Collection methods?

---

The roadmap

• Wikipedia/Sorting algorithm
  • Simple quadratic algorithms
    • Bubble sort - beginner friendly
    • Selection sort - very intuitive
    • Insertion sort - also intuitive
  • Essential comparison-based sort
    • Merge sort - slightly more advanced
    • Quick sort - skip this for now, but watch for it later
  • Essential non-comparison sort
    • Counting sort - important to understand

Your first sorting algorithm

I think counting sort is the best algorithm to start with. Read up about it and try to understand it, then write your own implementation as follows:

1. Generate 1000 random numbers between 0..9 (use java.util.Random to populate int[])
2. Sort them using counting sort.

Once you do this, you'll realize how simple sorting can be when you can take advantage of certain properties of the numbers (in this case, the fact that they're between 0..9).

Your second sorting algorithm

Selection sort is a good intuitive sorting algorithm for your next implementation. It's a comparison sort, and doesn't assume anything about the range of the numbers. Many people in real life sort using this algorithm:

• Given some selection to choose from, we look for the best and pick it first.
• Now the best is out, so we look for the second best from the rest.
• Then we look for the third best... etc

The rest of the journey

You may want to implement the other quadratic algorithms just to get a good grasp on the basics, but the next step would be to learn recursion, specifically divide and conquer algorithms.

You would not want to dive straight into merge sort/quick sort without first understanding basic recursion, because it can get too overwhelming.

Do the usual recursion exercises, factorial, Fibonacci, etc. Ask for pointers from stackoverflow if you need guidance. There may even already be questions with good answers about learning recursion.

A side trip

You may want to implement the merge portion of merge sort, even before you fully understand recursion yet. It's a very educational exercise:

• Given a sorted array of numbers A and a sorted array of numbers B, merge the two into one sorted array
  • Take advantage of the fact that A and B are already sorted

---

Since this is most likely homework I am going to give you advice rather than source code.

Take a look at this page on sorting algorithms. You should choose the correct sorting algorithm based on your requirements. Choosing the wrong algorithm can mean poor performance or unnecessary complexity.

Assuming you have only a small number of items and want a simple algorithm then you could look at insertion sort. The Wikipedia page includes pseudocode. This algorithm has O(n^2) performance.

If your lists are quite long and you want better performance at the cost of a slightly more complicated algorithm, you could try merge sort. This algorithm has O(n log(n)) performance both average and worst case and is a popular choice in language libraries.