Bubble Sort

For this challenge, your goal is to sort an array of numbers in Python, with the following guidelines:

• Cannot use any built-in sort functions

• Must be in-place (cannot create a new array)

  • therefore, you'll need to swap values

The name of this challenge contains bubble sort, so you may want to either research the sort or think about how you can sort the array by having the items "bubble" up to their correct positions.

Starter Code:

# O(n) best case, O(n^2) worst case
def bubble_sort(ls):
    pass

Data for testing:

numbers = [413, 445, 403, 224, 157, 312, 785, 862, 602, 354, 90, 442, 458, 641, 595, 441, 661, 690, 963, 376, 840, 463, 514, 919, 789, 423, 81, 272, 46, 981, 375, 70, 139, 955, 399, 179, 346, 369, 827, 171, 460, 982, 721, 631, 218, 200, 163, 510, 56, 30, 490, 320, 326, 327, 161, 586, 949, 244, 857, 750, 290, 716, 511, 573, 96, 340, 78, 800, 821, 417, 627, 847, 906, 672, 294, 279, 554, 709, 731, 344, 449, 790, 231, 307, 39, 574, 566, 941, 72, 884, 763, 486, 66, 578, 261, 723, 914, 104, 256, 600, 32, 358, 762, 526, 495, 367, 2, 875, 500, 165, 813, 172, 419, 616, 809, 699, 908, 945, 381, 742, 408, 575, 260, 468, 1, 959, 969, 755, 492, 135, 714, 624, 648, 336, 298, 464, 922, 18, 635, 874, 45, 370, 647, 769, 347, 772, 479, 140, 412, 118, 415, 170, 596, 798, 420, 250, 406, 73, 839, 656, 662, 512, 444, 324, 659, 363, 60, 69, 74, 633, 845, 537, 466, 19, 421, 844, 362, 166, 430, 62, 503, 202, 175, 888, 257, 696, 125, 206, 300, 726, 803, 836, 644, 741, 150, 353, 443, 233, 323, 396, 454, 356, 751, 31, 724, 747, 666, 236, 131, 151, 848, 736, 704, 240, 728, 299, 568, 990, 892, 855, 920, 424, 950, 379, 319, 304, 665, 766, 207, 846, 398, 730, 828, 177, 88, 5, 540, 44, 707, 54, 329, 357, 858, 132, 913, 84, 100, 680, 816, 551, 225, 305, 122, 757, 291, 478, 310, 583, 743, 205, 41, 186, 866, 655, 547, 764, 694, 748, 284, 8, 107, 562, 749, 679, 673, 833, 351, 28, 245, 143, 902, 20, 642, 784, 791, 604, 998, 893, 531, 989, 783, 980, 612, 221, 960, 964, 475, 268, 251, 416, 7, 992, 570, 293, 119, 116, 133, 29, 501, 316, 987, 713, 660, 504, 410, 541, 405, 418, 601, 465, 832, 854, 338, 863, 865, 219, 453, 469, 296, 975, 843, 653, 43, 211, 1000, 437, 619, 232, 685, 439, 447, 899, 697, 249, 876, 814, 801, 128, 13, 782, 237, 947, 489, 628, 544, 905, 303, 988, 390, 753, 470, 572, 10, 582, 431, 203, 180, 560, 141, 546, 65, 123, 695, 860, 598, 350, 111, 330, 943, 183, 51, 525, 775, 508, 923, 451, 682, 289, 138, 557, 640, 274, 49, 808, 286, 102, 173, 422, 456, 886, 273, 881, 765, 872, 308, 306, 35, 608, 334, 539, 625, 212, 455, 414, 850, 195, 711, 794, 282, 129, 335, 137, 962, 932, 811, 958, 101, 333, 188, 283, 771, 907, 677, 585, 227, 795, 168, 768, 910, 190, 997, 977, 281, 228, 254, 382, 158, 497, 38, 693, 687, 719, 933, 651, 758, 754, 868, 532, 965, 530, 820, 167, 159, 861, 930, 86, 246, 427, 343, 520, 124, 545, 95, 607, 924, 387, 404, 621, 113, 302, 611, 345, 230, 386, 328, 698, 321, 852, 946, 715, 134, 536, 438, 482, 898, 52, 178, 688, 515, 938, 819, 432, 556, 341, 16, 361, 927, 838, 729, 654, 318, 9, 733, 75, 26, 24, 793, 897, 538, 121, 93, 196, 339, 954, 292, 851, 645, 220, 571, 488, 162, 372, 313, 591, 457, 22, 110, 589, 563, 266, 364, 429, 710, 725, 717, 953, 505, 377, 64, 146, 325, 564, 903, 818, 271, 773, 270, 434, 277, 94, 614, 535, 740, 951, 529, 702, 384, 671, 674, 452, 594, 467, 603, 643, 181, 735, 99, 189, 870, 169, 473, 802, 629, 509, 352, 916, 761, 79, 366, 378, 617, 103, 209, 770, 502, 904, 581, 287, 285, 986, 263, 823, 548, 472, 144, 658, 901, 259, 223, 528, 984, 976, 650, 683, 280, 634, 374, 692, 92, 760, 182, 3, 380, 349, 737, 275, 174, 752, 337, 746, 37, 620, 995, 435, 87, 689, 397, 342, 278, 185, 85, 956, 499, 448, 243, 807, 389, 192, 638, 184, 450, 885, 506, 632, 744, 918, 276, 153, 780, 105, 411, 331, 204, 738, 48, 817, 193, 675, 622, 994, 667, 636, 983, 461, 891, 550, 663, 164, 147, 297, 34, 605, 931, 708, 552, 527, 11, 597, 481, 176, 966, 258, 792, 214, 580, 973, 649, 235, 565, 76, 701, 371, 606, 734, 208, 61, 829, 579, 590, 301, 657, 309, 720, 935, 14, 264, 332, 799, 426, 895, 670, 652, 974, 229, 355, 815, 55, 584, 727, 126, 63, 774, 498, 837, 767, 942, 36, 117, 407, 826, 210, 985, 993, 804, 706, 939, 613, 926, 82, 705, 360, 42, 558, 145, 841, 778, 507, 6, 388, 593, 97, 664, 686, 213, 787, 17, 567, 265, 15, 47, 21, 239, 476, 588, 58, 533, 849, 142, 433, 238, 215, 776, 676, 446, 887, 89, 523, 991, 156, 576, 940, 630, 948, 883, 879, 516, 639, 425, 485, 136, 796, 483, 921, 392, 368, 191, 67, 459, 120, 553, 267, 4, 834, 393, 252, 216, 255, 618, 517, 262, 491, 160, 409, 894, 900, 718, 822, 108, 873, 25, 197, 522, 474, 496, 201, 400, 712, 436, 519, 53, 967, 979, 915, 669, 480, 912, 952, 12, 112, 856, 77, 199, 543, 609, 806, 970, 317, 315, 972, 882, 681, 812, 911, 909, 365, 471, 98, 402, 610, 148, 810, 646, 521, 114, 217, 961, 937, 518, 241, 385, 149, 462, 373, 878, 853, 777, 957, 756, 494, 234, 484, 487, 703, 391, 869, 805, 929, 788, 824, 781, 917, 152, 599, 830, 222, 71, 968, 896, 542, 797, 248, 637, 127, 759, 877, 928, 27, 978, 678, 288, 577, 996, 477, 23, 226, 50, 401, 925, 561, 934, 40, 890, 493, 835, 864, 198, 383, 314, 295, 155, 831, 524, 322, 348, 745, 626, 57, 80, 115, 534, 825, 440, 68, 59, 971, 880, 615, 779, 722, 187, 859, 684, 154, 559, 91, 269, 513, 83, 623, 936, 786, 253, 587, 700, 555, 194, 592, 311, 130, 867, 944, 871, 109, 359, 549, 242, 668, 395, 394, 106, 999, 569, 732, 691, 428, 889, 842, 33, 247, 739]

Hint: Start figuring out how to move the first element to the right place, and go from there (the elements will have to bubble up to the top).