Ordenar e insertar ordenado en TObjectList

[roman]

Empezado por sebamawa

Ya que estoy en este tema, me podrán recomendar un buen manual de Delphi donde pueda estudiar. Si estuviera su versión digital para descarga sería fantástico.

¡Claro! En nuestro Repositorio de archivos hay mucho material. Busca en Delphi/Manuales. Entre otros, encontrarás La cara oculta de delphi 4, que en gran medidad, sigue vigente aún para las versiones actules de delphi.

// Saludos

[roman]

¡Ah! También está el mismo libro pero para la versión 6. Tiene su título en inglés (The Dark Side of Delphi) pero el libro está en español.

// Saludos

[[Delphius]]

Roman tengo una duda sobre tu propuesta, que dicho sea de paso, es altamente ingeniosa como acostumbras.
La inserción binaria, al menos lo que yo tengo entendido y recuerdo de cátedra (de hace ya años...) sólo tiene sentido si la lista ya está está ordenada. Es decir que para poder insertar de forma ordenada, se debe ejecutar el método Sort() previamente.
No si es que he analizado mal el algoritmo que propones, pero creo ese InsertaOrdenado() falla cuando se intenta insertar el 1er item y el vez de colocarlo en el índice 0, va a parar en el índice 1.

Como nota: No sería de extrañar que en las nuevas versiones de Delphi el algoritmo de ordenamiento "base" o "kernel" de TList deje de ser QuickSort. Existe un algoritmo, relativamente reciente, que es más rápido y además permite hacer inserciones de forma directa. Se llama TimSort. Java, Python ya lo tienen implementado como el algoritmo de ordenamiento por defecto en sus últimas versiones.

Por otro lado nada impide hacer un TOrderObjectList que implemente justamente tanto ordenamiento como inserción ordenada.

Saludos,

[roman]

Empezado por Delphius

La inserción binaria, al menos lo que yo tengo entendido y recuerdo de cátedra (de hace ya años...) sólo tiene sentido si la lista ya está está ordenada.

Así es. Por eso hay que usarla desde el principio . Cuando la lista está vacía, no hay nada qué ordenar y por tanto llamar a Sort está de más. Pero si se intenta usar sobre una lista desordenada, ciertamente hay que llamar a Sort primero.

Empezado por Delphius

No si es que he analizado mal el algoritmo que propones, pero creo ese InsertaOrdenado() falla cuando se intenta insertar el 1er item y el vez de colocarlo en el índice 0, va a parar en el índice 1.

Si la lista está vacía, Primero = 0 y Ultimo = -1 así que el ciclo while no se ejecuta y se hace la inserción en el índice 0.

Empezado por Delphius

Existe un algoritmo, relativamente reciente, que es más rápido y además permite hacer inserciones de forma directa.

No entiendo que significa que un algoritmo de ordenamiento permita hacer inserciones directas.

Empezado por Delphius

Por otro lado nada impide hacer un TOrderObjectList que implemente justamente tanto ordenamiento como inserción ordenada.

Así es, sería lo óptimo, pero hice el procedimiento para facilitar las cosas y no tener que implementar una clase derivada.

// Saludos

[[Delphius]]

Empezado por roman

Así es. Por eso hay que usarla desde el principio . Cuando la lista está vacía, no hay nada qué ordenar y por tanto llamar a Sort está de más. Pero si se intenta usar sobre una lista desordenada, ciertamente hay que llamar a Sort primero.

Es que a como entendí de las palabras de sebamawa es que quería evitarse el ordenamiento y hacer inserciones ordenadas directamente sobre la lista, con los datos previamente almacenados.

Empezado por roman

Si la lista está vacía, Primero = 0 y Ultimo = -1 así que el ciclo while no se ejecuta y se hace la inserción en el índice 0.

Marche unos lentes para Delphius... no vi ese .Count -1

Empezado por roman

No entiendo que significa que un algoritmo de ordenamiento permita hacer inserciones directas.

Si... admito que lo dije muy flojo y que no se entendería bien... Como TimSort() es un algoritmo híbrido, posee una combinación del Merge() con Insertion() por lo que posee la particularidad de ofrecer internamente una insercción ordenada.
Con TimSort, de lo poco que le entendí de su funcionamiento, es capaz de determinar cuando aplicar un Merge() y cuando aprovechar una insercción. Si se tuviera TimSort por defecto, al hacer un Add, Insert, Move, etc de forma "automática" se hacen las cosas con un único algoritmo y es posible que en ningún momento se ejecute la parte del Merge().

Empezado por roman

Así es, sería lo óptimo, pero hice el procedimiento para facilitar las cosas y no tener que implementar una clase derivada.
// Saludos

No sería extraño que en las nuevas versiones ya existiera una clase como esta. Lo más "cercano" a ésta que veo en D6 es TOrderedList, la clase base para TStack y TQueue, que ofrece el método virtual y abstracto PushItem() que está pensado para determinar como ha de tener lugar la inserción del ítem. Tanto TStack como TQueue sobrescriben a éste para conseguir la inserción por pila y cola respectivamente.

Saludos,

[roman]

Empezado por Delphius

Es que a como entendí de las palabras de sebamawa es que quería evitarse el ordenamiento y hacer inserciones ordenadas directamente sobre la lista

Eso mismo entendí yo.

Empezado por Delphius

con los datos previamente almacenados.

Bueno, es que esto sería imposible

// Saludos

[[Delphius]]

Empezado por roman

Bueno, es que esto sería imposible
// Saludos

Pues si. Pero es que yo asumía que por "previamente almacenados" hace referencia a que de algún modo se recuperaban los datos almacenados físicamente y que éstos ya se encontraban ordenados.

Voy a tener que dejar los supuestos

Yo también le apuesto a TStringList cuando se trata de mantener los objetos ordenados de acuerdo a cierta "clave", aunque no me es de total agrado... Lo siento como que se está utilizando un parche.
Resulta extraño que no hubiera de fábrica una lista de objetos ordenada, sin tener que recurrir a otra vía.

Saludos,