Computer Science - Data Structure - Sorting

Ehh.... weren't we talking about japanese ???
Yes, but as the title of my blog says this blog won't be only for learning japanese, it will handle many subjects at the same time. Each person consulting it can make personal use the informations provided. Please don't hesitate to coment, or even leave send me e-mails about your impressions or advices or critics or whatever you want :p but the most important thing to do is to enjoy reading xP


So in this post we're going to talk about sorting types just some types i ll try to summarize the main idea of two or three we use the most, i ll try to be as clear as possible, all of this using C-Language.

Bubble sort (Tri à bulles) :

Example : (from wikipedia)

How to remember :

• go across the tab from the end to the beginning with a first selector i=n;
• with a second selector j go from the beginning to i, go across the tab this time by swapping each two values that need to be.
• repeat the process with i-- and so on..

Program :



void tri_a_bulle (int t[],int n)
{
int i,j;
for(i=n-1;i>1;i--)
{
for(j=0;j<i;j++)
{
if(t[j]>t[j+1])
{
echanger(t+j,t+j+1); //echanger is a function that swaps two variables !
}
}
}
}


of course it's not the best version of the bubble sort, it's just a version i made to do exactly as the example shows. If there's any mistake or something isn't clear enough feel free to correct it in a coment or contact me directly. For the main program you'll find the download link at the end of this post, build&run it on your IDE like Code::Blocks (for windows) or Geany (for linux users), those two are my favorites by the way.



Let's move to a second type of sorting.

Insertion sort :

Example : (from wikipedia)

How to remember : 

• consider your tab sorted until the position i-1
• grab the T[i] and put it in "mem"
• seek in the previous sorted squares if mem is lower then T[i-1] then put T[i-1] in T[i], go on like this until you find the first value < mem, this time u stop and put the value mem in its right place

Program :


void tri_par_insertion (int t[], int n)
{
int i,j,mem;
for(i=1;i<n;i++)
{
mem=t[i];
j=i-1;
while(j>=0 && mem<t[j])
{
t[j+1]=t[j];
j--;
}
t[j+1]=mem;
}
}

Selection sort :

Example : (from wikipedia)

How to remember : 

• consider your tab sorted until the position i-1
• seek the minimum of the following squares
• put it in the i place, and repeat the same process until the end of your table

Program :


void tri_selection (int t[],int n)
{
int i,j,min;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(t[j]<t[min]) min=j;
}
echanger(t+i,t+min);
}
}

by this i end my post, it's not the best course you can find in the net of course but it's only my way of seeing things. hope you liked. Oh by the way here's the main.c file ^^!