# A question about sorting

David Wong

Greenhorn

Posts: 15

posted 8 years ago

Now I have more than one hundred thousand records need to sort, what is the best algorithm can work at a high performance.

name math english total ranklist

jack 80.00 90.00 170.00 2

tom 95.00 90.00 185.00 1

jerry 50.00 40.00 90.00 3

I want to sort ranklist dynamically,when a new thing was added, then sort it ,but pay attention please, there are one thousand records here at least. Who can find a answer for this, show me the way, thank you in advance and my best wishes.

David

name math english total ranklist

jack 80.00 90.00 170.00 2

tom 95.00 90.00 185.00 1

jerry 50.00 40.00 90.00 3

I want to sort ranklist dynamically,when a new thing was added, then sort it ,but pay attention please, there are one thousand records here at least. Who can find a answer for this, show me the way, thank you in advance and my best wishes.

David

posted 8 years ago

You just want to store your records in a binary tree. Then you can quickly add a new record in the right place without resorting the whole thing.

For example, a TreeSet with an appropriate Comparator.

For example, a TreeSet with an appropriate Comparator.

Piet Verdriet

Ranch Hand

Posts: 266

posted 8 years ago

@OP: A small side note:

A binary tree (BT) tells nothing about the order of the structure: a BT is just a structure where each node in it has at 0, 1 or 2 children. A binary search tree (BST) however orders the nodes: "smaller" nodes go into the left subtree and "greater" (or equal) nodes into the right subtree of each node. Now a TreeSet or TreeMap is backed up internally by a red-black tree which is a special kind of BST: one that, while inserting nodes, balances itself so that the tree guarantees lookups, insertions etc. in log(n) time, where n is the total number of nodes in the tree.

[ August 29, 2008: Message edited by: Piet Verdriet ]

Originally posted by Ernest Friedman-Hill:

You just want to store your records in a binary tree. Then you can quickly add a new record in the right place without resorting the whole thing.

For example, a TreeSet with an appropriate Comparator.

@OP: A small side note:

A binary tree (BT) tells nothing about the order of the structure: a BT is just a structure where each node in it has at 0, 1 or 2 children. A binary search tree (BST) however orders the nodes: "smaller" nodes go into the left subtree and "greater" (or equal) nodes into the right subtree of each node. Now a TreeSet or TreeMap is backed up internally by a red-black tree which is a special kind of BST: one that, while inserting nodes, balances itself so that the tree guarantees lookups, insertions etc. in log(n) time, where n is the total number of nodes in the tree.

[ August 29, 2008: Message edited by: Piet Verdriet ]

Campbell Ritchie

Sheriff

Posts: 50749

83

posted 8 years ago

More of a beginner's question. I presume you are familiar with the common sort algorithms.

The question is: do you require a stable sort? If yes, then use recursive merge sort, if no use quicksort. Both run in O(

Once you have sorted your collection then a sorted binary tree is probably the best way to maintain sorting, as you have been told; in fact transferring your entire record to a binary sorted tree will sort it in O(

The question is: do you require a stable sort? If yes, then use recursive merge sort, if no use quicksort. Both run in O(

*n*log*n*) timeOnce you have sorted your collection then a sorted binary tree is probably the best way to maintain sorting, as you have been told; in fact transferring your entire record to a binary sorted tree will sort it in O(

*n*log*n*) time anyway.