Adaptive Sorting and Coding: Merge Sort and Permutations
Jérémy Barbay 30 Mar 201030/03/10 a las 17:59 hrs.2010-03-30 17:59:30
Adaptive Sorting and Coding: Merge Sort and Permutations
========================================================
Author: Jérémy Barbay
Date: 2010-03-30 21:59:40 XXX
<2010-03-30 Tue 14:30-16:00>
1) Merge Sort
1. O(n \lg n)
2. O(n \lg \rho)
3. O(n H(Runs))
2) Adaptivity and Compression
1. Wavelet Tree
2. Compressed Wavelet Tree
3. Compression of Permutations
3) Other types of adaptive sorting
1. Insertion Sort
2. SUS, SMS
3. Adaptive Analysis of HeapSort?
1 References: (Many)
~~~~~~~~~~~~~~~~~~~~~
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
@Article{encroachingListsAsAMeasureOfPresortedness,
author = {S. S. Skiena},
title = {Encroaching lists as a measure of presortedness},
journal = {BIT},
year = 1988,
volume = 28,
number = 4,
pages = {775-784}
}
@article{sortingShuffledMonotoneSequences,
author = {Christos Levcopoulos and
Ola Petersson},
title = {Sorting Shuffled Monotone Sequences},
journal = {Inf. Comput.},
volume = {112},
number = {1},
year = {1994},
pages = {37-50},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
@Article{cook,
author = {C.R. Cool and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
@Article{dijkstra,
author = {Edsger W. Dijkstra},
title = {Smoothsort, an alternative for sorting in situ},
journal = {Science of Computer Programming},
year = {1982},
volume = {1},
number = {3},
pages = {223--233},
month = {May},
}
@InProceedings{measuresOfPresortednessAndOptimalSortingAlgorithms,
author = {Heikki Mannila},
title = {Measures of Presortedness and Optimal Sorting Algorithms.},
booktitle = {IEEE Trans. Comput.},
pages = {318--325},
year = {1985},
volume = {34},
}
========================================================
Author: Jérémy Barbay
Date: 2010-03-30 21:59:40 XXX
<2010-03-30 Tue 14:30-16:00>
1) Merge Sort
1. O(n \lg n)
2. O(n \lg \rho)
3. O(n H(Runs))
2) Adaptivity and Compression
1. Wavelet Tree
2. Compressed Wavelet Tree
3. Compression of Permutations
3) Other types of adaptive sorting
1. Insertion Sort
2. SUS, SMS
3. Adaptive Analysis of HeapSort?
1 References: (Many)
~~~~~~~~~~~~~~~~~~~~~
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
@Article{encroachingListsAsAMeasureOfPresortedness,
author = {S. S. Skiena},
title = {Encroaching lists as a measure of presortedness},
journal = {BIT},
year = 1988,
volume = 28,
number = 4,
pages = {775-784}
}
@article{sortingShuffledMonotoneSequences,
author = {Christos Levcopoulos and
Ola Petersson},
title = {Sorting Shuffled Monotone Sequences},
journal = {Inf. Comput.},
volume = {112},
number = {1},
year = {1994},
pages = {37-50},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
@Article{cook,
author = {C.R. Cool and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
@Article{dijkstra,
author = {Edsger W. Dijkstra},
title = {Smoothsort, an alternative for sorting in situ},
journal = {Science of Computer Programming},
year = {1982},
volume = {1},
number = {3},
pages = {223--233},
month = {May},
}
@InProceedings{measuresOfPresortednessAndOptimalSortingAlgorithms,
author = {Heikki Mannila},
title = {Measures of Presortedness and Optimal Sorting Algorithms.},
booktitle = {IEEE Trans. Comput.},
pages = {318--325},
year = {1985},
volume = {34},
}
| Última Modificación | 30 Mar 201030/03/10 a las 18:01 hrs.2010-03-30 18:01:30 |
|---|---|
| Vistas Únicas | 2 |
| Compartir | |
| Comentarios |
|
