Categories
Programming & Web Development

Select sort algorithm explained with code and dance

Select sort is a very simple algorithm but it’s very inefficient for large lists, but it is good when memory is an issue, since it is an in-place sorting algorithm. Meaning it is an algorithm that doesn’t need to use extra memory to store sorted from unsorted elements.

The way it works is the following: Take the fist element in the list and compare with the next elements to find the minimum value of the list. If found swap values. Repeat starting with second element and so on until reaching the last element in the list.

Select sort example

Big-O notation

O(n2)

Pseudo code

for each current_element in the list:
  assume_minimum = current_element
  for each element in the list:
     if assume_minimum > element[value]
        assume_minimum = element[value]
  swap current element with assume_minimum values

PHP code example

/**
 * Select sort
 *
 * @param array $list The unsorted list
 * @return array The sorted list
 */
function select_sort($list) {
  for($i = 0; $i <= count($list); $i++) {
      $min_position = $i;
      for($j = $i + 1; $j <= count($list); $j++) {
          if($list[$min_position] > $list[$j]) {
              $min_position = $j;
          }
      }
      list($list[$i], $list[$min_position]) = array($list[$min_position], $list[$i]);
  }
  return $list;
}

Python code example

def select_sort(a_list):
  """ Performs a select sort on list """
  for i in range(0,len(a_list)-1):
    min_position = i
    for j in range(i+1,len(a_list)):
      if a_list[min_position] > a_list[j]:
        min_position = j
    a_list[i], a_list[min_position] = a_list[min_position], a_list[i]
  return a_list

Gypsy folk dance example

Categories
Programming & Web Development

Insert-sort algorithm explained with code and dance

Insert sort is a fast algorithm for small lists. On some languages, insert sort is used to sort small arrays (small sometimes means less than 10) instead of more complex algorithms because it’s fast enough and doesn’t need much memory.

Insertion sort example

To perform Insert-sort: take one element from the list on each iteration, starting from the first, and compare with the next element. If the previous one is greater, move it one position ahead. Continue comparing the rest of the elements pushing them forward until you find a the place of the current value and no elements are left. Repeat with next element in list.

Big-O notation

O(n2)

Pseudo code

function insert_sort(list):
  (evaluate the list forward)
  for i from 1 to length_of_list - 1:
    value = list[i]
    (evaluate the list backward from i):
    while prev_position >= 0 and list[prev_position] > value:
      (swap values from current position to the next)
      list[prev_position+1] = list[prev_position]
      go on position back in the list
    if there was no swap, set value back in current position

PHP code example

function insert_sort($list) {
    for($i = 0; $i < count($list); $i++) {
        $value = $list[$i];
        $j = $i - 1;
        while($j >= 0 AND $list[$j] > $value) {
            $list[$j + 1] = $list[$j];
            $j--;
        }
        $list[$j + 1] = $value;
    }
    return $list;
}

Python code example

def insert_sort(unordered_list):
    for i in xrange(0,len(unordered_list)):
        value = unordered_list[i]
        j = i -1
        while (j >= 0) and (unordered_list[j] > value):
            unordered_list[j+1] = unordered_list[j]
            j -= 1
        unordered_list[j+1] = value
    return unordered_list

Insert sort algorithm can be explained better visually with a Romanian folk dance:

Categories
Programming & Web Development

Basic programming algorithm: Bubble Sort

Bubble sort is one of the most basic sorting algorithms in taught in computer science classes. It will order values in a list from smallest to largest passing several times through the list comparing two items at a time and reordering them. This algorithm is not very efficient with large lists because it has to evaluate every member of the list several times. The longer the list, the more it will take the algorithm to finish. In big-O notation, this algorithm’s efficiency is represented by: O(n2)

An explanation of bubble sort from Wikipedia:

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

bubble sort example

While passing through the list, compare two elements, if the second one is bigger than the first, swap their positions in the list. Continue going through the list, comparing the next elements in the same way. Go through the list until no more swaps take place.

Pseudocode:

while not sorted:
  sorted = True
  for iterator = 1 to length_of_list - 1 do:
    check if pair is out of order:
    if list[iterator] is bigger than list[iterator+1] then
    swap them:
      temporal_value = list[iterator]
      list[iterator] = list[iterator+1]
      list[iterator+1] = temporal_value
      sorted = False
      skip to next element in list

PHP code example:

/**
 * Sort an array using bubble sort algorithm
 * @param array $list The list to be sorted
 * @return array The sorted array
 */
function bubbleSort($list) {
   while(!$sorted){
     $sorted = True;
     foreach($list as $key => $value) {
        if($list[$key] > $list[$key+1]) {
          $temp = $list[$key+1];
          $list[$key+1] = $list[$key];
          $list[$key] = $temp;
          $sorted = False;
        }
     }
   }
   return $list;
}

Python code example:

function bubbleSort(a_list):
  """ Sort an array using bubble sort algorithm """
  sorted = False
  length = len(a_list)
  while not sorted:
     sorted = True
     for position in range(length):
       if a_list[position] > a_list[position+1]:
         # Swap values
         a_list[position], a_list[position+1] = a_list[position+1], a_list[position]
         sorted = False
  return a_list

There is another way to write the bubble sort, by shrinking the list by one element after every pass. If you see the animated graphic above, after each pass, the last number is already in its correct place, so you don’t have to iterate over those every subsequent time. You can discard the last element each time, making the algorithm faster.

An example of this version in Python code would look like this:

function betterBubbleSort(a_list):
  """ Sort an array using bubble sort algorithm """
  length = len(a_list)
  while length:
     for position in range(length):
       if a_list[position] > a_list[position+1]:
         # Swap values
         a_list[position], a_list[position+1] = a_list[position+1],a_list[position]
     length -= 1
  return a_list

Do you have other ways of writing the bubble sort? Share them in the comments section below.

Categories
personal

Learn better by sharing your knowledge

Reading Sacha Chua’s blog post on testing what you know by sharing inspired me on how to practice some basic computer science skills I have not used much in a while but are very useful to have freshly in mind. I’ve been wanting to improve my computer algorithm knowledge skills for a while, but never got around to it, putting the task aside for “other important things”.

For a very basic start, an algorithm is a series of steps to accomplish something. A cooking recipe can be an algorithm for the dish, and like every recipe, there are several ways to make the same dish.

See, that wasn’t hard to explain at all! I hope the rest comes as easy as this one.

By sharing what I learn here in my blog, I will need to comprehend fully the concepts to write them down and I will also be practicing my programming skills, keeping a log of my notes for future reference and sharing with other people interested in the topic. Hopefully I will get comments with better ways to explain this concepts or better code examples. So this looks like a win-win situation for everyone.

By the way, if you want to read a fun blog with a mixture of cooking recipes (or algorithms) and politics, check out Tacos and Politics.