Computers are good at performing repetitive tasks; doing the same boring nonsense over and over. Two great examples are searching and sorting.
\n
\nIn my C programming books, I demonstrate the most basic and obvious type of sorting technique: The bubble sort. It’s a brute-force method of comparing each item in a list to every other item in the list. Items out of place are swapped, and the whole process repeats.<\/p>\n
For simple, small lists, the bubble sort works fine. I demonstrate such a sort in Chapter 12 of my book, Beginning Programming with C For Dummies<\/em>. A sort of 40 random integers is presented as the solution for the book’s Exercise 12-14<\/a>. It works well and demonstrates how a bubble sort works. And it’s pretty fast for sorting 40 values.<\/p>\n How about creating and sorting an array of 100,000 random integers?<\/p>\n A computer is quite content to sort 100,000 integers, although a bubble sort probably isn’t the most efficient way to order those values. (And at 4 bytes of storage per int<\/em>, that’s nearly half a megabyte of data.)<\/p>\n The change to the source code for Exercise 12-14 is simple: Modify the Here is the final code:<\/p>\n Compile and run the program to see how long your computer takes to do a bubble sort of 100,000 integers. On a Unix terminal (Mac OS X, Linux, or CYGWIN) use the time<\/em> command, followed by the compiled program name, such as:<\/p>\n Assuming that Nearly 10 seconds (9.910) elapsed between the time the first string was displayed and the program completed. That’s probably much faster than you (as a human) could sort the values, but it’s near an eternity for the computer. That’s because the bubble sort is inefficient.<\/p>\n Next week<\/a> I’ll show you another way to sort that’s much, much faster. Or I should write, quicker<\/em>.<\/p>\n","protected":false},"excerpt":{"rendered":" There has to be a better way to get to A to Z. Continue reading SIZE<\/code> constant, changing it from 40 to 100000. To make the code run faster, I removed the output statements; displaying output slows down any program, but more importantly watching 100,000 sorted, random integers fly up the terminal screen is meaningless.<\/p>\n\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <time.h>\r\n\r\n#define SIZE 100000\r\n\r\nint main()\r\n{\r\n int bubble[SIZE];\r\n int inner,outer,temp,x;\r\n\r\n srand((unsigned)time(NULL));\r\n \/* populate array *\/<\/span>\r\n for(x=0;x<SIZE;x++)\r\n {\r\n bubble[x] = rand();\r\n bubble[x] = (bubble[x] % 100)+1;\r\n }\r\n printf(\"%d element array created.\\n\",SIZE);\r\n\r\n \/* bubble sort *\/<\/span>\r\n printf(\"Sorting . . . \");\r\n for(outer=0;outer<SIZE-1;outer++)\r\n {\r\n for(inner=outer+1;inner<=SIZE;inner++)\r\n {\r\n if(bubble[outer] > bubble[inner])\r\n {\r\n temp=bubble[outer];\r\n bubble[outer] = bubble[inner];\r\n bubble[inner] = temp;\r\n }\r\n }\r\n }\r\n printf(\"Done!\\n\");\r\n\r\n return(0);\r\n}<\/pre>\n$ time blog0314<\/code><\/pre>\nblog0314<\/code> is the program generated by this Lesson’s source code, here’s the sample output on my screen:<\/p>\n100000 element array created.\r\nSorting . . . Done!\r\n\r\nreal\t0m9.910s\r\nuser\t0m9.899s\r\nsys\t0m0.011s<\/code><\/pre>\n