Inf 2 7, informatyka
[ Pobierz całość w formacie PDF ]
UNIWERSYTET TECHNOLOGICZNO-PRZYRODNICZY
w Bydgoszczy
ZAKŁAD ELEKTROENERGETYKI
LABORATORIUM INFORMATYKI
INSTRUKCJA DO ĘWICZENIA VII
Metody sortowania i przeszukiwania tablic
Opracował:
dr inŇ. Marcin Drechny
Luty 2010 r.
2
1. Cel ęwiczenia
Celem ęwiczenia jest zapoznanie siħ z metodami sortowania oraz wyszukiwania
elementów w tablicach.
2. Wprowadzenie
Sortowanie polega na ustaleniu ŇĢdanej kolejnoĻci elementów tablicy. IstniejĢ róŇne metody
sortowania. JednĢ z popularniejszych jest metoda bĢbelkowa. Algorytm ten opiera siħ na
zasadzie porównywania i zamiany par sĢsiadujĢcych ze sobĢ elementów, tzn. przeglĢda siħ
elementy i porównuje bieŇĢcy element z nastħpnym. JeĻli pierwszy element jest wiħkszy od
drugiego, to zostajĢ zamienione miejscami. Nastħpnym krokiem jest odczyt kolejnego
elementu i porównanie go z poprzednim. CzynnoĻę tħ wykonujemy aŇ do osiĢgniħcia koıca
tablicy. Porównania naleŇy wykonywaę w pħtli do momentu gdy nie bħdzie zamiany
miejscami elementów podczas sprawdzania całej tablicy. Oznacza to koniec sortowania
danych. Ten sposób sortowania pozwala na ustawienie elementów od najmniejszego do
najwiħkszego. Sytuacja bħdzie odwrotna, gdy dane bħdziemy zamieniali miejscami, jeŇeli
element nastħpny bħdzie wiħkszy od poprzedniego. Wtedy sortujemy od elementu
najwiħkszego do najmniejszego.
InnĢ metodĢ jest metoda sortowania przez wybieranie. W pierwszym kroku wyszukujemy
najmniejszej liczby w ciĢgu i przestawiamy jĢ na poczĢtek ciĢgu elementów (poprzez
zamianħ jej z pierwszym elementem ciĢgu). Ponownie wyszukujemy najmniejszy elementu
ciĢgu (pomijajĢc element pierwszy) i po znalezieniu go zamieniamy z drugim elementem
ciĢgu. Postħpujemy w ten sposób tak długo aŇ zostanĢ zamienione ostatnia i przedostatnia
wartoĻę w tablicy. W ten sposób uzuskujemy posortowanĢ tablicħ od wartoĻci najmniejszej do
najwiħkszej.
Przykład 1: Zamiana wartoĻci zmiennych a i b. Zmienne a=23 i b=50.
#include <vcl.h>
#include<conio.h>
#include<iostream.h>
void main(void)
{
3
int a = 23;
int b = 50;
int temp;
clrscr();
cout<<" Wartosc zmiennej a przed zamiana wynosi: "<< a << endl;
cout<<" Wartosc zmiennej b przed zamiana wynosi: "<< b << endl;
temp = a;
a = b;
b = temp;
cout<<" Wartosc zmiennej a po zamianie wynosi: "<< a << endl;
cout<<" Wartosc zmiennej b po zamianie wynosi: "<< b << endl;
getch();
}
Wyszukiwanie sekwencyjne jest najprostszĢ metodĢ wyszukiwania. Zasada wyszukiwania tĢ
metodĢ polega na porównaniu zadanej liczby lub tekstu z kaŇdym elementem tablicy.
Porównanie elementów wykonujemy przy pomocy instrukcji warunkowej. ZaletĢ tej metody
jest prosty algorytm i program. GłównĢ jej wadĢ jest czasochłonnoĻę przy duŇych rozmiarach
tablic gdzie wiele porównaı jest zbħdnych.
Przykład 2: Wyszukiwanie sekwencyjne liczby 20 w tablicy jednowymiarowej,
5 elementowej o nazwie POMIAR.
#include<vcl.h>
#include<conio.h>
#include<iostream.h>
4
void main(void)
{
int tab[5] = {4, 27, 17, 20, 9};
int i;
clrscr();
for(i = 0; i<5; i++)
{
if (tab[i] == 20)
cout << "Znaleziono liczbe 20 w tablicy o indeksie " << i << endl;
}
getch();
}
UdoskonalonĢ metodĢ wyszukiwania jest wyszukiwanie binarne. Aby móc zastosowaę tħ
metodħ, naleŇy posortowaę tablicħ malejĢco lub rosnĢco. Wyszukiwanie rozpoczyna siħ od
sprawdzenia, czy Ļrodkowy element tablicy jest równy poszukiwanemu. JeĻli nie, procedura
sprawdza czy Ļrodkowy element jest mniejszy czy wiħkszy od poszukiwanego. W pierwszym
wypadku sprawdza Ļrodkowy element górnej połówki tablicy (zawierajĢcej wartoĻci wiħksze
od Ļrodkowego elementu). W drugim przypadku program sprawdza Ļrodkowy element dolnej
połówki tablicy. Wyszukiwanie binarne kontynuuje działanie w ten sposób, Ňe zmniejsza
liczbħ pozostałych elementów do sprawdzenia o połowħ, przy kaŇdym obrocie pħtli oraz
sprawdza Ļrodkowe elementy pozostałych wartoĻci, aŇ do chwili znalezienia poszukiwanej
wartoĻci.
5
Przykład 3: Wyszukiwanie binarne.
#include<vcl.h>
#include<conio.h>
#include<iostream.h>
void main(void)
{
int tab[10] = {3, 12, 15, 27, 32, 36, 45, 51, 74, 87};
int szukana;
int indeks;
int i_min = 0;
int i_max = 10;
int wyjscie = 0;
clrscr();
cout<<"Podaj wartosc szukanej liczby " << endl;
cin >> szukana;
do
{
indeks = (i_min + i_max)/2;
if (tab[indeks] == szukana)
{
wyjscie = 1;
} else
{
if (szukana > tab[indeks])
i_min = indeks + 1;
else
i_max = indeks - 1;
}
} while(wyjscie == 0);
cout << "Znaleziono szukana wartosc na miejscu " << indeks + 1 << " tablicy." << endl;
[ Pobierz całość w formacie PDF ]