{"id":14796,"date":"2022-05-28T20:18:55","date_gmt":"2022-05-29T00:18:55","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14796"},"modified":"2026-06-09T10:53:34","modified_gmt":"2026-06-09T14:53:34","slug":"tr-174-a-presortedness-metric-for-ensembles-of-data-sequences","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/tr-174-a-presortedness-metric-for-ensembles-of-data-sequences\/","title":{"rendered":"TR-174: A Presortedness Metric for Ensembles of Data Sequences"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-174: A Presortedness Metric for Ensembles of Data Sequences\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/\">Technical Report<\/a>&nbsp;<strong>TR-174<\/strong><br>May 1990<\/p>\n\n\n\n<h2 id=\"a-presortedness-metric-for-ensembles-of-data-sequences\" class=\"wp-block-heading\">A Presortedness Metric for Ensembles of Data Sequences<\/h2>\n\n\n\n<p>R.S. Valiveti &amp; B.J. Oommen<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Sorting is a well studied problem in the field of computer science. Many excellent sorting methods are known today, including the recent adaptive methods which sort all sequences of data ( or permutations) and perform particularly well on sequences that are \u201calmost sorted\u201d according to some \u201cpresortedness\u201d measure. The methods existing in the literature have focussed on assigning a \u201cpresortedness\u201d measure to a single input sequence. The particular measure in question can then be related to the computational complexity of the algorithm being utilized. Such a measure, in itself, cannot be used to predict the expected complexity of au algorithm. A comparison of any two sorting algorithms (in the expected sense) necessarily requires a knowledge of the distribution of the data sequences presented to the sorting program.<br>In an attempt to capture the nature of the distribution of data sequences presented to a sorting program, we propose a presortedness metric which characterizes the properties of an ensemble of data sequences by a single parameter. This parameter indicates how sorted or unsorted the ensemble of random data sequences is. Various theoretical properties of the metric are derived. The estimation procedure for determining the Maximum Likelihood Estimate of the \u201cEnsemble Presortedness metric\u201d for a given ensemble of data sequences is also included. The results have been experimentally validated.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-174.pdf\">TR-174.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-174May 1990 A Presortedness Metric for Ensembles of Data Sequences R.S. Valiveti &amp; B.J. Oommen Abstract Sorting is a well studied problem in the field of computer science. Many excellent sorting methods are known today, including the recent adaptive methods which sort all sequences of data ( or permutations) and perform particularly well [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11906,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-14796","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14796","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14796"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14796\/revisions"}],"predecessor-version":[{"id":24539,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14796\/revisions\/24539"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11906"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14796"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14796"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}