This is the SORTING page!



What is a sort?


   A sort is an algorithm used to put data into order.

What types of sorts are there?


   There are three main types of sorts. These are bubble sorts, selection sorts, and shell sorts.

How does a bubble sort work?


(This is from the website: http://www.cs.usask.ca/research/research_groups/aries/projects/applets/tutorials/sorting/bubble/1-1.shtml)
   Bubble sorts work by repeatedly moving the largest element to the highest index position of the array. Rather than search the entire array to find the largest element, bubble sort focuses on successive adjacent pairs of elements in the array.
   It compares the two elements, and then either swaps them (if the element with the smaller index number is larger than the other element) or leaves them alone (if the element with the smaller index is smaller than the other element). In either case, after such a step, the larger of the two elements will be in the higher index position.
   The focus then moves to the next highest position, and the process is repeated. When the focus reaches the end of the array, the largest element will have "bubbled" from whatever its original position was, to the last or highest index position in the array. The procedure is then repeated, causing the next largest element to bubble up to the highest index position - 1. This is repeated until all elements in the array have been sorted.

What is a selection sort and how does it work?


(This is from the website: http://www.mnu.samara.ru/St_Works/Leo/SortAlg/)
   The idea behind selection sort is that each shift of data moves an item directly into its final, correct place. This is done by finding the smallest element in the array and swapping it with the element in the first position, then finding the second smallest element and exchanging it with the element in the second position, and doing in this way until the entire array is sorted. This method is called selection sort because it repeatedly selects the smallest element in the yet unsorted part of the array. Because selection sort involves accessing the list at various points in a more-or-less random fashion, it is not a good algorithm to use with data stored as a linked list, since a great deal of time will be used traversing the list trying to locate the correct elements at each step, and then reassigning the pointers.

What is a Shell sort and how does it work?


(This is from the website: http://www.mnu.samara.ru/St_Works/Leo/SortAlg/)
   This sorting algorithm is conceived by D. L. Shell, and is inspired by the Insertion Sort's ability to work very fast on an array that is almost in order. It is also called diminishing increment sort. Unlike Insertion Sort, Shell Sort does not sort the entire array at once. Instead, it divides the array into noncontiguous segments, which are separately sorted by using Insertion Sort. Once all of the segments are sorted, Shell Sort re-divides the array into less segments and repeat the the algorithm until at last that the number of segment equals one, and the segment is sorted.

Back to the Main CS Website    Home