Inversions from Sorting with Distance-Based Errors View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-12-22

AUTHORS

Barbara Geissmann , Paolo Penna

ABSTRACT

We study the number of inversions after running the Insertion Sort or Quicksort algorithm, when errors in the comparisons occur with some probability. We investigate the case in which probabilities depend on the difference between the two numbers to be compared and only differences up to some threshold τ are prone to errors. We give upper bounds for this model and show that for constant τ, the expected number of inversions is linear in the number of elements to be sorted. For Insertion Sort, we also yield an upper bound on the expected number of runs, i.e., the number of consecutive increasing subsequences. More... »

PAGES

508-522

References to SciGraph publications

Book

TITLE

SOFSEM 2018: Theory and Practice of Computer Science

ISBN

978-3-319-73116-2
978-3-319-73117-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-73117-9_36

DOI

http://dx.doi.org/10.1007/978-3-319-73117-9_36

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1099938617


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Geissmann", 
        "givenName": "Barbara", 
        "id": "sg:person.011771624777.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011771624777.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, ETH Zurich, Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0304-3975(01)00303-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001245016"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2465787.2465789", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003581996"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1037/h0070288", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009587172"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2701427", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021549032"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17327-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024486220", 
          "https://doi.org/10.1007/978-3-642-17327-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17327-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024486220", 
          "https://doi.org/10.1007/978-3-642-17327-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.1997.1470", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026878370"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2011.05.010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032146960"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-22177-9_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037392270", 
          "https://doi.org/10.1007/978-3-319-22177-9_18"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.comgeo.2004.12.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038739103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0963548304006297", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039599862"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-23719-5_62", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046667531", 
          "https://doi.org/10.1007/978-3-642-23719-5_62"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-23719-5_62", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046667531", 
          "https://doi.org/10.1007/978-3-642-23719-5_62"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/12.83656", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061089118"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0214009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841798"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539791195877", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879660"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539796305298", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880117"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.2517-6161.1977.tb01624.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1110458075"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.2517-6161.1977.tb01624.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1110458075"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-12-22", 
    "datePublishedReg": "2017-12-22", 
    "description": "We study the number of inversions after running the Insertion Sort or Quicksort algorithm, when errors in the comparisons occur with some probability. We investigate the case in which probabilities depend on the difference between the two numbers to be compared and only differences up to some threshold \u03c4 are prone to errors. We give upper bounds for this model and show that for constant \u03c4, the expected number of inversions is linear in the number of elements to be sorted. For Insertion Sort, we also yield an upper bound on the expected number of runs, i.e., the number of consecutive increasing subsequences.", 
    "editor": [
      {
        "familyName": "Tjoa", 
        "givenName": "A Min", 
        "type": "Person"
      }, 
      {
        "familyName": "Bellatreche", 
        "givenName": "Ladjel", 
        "type": "Person"
      }, 
      {
        "familyName": "Biffl", 
        "givenName": "Stefan", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Wiedermann", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-73117-9_36", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-73116-2", 
        "978-3-319-73117-9"
      ], 
      "name": "SOFSEM 2018: Theory and Practice of Computer Science", 
      "type": "Book"
    }, 
    "name": "Inversions from Sorting with Distance-Based Errors", 
    "pagination": "508-522", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-73117-9_36"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4332a9f3bafcfba9e7b44359bad02e93f9851929a2449c99b9718e179b92bab0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1099938617"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-73117-9_36", 
      "https://app.dimensions.ai/details/publication/pub.1099938617"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000325_0000000325/records_100788_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-319-73117-9_36"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73117-9_36'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73117-9_36'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73117-9_36'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-73117-9_36'


 

This table displays all metadata directly associated to this object as RDF triples.

143 TRIPLES      23 PREDICATES      42 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-73117-9_36 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nd775b9de41744bb1be1cdd1ff3fe1e49
4 schema:citation sg:pub.10.1007/978-3-319-22177-9_18
5 sg:pub.10.1007/978-3-642-17327-1
6 sg:pub.10.1007/978-3-642-23719-5_62
7 https://doi.org/10.1006/jcss.1997.1470
8 https://doi.org/10.1016/j.comgeo.2004.12.007
9 https://doi.org/10.1016/j.dam.2011.05.010
10 https://doi.org/10.1016/s0304-3975(01)00303-6
11 https://doi.org/10.1017/s0963548304006297
12 https://doi.org/10.1037/h0070288
13 https://doi.org/10.1109/12.83656
14 https://doi.org/10.1111/j.2517-6161.1977.tb01624.x
15 https://doi.org/10.1137/0214009
16 https://doi.org/10.1137/s0097539791195877
17 https://doi.org/10.1137/s0097539796305298
18 https://doi.org/10.1145/2465787.2465789
19 https://doi.org/10.1145/2701427
20 schema:datePublished 2017-12-22
21 schema:datePublishedReg 2017-12-22
22 schema:description We study the number of inversions after running the Insertion Sort or Quicksort algorithm, when errors in the comparisons occur with some probability. We investigate the case in which probabilities depend on the difference between the two numbers to be compared and only differences up to some threshold τ are prone to errors. We give upper bounds for this model and show that for constant τ, the expected number of inversions is linear in the number of elements to be sorted. For Insertion Sort, we also yield an upper bound on the expected number of runs, i.e., the number of consecutive increasing subsequences.
23 schema:editor N3c5d124097184e0ba24f768007ea6478
24 schema:genre chapter
25 schema:inLanguage en
26 schema:isAccessibleForFree false
27 schema:isPartOf N23063cc4456544fabd1cdd3af4388b1c
28 schema:name Inversions from Sorting with Distance-Based Errors
29 schema:pagination 508-522
30 schema:productId N2198f80351ca4a78bef03070d8ba16fa
31 N61b2c5b484514130beea0113ff8d59f9
32 Nc34169ee4755487998769c5736a74e21
33 schema:publisher Nd759e67cc3614cf9a435751a48c563bb
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099938617
35 https://doi.org/10.1007/978-3-319-73117-9_36
36 schema:sdDatePublished 2019-04-16T05:00
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N324dcb4d3dbd468cbcb9e41a8cbc6f85
39 schema:url https://link.springer.com/10.1007%2F978-3-319-73117-9_36
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N05f45f6e2b314c6ca5f0c8ab2fa7af10 schema:familyName Bellatreche
44 schema:givenName Ladjel
45 rdf:type schema:Person
46 N2198f80351ca4a78bef03070d8ba16fa schema:name doi
47 schema:value 10.1007/978-3-319-73117-9_36
48 rdf:type schema:PropertyValue
49 N23063cc4456544fabd1cdd3af4388b1c schema:isbn 978-3-319-73116-2
50 978-3-319-73117-9
51 schema:name SOFSEM 2018: Theory and Practice of Computer Science
52 rdf:type schema:Book
53 N324dcb4d3dbd468cbcb9e41a8cbc6f85 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 N3c5d124097184e0ba24f768007ea6478 rdf:first N64b597a2a77443939434430ee34ba46c
56 rdf:rest Nba67f4ae710c4319bf991e6b9f7e2beb
57 N43ef35faba9d49ad89258c5e49309816 schema:familyName Biffl
58 schema:givenName Stefan
59 rdf:type schema:Person
60 N58791f1c2b9e4fcebc1a1122d9ebf818 rdf:first Nd316dc7998324c40989988ca68e4f079
61 rdf:rest rdf:nil
62 N5cfbaaec22204b83a37ccb18738ee0de rdf:first N43ef35faba9d49ad89258c5e49309816
63 rdf:rest Nfe3453b74fbb48dd904221e9c121309f
64 N61b2c5b484514130beea0113ff8d59f9 schema:name readcube_id
65 schema:value 4332a9f3bafcfba9e7b44359bad02e93f9851929a2449c99b9718e179b92bab0
66 rdf:type schema:PropertyValue
67 N64b597a2a77443939434430ee34ba46c schema:familyName Tjoa
68 schema:givenName A Min
69 rdf:type schema:Person
70 Naf673548a27c48ba82c1d726e0c7979a rdf:first sg:person.013624103516.76
71 rdf:rest rdf:nil
72 Nba67f4ae710c4319bf991e6b9f7e2beb rdf:first N05f45f6e2b314c6ca5f0c8ab2fa7af10
73 rdf:rest N5cfbaaec22204b83a37ccb18738ee0de
74 Nc34169ee4755487998769c5736a74e21 schema:name dimensions_id
75 schema:value pub.1099938617
76 rdf:type schema:PropertyValue
77 Nd316dc7998324c40989988ca68e4f079 schema:familyName Wiedermann
78 schema:givenName Jiří
79 rdf:type schema:Person
80 Nd5adea086f41456ab4d47797af68f175 schema:familyName van Leeuwen
81 schema:givenName Jan
82 rdf:type schema:Person
83 Nd759e67cc3614cf9a435751a48c563bb schema:location Cham
84 schema:name Springer International Publishing
85 rdf:type schema:Organisation
86 Nd775b9de41744bb1be1cdd1ff3fe1e49 rdf:first sg:person.011771624777.02
87 rdf:rest Naf673548a27c48ba82c1d726e0c7979a
88 Nfe3453b74fbb48dd904221e9c121309f rdf:first Nd5adea086f41456ab4d47797af68f175
89 rdf:rest N58791f1c2b9e4fcebc1a1122d9ebf818
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
94 schema:name Pure Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.011771624777.02 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
97 schema:familyName Geissmann
98 schema:givenName Barbara
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011771624777.02
100 rdf:type schema:Person
101 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
102 schema:familyName Penna
103 schema:givenName Paolo
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
105 rdf:type schema:Person
106 sg:pub.10.1007/978-3-319-22177-9_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037392270
107 https://doi.org/10.1007/978-3-319-22177-9_18
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-642-17327-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024486220
110 https://doi.org/10.1007/978-3-642-17327-1
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/978-3-642-23719-5_62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046667531
113 https://doi.org/10.1007/978-3-642-23719-5_62
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1006/jcss.1997.1470 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026878370
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/j.comgeo.2004.12.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038739103
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/j.dam.2011.05.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032146960
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/s0304-3975(01)00303-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001245016
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1017/s0963548304006297 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039599862
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1037/h0070288 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009587172
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1109/12.83656 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061089118
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1111/j.2517-6161.1977.tb01624.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1110458075
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1137/0214009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841798
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1137/s0097539791195877 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879660
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1137/s0097539796305298 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880117
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1145/2465787.2465789 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003581996
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1145/2701427 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021549032
140 rdf:type schema:CreativeWork
141 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
142 schema:name Department of Computer Science, ETH Zurich, Zurich, Switzerland
143 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...