Latest revision as of 14:25, 27 April 2011

Binary & Selection Sort

Binary Search

Cuts the search area in half every time until the number is found

(caveat – the list must be sorted for the binary search to work)

For Example: Search for a number between 0 and 100. Search for : 63

| |||||||||||||||||||||| O 50 100 (first search eliminates anything less than 50)

|||||||||||||||| | 50 75 100 (second search eliminates anything greater than 75)

| ||||||||||||||||||||| 50 63 75 (at this point, the algorithm sees that 63 is one of the boundaries and the number has been found)

Code for a Binary Search: int binary_search(int *v,int value, int min_ndx,int max_ndx){

   int mid_ndx = (max_ndx + min_ndx)/2;
   
   //Base Step 1 - Ensures that the minimum index is larger than the maximum index
   if (min_ndx > max_ndx){
       return -1;
   }
   
   //Baser Step 2 - Checks to see if the Middle Value is the Value that is being searched for
   if(v[mid_ndx] == value){
       return mid_ndx;
   }
   
   //Recursive Steps
   
   if (value < v[mid_ndx]){
       return binary_search(v, value, min_ndx, mid_ndx - 1);
   }
   else {
       return binary_search(v, value, mid_ndx + 1, max_ndx);
   }

}

Selection Sort

Example: Sort the following list of numbers 14,4,92,74,3

(N.B. - the bolded numbers are the ones that the algorithm is searching through)

14 4 92 74 3 (First iteration - looks for the smallest number out of the entire set – “3” - and switches its location with the first element in the list)

3 4 92 74 14 (Second iteration – finds the smallest number left in the search set – “4” – and switches it’s location with the second element in the list. In this particular example, the four is in its proper location from the initial list, so no changes are )

3	4	92	74	14

(Third Iteration – finds “14” as the smallest number swaps it with the number in the third position on the list)

3 4 14 74 92 (Fourth iteration – finds “74” as the smallest number and swaps it with the fourth number in the list.)

Because there are only 5 elements in this list, the algorithm will only run 4 loops. By definition, the fifth loops would show that the last number is in the correct position.

Code for a Selection Sort: void selection_sort(int *v,int items){

   int i,j;
   for (i = 0;i < items -1;i++){
       int min_ndx;
       int min_value = v[i];
       
       for (j = i;j < items;j++){
           if (v[j] < min_value){
               min_value = v[j];
               min_ndx = j;
           }
       }
       v[min_value] = v[i];
       v[i] = min_value;
   }

}

Back to ECE264