Forum Informatyka Strona Główna Informatyka
Forum I-go roku wydziału informatycznego UW
 
 POMOCPOMOC   FAQFAQ   SzukajSzukaj   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Ćwiczenia - merge

 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka Strona Główna -> ALGORYTMY I STRUKTURY DANYCH
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Marek_Z
moderator
moderator


Dołączył: 08 Paź 2007
Posty: 59

PostWysłany: Wto Maj 19, 2009 19:24    Temat postu: Ćwiczenia - merge Odpowiedz z cytatem

// Sortowanie przez scalanie (mergesort)
// Koszt algorytmu w każdym przypadku:
// T(n)=n log n

#include <cstdlib>
#include <iostream>
#include <conio.h>
using namespace std;
char kontrol;
int licznik;
int N;
int *tab= new int[N];
int *t= new int[N]; // Tablica pomocnicza

/* Scalanie dwoch posortowanych ciagow
tab[pocz...sr] i tab[sr+1...kon] i
wynik zapisuje w tab[pocz...kon] */

void pokaz(int dlugosc)//wyswietla tabele
{
int k=0;
for(k=0;k<dlugosc;k++)
{
cout<<tab[k]<<" ";
}
cout<<endl;
}

void merge(int pocz, int sr, int kon)
{
int i,j,q;
for (i=pocz; i<=kon; i++) t[i]=tab[i]; // Skopiowanie danych do tablicy pomocniczej
i=pocz; j=sr+1; q=pocz; // Ustawienie wskaźników tablic
while (i<=sr && j<=kon) { // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
if (t[i]<t[j])
{
tab[q++]=t[i++];

}
else
{
tab[q++]=t[j++];

}
}
while (i<=sr)
{
tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył

}

}

/* Procedura sortowania tab[pocz...kon] */
void mergesort(int pocz, int kon)
{
int sr, i;
if (pocz<kon) {
sr=(pocz+kon)/2;
mergesort(pocz, sr); // Dzielenie lewej części

mergesort(sr+1, kon); // Dzielenie prawej części

merge(pocz, sr, kon); // Łączenie części lewej i prawej
}
}

int main() {
int i;

licznik=0;
while (kontrol != 'n' && kontrol != 'N')
{


cout<<"Wpisz dane: ";
cin>>tab[licznik];
licznik=licznik+1;
cout<<endl;
system("cls");
cout<<"Czy chcesz wprowadzic nastepne dane - t(ak) / n(ie) ?"<<endl;
kontrol=getch();
system("cls");

}



printf("Tablica przed sortowaniem:\n");
pokaz (licznik);
cout<<endl;

cout<<"Sortowanie"<<endl;
cout<<endl;

N=licznik;

mergesort(0,N-1);

cout<<endl;
printf("\nZbior po sortowaniu:\n");
cout<<endl;

pokaz (licznik);

cout<<endl;
system("pause");
return 0;
}
_________________
Marek ZIN 3 (kiedyś 6)
Powrót do góry
Ogląda profil użytkownika Wyślij prywatną wiadomość
Reklama






Wysłany: Wto Maj 19, 2009 19:24    Temat postu:

Powrót do góry
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka Strona Główna -> ALGORYTMY I STRUKTURY DANYCH Wszystkie czasy w strefie CET (Europa)
Strona 1 z 1
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

Informatyka  

To forum działa w systemie phorum.pl
Masz pomysł na forum? Załóż forum za darmo!
Forum narusza regulamin? Powiadom nas o tym!
Powered by Active24, phpBB © phpBB Group