Skip to main content

Fusion sort


The usual dumb algorithms for sorting things require a number of operations proportional to the square of the number of elements to sort (O(n2)). In practice, the used algorithms require a number of operations proportional to n×log n.

 The first one is the fusion sort.

 The main point is that given two sorted list of numbers, generating the sorted merged list needs a number of operations proportional to the size of this result list. Two index indicate the next elements to take from each list, and one indicates where to store the smallest of the two (see figure 7.3). This process can be iterated, starting with packets of size 1 (which are already sorted ...) and merging them each time two by two (see figure 7.4). After k iterations of that procedure, the packets are of size 2k, so the number of iterations for this process is log2 n where n is the total number of objects to sort.
Each step of this main process cost the sum of the sizes of the resulting packets, which is n. Finally the total number of operations is Plog 2 n i=1 n = n × log2 n.


Labels:

Popular posts from this blog

C++ Program to find the sum, difference, product and quotient of two integers

#include <iostream.h> #include <conio.h> void main() {   clrscr();   int x = 10;   int y = 2;   int sum, difference, product, quotient;   sum = x + y;   difference = x - y;   product = x * y;   quotient = x / y;   cout << "The sum of " << x << " & " << y << " is " << sum << "." << endl;   cout << "The difference of " << x << " & " << "y <<  is " << difference << "." << endl;   cout << "The product of " << x << " & " << y << " is " << product << "." << endl;   cout << "The quotient of " << x << " & " << y << " is " << quotient << "." << endl;   getch(); }
Read more

Program of virtual piano

//////////////Tested And Created By C++/////////////////////////////// #include<stdio.h> #include<dos.h> #include<conio.h> #include<stdlib.h> #define SHOW 1 #define HIDE 2 union REGS input,output; class piano {  public:int BIGKEY,MIDKEY,back,border;     piano()//init constructor     {         BIGKEY=15;         MIDKEY=1;         back=7;         border=15;     } }color; void drawpiano(int x,int y); int check_xy(int x,int y); void BOX(int c,int r,int c1,int r1,int col); int initmouse(); void setupscreen(); void pointer(int on); void restrictmouse(int x1,int y1,int x2,int y2); void check_keys(int x,int y); void getmouse(int *button,int *x,int *y); float freq[7] = {130.81, 146.83, 164.81, 174.61,196, 220, 246.94 } ; int n=0,a=4,backcolor=2,exitcode=1; void showbar(int t) {  if(t>65) t=65;  if(t<1) t=1;  textcolor(15);  for(int q=0;q<=t;t++)  {     gotoxy(3+q,4);     cprintf("Û");  } } void main() {  int
Read more

Putimage function in c

putimage function outputs a bit image onto the screen. Declaration:- void putimage(int left, int top, void *ptr, int op); putimage puts the bit image previously saved with getimage back onto the screen, with the upper left corner of the image placed at (left, top). ptr points to the area in memory where the source image is stored. The op argument specifies a operator that controls how the color for each destination pixel on screen is computed, based on pixel already on screen and the corresponding source pixel in memory. c smiling face animation This animation using c draws a smiling face which appears at random position on screen. See output below the code, it will help you in understanding the code easily. C programming code #include<graphics.h> #include<conio.h> #include<stdlib.h>   main() { int gd = DETECT, gm, area, temp1, temp2, left = 25, top = 75; void *p;   initgraph(&gd,&gm,"C:\\TC\\BGI");   setcolor(YELLOW);
Read more