Skip to content

Instantly share code, notes, and snippets.

@sobrinho

sobrinho/stable_sort_example.rb

Forked from cyberfox/stable_sort_example.rb
Last active May 3, 2022 23:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sobrinho/cdaffbe69f918710c17df70c24d9e1cd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sobrinho/cdaffbe69f918710c17df70c24d9e1cd to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sobrinho revised this gist May 3, 2022. 1 changed file with 14 additions and 20 deletions.
    34 changes: 14 additions & 20 deletions stable_sort_example.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,21 +1,15 @@
    # This example is flawed, but hopefully useful for demonstration purposes.
    def test_stable_sorting
    ary = (1..100).to_a.shuffle + (1..100).to_a.shuffle
    # Create a array with numbers from 1 to 100 in a random order
    ary = (1..100).to_a.shuffle + (1..100).to_a.shuffle

    # This associates an ordering with the randomized numbers
    idx = 0
    paired = ary.collect {|value| [value, idx += 1]}
    puts "Now the numbers are paired; the first is the random number 1-100,"
    puts "the second is its sequence within the 200 entries."
    puts paired.inspect
    puts
    puts "#sort is unstable; you'll see many entries with equal first values"
    puts "where the first of them has a higher second (sequence) number, meaning"
    puts "it's out of order now."
    puts paired.sort {|x,y| x.first <=> y.first }.inspect
    puts
    puts "Now we sort exclusively on the value, while preserving ordering;"
    puts "All entries with identical first values should have second values"
    puts "that are also in numerical order."
    puts paired.sort_by.with_index {|x, i| [x.first, i]}.inspect
    end
    idx = 0
    paired = ary.map.with_index { |value| [value, idx += 1] }

    # Now the numbers are paired; the first is the random number 1-100 the second is its sequence within the 200 entries
    puts paired.inspect

    # You'll see many entries with equal first values where the first of them has a higher second (sequence) number, meaning it's out of order now
    puts paired.sort { |x, y| x[0] <=> y[0] }.inspect

    # Now we sort exclusively on the value, while preserving ordering
    # All entries with identical first values should have second values that are also in numerical order
    puts paired.sort_by.with_index { |x, i| [x[0], i] }.inspect
  2. @cyberfox cyberfox created this gist Jan 31, 2011.
    21 changes: 21 additions & 0 deletions stable_sort_example.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,21 @@
    # This example is flawed, but hopefully useful for demonstration purposes.
    def test_stable_sorting
    ary = (1..100).to_a.shuffle + (1..100).to_a.shuffle

    # This associates an ordering with the randomized numbers
    idx = 0
    paired = ary.collect {|value| [value, idx += 1]}
    puts "Now the numbers are paired; the first is the random number 1-100,"
    puts "the second is its sequence within the 200 entries."
    puts paired.inspect
    puts
    puts "#sort is unstable; you'll see many entries with equal first values"
    puts "where the first of them has a higher second (sequence) number, meaning"
    puts "it's out of order now."
    puts paired.sort {|x,y| x.first <=> y.first }.inspect
    puts
    puts "Now we sort exclusively on the value, while preserving ordering;"
    puts "All entries with identical first values should have second values"
    puts "that are also in numerical order."
    puts paired.sort_by.with_index {|x, i| [x.first, i]}.inspect
    end