Assignment 1

  • Implement the sorting algorithm you came up with in pseudocode with Python.
  • Test the sorting algorithm with a list of 10, 100, 1000 random numbers and compare the result using the %time to time your code and submit your results in code comments.

In [188]:
import random

Pseudocode

Read in the list and count the number of its elements. Build a loop that runs as many times.

Build a second loop, starting at the index of the first element plus 1, runing for the full length of the list.

Check if the selected element is smaller than the one from the first loop. If it is: Exchange the two elements.

The algorithm


In [189]:
def ownsort(int_list):
    for i in range(len(int_list) - 1):
        k = i
        for j in range(i + 1, len(int_list)):
            if int_list[j] < int_list[k]:
                k = j
        int_list[i], int_list[k] = int_list[k], int_list[i]
    return int_list

In [190]:
int_list = [3,1,6,55,13,22,6,9,32]
ownsort(int_list)


Out[190]:
[1, 3, 6, 6, 9, 13, 22, 32, 55]

Test the sorting Algorithm


In [191]:
# Generate random numbers

int_list_10 = []
for i in range(0,10):
    int_list_10.append(random.randint(1,1000))

int_list_100 = []
for i in range(0,100):
    int_list_100.append(random.randint(1,1000))

int_list_1000 = []
for i in range(0,1000):
    int_list_1000.append(random.randint(1,1000))

In [192]:
print(ownsort(int_list_10))
%time


[246, 273, 286, 389, 426, 637, 801, 954, 974, 996]
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.72 µs

Result of %time:

CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 5.72 µs


In [194]:
print(ownsort(int_list_100))
%time


[11, 13, 31, 47, 73, 74, 76, 95, 105, 110, 135, 151, 154, 161, 165, 165, 166, 177, 177, 184, 189, 190, 213, 220, 220, 249, 266, 267, 290, 291, 298, 307, 318, 323, 337, 343, 346, 348, 348, 348, 360, 367, 371, 414, 452, 472, 476, 477, 483, 505, 510, 526, 546, 557, 575, 575, 587, 592, 599, 614, 619, 641, 662, 665, 677, 677, 691, 696, 699, 699, 710, 720, 740, 745, 754, 759, 767, 770, 782, 791, 794, 796, 815, 826, 836, 836, 839, 884, 885, 912, 931, 932, 942, 944, 951, 952, 962, 979, 983, 987]
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 5.48 µs

Result of %time:

CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 5.48 µs


In [195]:
print(ownsort(int_list_1000))
%time


[2, 4, 5, 7, 8, 8, 9, 9, 10, 12, 15, 15, 15, 16, 16, 17, 17, 18, 18, 18, 19, 19, 19, 20, 21, 21, 22, 23, 23, 24, 25, 27, 27, 30, 31, 31, 33, 33, 34, 37, 39, 42, 42, 43, 43, 43, 43, 45, 46, 46, 47, 47, 48, 49, 50, 52, 52, 53, 53, 54, 54, 56, 56, 56, 59, 61, 61, 63, 63, 65, 66, 66, 67, 68, 68, 68, 70, 70, 72, 72, 73, 73, 74, 76, 76, 78, 79, 79, 79, 81, 82, 82, 82, 82, 83, 83, 84, 84, 85, 85, 86, 86, 87, 88, 88, 89, 92, 92, 93, 93, 93, 94, 95, 96, 97, 98, 99, 101, 105, 106, 108, 110, 111, 112, 116, 117, 118, 119, 119, 120, 121, 124, 127, 127, 128, 128, 129, 131, 133, 133, 133, 135, 136, 136, 136, 138, 138, 139, 144, 145, 145, 145, 148, 148, 148, 148, 148, 148, 149, 151, 152, 153, 153, 157, 158, 160, 161, 162, 163, 164, 167, 168, 168, 169, 169, 170, 171, 172, 172, 174, 174, 175, 175, 176, 176, 177, 177, 178, 179, 182, 184, 185, 185, 185, 186, 188, 189, 189, 190, 190, 191, 192, 193, 193, 195, 197, 197, 199, 201, 201, 202, 203, 203, 205, 206, 206, 207, 208, 210, 211, 213, 213, 214, 215, 217, 219, 219, 220, 222, 223, 224, 224, 224, 224, 225, 226, 226, 227, 228, 228, 229, 230, 230, 230, 230, 232, 233, 233, 233, 234, 234, 235, 237, 237, 237, 238, 239, 239, 242, 245, 248, 248, 251, 252, 252, 252, 253, 255, 257, 259, 260, 264, 264, 264, 264, 265, 267, 267, 267, 270, 270, 272, 272, 275, 277, 278, 282, 283, 284, 286, 287, 288, 288, 290, 291, 293, 293, 296, 297, 299, 299, 300, 300, 300, 300, 301, 301, 302, 303, 304, 305, 306, 308, 309, 310, 310, 312, 313, 315, 316, 320, 321, 322, 322, 324, 324, 324, 326, 326, 327, 327, 327, 327, 328, 329, 329, 329, 330, 331, 331, 331, 332, 332, 332, 333, 335, 336, 336, 337, 338, 338, 342, 344, 345, 346, 348, 349, 351, 352, 353, 354, 355, 356, 356, 357, 357, 357, 358, 360, 362, 362, 363, 366, 367, 367, 367, 368, 369, 370, 372, 373, 373, 374, 375, 377, 378, 379, 380, 382, 383, 383, 384, 386, 386, 387, 389, 390, 390, 391, 391, 391, 392, 393, 394, 395, 396, 399, 399, 401, 402, 403, 407, 407, 408, 411, 411, 411, 412, 413, 416, 417, 418, 418, 419, 420, 422, 424, 424, 426, 426, 426, 427, 430, 433, 433, 433, 434, 434, 434, 434, 434, 438, 439, 439, 440, 440, 441, 441, 441, 442, 443, 443, 443, 444, 444, 445, 448, 451, 452, 452, 453, 454, 455, 459, 459, 460, 462, 462, 463, 464, 466, 467, 469, 469, 471, 473, 473, 478, 479, 482, 482, 484, 484, 485, 485, 486, 486, 486, 486, 487, 487, 488, 488, 488, 489, 489, 491, 491, 492, 493, 494, 496, 497, 499, 501, 501, 503, 505, 505, 506, 509, 510, 513, 513, 514, 514, 516, 517, 518, 518, 519, 520, 520, 521, 522, 523, 526, 530, 530, 531, 534, 535, 535, 536, 538, 538, 539, 539, 540, 541, 541, 543, 545, 547, 548, 549, 551, 551, 552, 554, 554, 554, 555, 556, 557, 558, 559, 561, 563, 566, 566, 567, 567, 569, 569, 572, 572, 574, 574, 574, 576, 579, 580, 581, 581, 583, 585, 585, 587, 587, 590, 590, 590, 593, 596, 596, 596, 598, 599, 599, 600, 600, 601, 602, 604, 605, 608, 608, 608, 609, 609, 611, 612, 612, 615, 619, 619, 620, 620, 621, 621, 626, 626, 627, 627, 628, 631, 633, 633, 634, 635, 635, 635, 636, 636, 637, 637, 637, 638, 639, 639, 643, 643, 643, 644, 644, 645, 645, 645, 647, 648, 648, 649, 651, 652, 653, 654, 654, 655, 656, 659, 660, 661, 661, 662, 663, 664, 665, 665, 671, 672, 675, 675, 676, 676, 677, 678, 678, 679, 680, 681, 681, 681, 681, 686, 688, 688, 689, 689, 690, 690, 691, 692, 693, 693, 693, 695, 695, 696, 697, 697, 698, 698, 699, 699, 701, 701, 702, 702, 703, 705, 707, 707, 708, 708, 713, 714, 716, 716, 717, 719, 722, 722, 722, 723, 723, 723, 725, 726, 727, 727, 728, 729, 730, 732, 732, 732, 733, 733, 734, 735, 736, 736, 736, 737, 740, 742, 742, 744, 744, 745, 746, 746, 747, 748, 749, 749, 750, 751, 751, 753, 756, 758, 763, 765, 767, 767, 769, 769, 769, 770, 773, 773, 774, 775, 776, 776, 776, 779, 779, 779, 779, 780, 780, 782, 782, 782, 782, 783, 784, 785, 787, 787, 788, 788, 790, 792, 794, 796, 796, 798, 800, 801, 802, 803, 805, 805, 806, 808, 808, 808, 808, 809, 810, 812, 812, 813, 814, 816, 816, 819, 820, 820, 823, 823, 824, 826, 827, 828, 828, 830, 831, 831, 831, 832, 832, 832, 836, 836, 838, 838, 838, 838, 840, 840, 843, 844, 844, 845, 845, 846, 848, 848, 850, 851, 851, 852, 854, 858, 859, 859, 863, 865, 865, 866, 866, 867, 867, 869, 870, 871, 872, 873, 873, 873, 875, 877, 877, 878, 880, 880, 883, 884, 885, 887, 890, 891, 892, 893, 894, 895, 895, 899, 899, 900, 901, 902, 902, 902, 902, 902, 903, 907, 907, 909, 909, 910, 911, 912, 913, 913, 913, 913, 915, 915, 915, 917, 917, 917, 920, 922, 922, 923, 925, 925, 926, 926, 927, 927, 928, 928, 929, 929, 930, 930, 934, 936, 938, 938, 939, 939, 939, 940, 941, 941, 945, 946, 948, 948, 948, 949, 950, 950, 951, 952, 952, 952, 953, 954, 954, 955, 955, 955, 956, 957, 962, 964, 965, 966, 966, 968, 969, 970, 970, 970, 971, 971, 972, 972, 973, 973, 974, 974, 975, 975, 975, 975, 976, 977, 978, 981, 983, 986, 988, 988, 989, 989, 990, 991, 991, 992, 992, 994, 996, 996, 997, 998, 999, 999, 999]
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 4.05 µs

Result of %time:

CPU times: user 0 ns, sys: 0 ns, total: 0 ns Wall time: 4.05 µs


In [ ]: