SOISK - SYSTEMY OPERACYJNE I SIECI KOMPUTEROWE
Tomasz Puchała

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








ZADANIE
1
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;
}