LAB1 TOM-PSR

Instrukcja laboratoryjna nr 1

Sortowanie tablicy podzielonej na części

oprac. Robert Tomaszewski

ZADANIE: Napisz w języku C program, który pobiera od użytkownika 20 liczb zapisując je do tablicy.

Następnie jedną połowę tablicy przekazuje do posortowania jednej procedurze, potem drugą połowę – drugiej

procedurze (w rzeczywistości może to być ta sama procedura dla obu połówek tablicy – trzeba jedynie

pamiętać o odpowiednich parametrach przekazywanych do procedury podczas jej wywołania). Po

posortowaniu dowolną metodą połówek tablicy wyświetl je i przekaż do ostatniej procedury, która dokona

scalenia tablicy w jedną, posortowaną całość. Wyświetl rezultat końcowy.

Wskazówki:

Ostatni etap sortowania opisany powyżej występuje w informatyce pod nazwą „scalanie” lub „merge”. W

związku z tym, że obie połówki mogą być sortowane niezależnie, powyższy problem nadaje się idealnie do

zrównoleglenia (co będzie tematem kolejnych zajęć laboratoryjnych). Do sortowania obu połówek można

wykorzystać dowolną z metod, np. QuickSort, InsertionSort, BubbleSort, itp..

Program napisz i przetestuj w jednym z dostępnych w pracowni środowisk programowania: CodeBlocks, Dev

C++, MinGW Studio, inne.

PRZYDATNE ŹRÓDŁA:

Opis algorytmu MERGE wraz z pseudokodem na Wikipedii:

http://pl.wikipedia.org/wiki/sortowanie_przez_scalanie

Kolejny opis algorytmu MERGE:

http://www.algorytm.org/index.php?option=com_content&task=view&id=179&Itemid=28

Przykładowy kod algorytmu MERGE budowany krok-po-kroku:

http://en.literateprograms.org/Category:Merge_sort

ZADANIE1
ROZWIĄZANIE 1
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <time.h>

int tab[20];
int i,min,max;

void bubblesort( int tab[], int n )
{
int i,j;
int tmp;
int change;

for (i=0; i<n-1; ++i)
{
       change=0;
       for (j=0; j<n-1-i; j++)
          if (tab[j+1] < tab[j])   //porównanie sąsiądów
          {
              tmp = tab[j];
              tab[j] = tab[j+1];
              tab[j+1] = tmp;    //wypchanie bąbelka
              change=1;
          }
       if(!change) break;      // nie dokonano zmian - koniec!
}
}
int main(int argc, char *argv[])
{
printf("Podaj 20 liczbn");
for (i=0 ; i<=19 ; i++)
{
printf("Podaj liczbe %d ",i);
scanf("%d",&tab[i]);
}

bubblesort (tab,20);

for (i=0 ; i<=19 ; i++)
{
printf("Podaj liczbe %d ",tab[i]);
}

system("PAUSE");
return 0;
}

Rozwiązanie 2
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <time.h>

int tab[20];
int tab1[10];
int tab2[10];
int i,min,max;
void bubblesort( int tab[], int n )
{
int i,j;
int tmp;
int change;

for (i=0; i<n-1; ++i)
{
       change=0;
       for (j=0; j<n-1-i; j++)
          if (tab[j+1] < tab[j])
          {
              tmp = tab[j];
              tab[j] = tab[j+1];
              tab[j+1] = tmp;
              change=1;
          }
       if(!change) break;
}
}

void bubblesort2( int tab[], int n )
{
int i,j;
int tmp;
int change;

for (i=0; i<n-1; ++i)
{
       change=0;
       for (j=0; j<n-1-i; j++)
          if (tab[j+1] < tab[j])
          {
              tmp = tab[j];
              tab[j] = tab[j+1];
              tab[j+1] = tmp;
              change=1;
          }
       if(!change) break;
}
}

int main(int argc, char *argv[])
{
srand( (unsigned)time( NULL ) );
printf("Podaj 20 liczbn");
for (i=0 ; i<=20 ; i++)
{
printf("Podaj liczbe %d ",i);
scanf("%d",&tab[i]);
//rand() >> tab[i];

}
for(i=0 ; i<=20 ; i++){
   if (i<=10){
              tab1[i]=tab[i];
   }else{
         tab2[i-10]=tab[i];
         }
}

bubblesort(tab1,10);
bubblesort(tab2,10);

for (i=0 ; i<10 ; i++)
{
printf("Tablica 1n");
printf("%d, ", tab1[i]);
}
for (i=0 ; i<10 ; i++)
{
printf("Tablica 2n");
printf("%d, ", tab2[i]);
}
system("PAUSE");
return 0;
}