We are still actively working on the spam issue.

Programming concepts

From InstallGentoo Wiki
Revision as of 09:58, 28 January 2014 by Chchjesus (talk | contribs) (Search Algorithms)
Jump to: navigation, search

This article needs to be improved.

Fundamentals are important, so here are some.

Sorting Algorithms

A big topic in computer applications is the quick and efficient sorting of data. There are many different sorting techniques, as a programmer one has to balance the algorithm's ease of reading vs the efficiency of said code. Many standard libraries/APIs already have sorting functions already written, however it is still good practice to know some of the theory behind how the different algorithms work.

Bubble Sort

The bubble sort is a very simple to read algorithm that is the standard first sorting method that most programmers learn. The bubble sort gets its name because values are swapped among each other, gradually moving to the top of the list.

//bubble sort example
#include <stdio.h>
#define SIZE 10
int main( void ){
int a[SIZE] = {2,6,9,1,4,15,7,2}; //array to be sorted
int count; //to be used to count passes
int i; //comparisons counter
int hold; //temp variable to hold numbers
//start of bubble sort
for(count=0; count<SIZE-1; count++){//loop to control number of passes
//size is decreased by 1 to prevent array out of bounds error
for(i=0; i<SIZE-1; i++){//comparison loop
if(a[i]>a[i+1]){//if a[i] bigger than a[i+1], swap values
hold = a[i];
a[i] = a[i+1];
a[i+1] = hold;
}//end if
}//end inner for
}//end outer for
//print array
for(i=0; i<SIZE; i++)
printf("%4d", a[i]);
return 0;
}

Selection Sort

A bit further up on the food chain is the selection sort. The selection sort goes through each element position and finds the value which should occupy the next position in the sorted array. When it finds the appropriate element, the algorithm exchanges it with the valuewhich previously occupied the desired position. On the second pass it looks for the second smallest element and swaps it with the second position and so on.

//Selection sort example
// finds smallest element between left hand and right hand
// moves element to correct position
  1. include <stdio.h>
void selectionSort(int array[], int n){
//n is length
int lh, rh, i, temp;
for (lh=0; lh < n; lh++){//everything left of lh is considered sorted
rh = lh; //reset right hand
//runs through lh-rh bounds of array
for (i = lh + 1; i<n; i++){
//if lowest element found, copy index to right hand
if (array[i] < array[rh]) rh = i;
}
//move lowest element to correct position
temp = array[lh];
array[lh] = array[rh];
array[rh] = temp;
}
}
int main( void ){
int len = 8;
int a[8] = {2,6,9,1,4,15,7,2}; //array to be sorted
int i;
selectionSort(a, len);
//print array
for(i=0; i<len; i++)
printf("%4d", a[i]);
return 0;
}

Merge sort

Performance

Search Algorithms

Two of the main searching algorithms are Knuth-Morris-Pratt (KMP) and the Boyer-Moore (BM) algorithms.

Recursion

Linked Lists

Binary Search Trees

Hash Tables