AISD wer. 2 str. 73
Sortowanie i wyszukiwanie
Metody sortowania:
-
według klucza (wybranej wartości)
-
według cyfrowych własności klucza (bitów) (ang. radix sorts)
Kategorie sortowania:
-
wewnętrzne sortowanie (dane są w pamięci operacyjnej)
-
zewnętrzne sortowanie (dane w zbiorach danych)
Proste metody sortowania:
-
przez wstawianie (ang. Insertion Sort)
-
wstawianie do listy (ang. Linked List Insertion Sort)
-
przez wybieranie (ang. Selection Sort)
-
sortowanie bąbelkowe (ang. Bubble Sort)
Zaawansowane metody sortowania:
-
Shell Sort
-
Quick Sort
-
Merge Sort
-
Binary Tree Sort
-
Heap Sort
-
Straight Radix Sort
-
Radix Exchange Sort
class Base_Sort {
public:
void build_list (DATA_TYPE input[]);
void debug_print (int iteration, int debug, char *hdr);
void Insertion_Sort (DATA_TYPE input[]);
void Selection_Sort (DATA_TYPE input[]);
void Bubble_Sort (DATA_TYPE input[]);
void Quick_Sort (DATA_TYPE input[]);
void Heap_Sort (DATA_TYPE A[]);
void Radix_Exch_Sort (DATA_TYPE input[], int bitnum);
void Shell_Sort (DATA_TYPE input[]);
void Merge_Sort (char *sorted_file_name); // Dissimilar
void Insert_Sort_dlist (void); // Doubly linked list sort
};
Sortowanie przez wstawianie (ang. Insertion Sort)
#include <stdio.h>
typedef int DATA_TYPE;
typedef DATA_TYPE ARY_LIST[];
class Sort {
private:
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
AISD wer. 2 str. 74
Sort (int size) { A = new DATA_TYPE[n=size]; }
~Sort() { delete []A; }
void build_list (DATA_TYPE input[]);
void debug_print (int iteration, int debug, char *hdr);
void Insertion_Sort (DATA_TYPE input[]);
};
void Sort::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Sort::debug_print (int iteration, int debug, char *hdr)
{
if (debug == 0)
printf("\n %s \n", hdr);
else
printf(" Pass #%d:", iteration + 1);
for (int i = 0; i < n; i++)
printf(" %d", A[i]);
printf("\n");
}
void Sort::Insertion_Sort (ARY_LIST input)
{
build_list(input); // Build array A
debug_print (0, 0, "List to be sorted in ascending order:");
int begin = n - 2;
for (int k = begin; k >= 0; k--) { // Outer loop
int i = k + 1;
DATA_TYPE swap_area = A[k];
while (swap_area > A[i]) { // inner loop
A[i - 1] = A[i];
i++;
}
A[i - 1] = swap_area;
debug_print (n - 2 - k, 1, "");
}
}
void main(void)
{
Sort insert_srt_obj (10);
static ARY_LIST A = {33, 60, 5, 15, 25,
12, 45, 70, 35, 7 };
printf("\n ** OOP IMPLEMENTATION OF %s",
"INSERTION SORT **");
insert_srt_obj.Insertion_Sort (A);
insert_srt_obj.debug_print (0, 0,
"List sorted using insertion sort:");
}
Sortowanie przez wstawianie ma złożoność O(n
2
) dla najgorszego przypadku. Jest proste i
wydajne dla małego n. Wadą jest to, że umieszcza prawidłowo tylko jeden element dla
pojedynczego kroku.
AISD wer. 2 str. 75
Sortowanie przez wstawianie do listy (ang. Linked List Insertion Sort)
#include <stdio.h>
#include <stdlib.h>
const int FOREVER = 1;
typedef int DATA_TYPE;
class Doubly_Linked_List {
private:
typedef struct DLIST_ELEMENT {
DATA_TYPE data;
DLIST_ELEMENT *next;
DLIST_ELEMENT *prev;
} *DLLIST_PTR;
DLLIST_PTR head_ptr, tail_ptr, curr_ptr;
void init_dlist (void);
public:
Doubly_Linked_List () { init_dlist(); }
~Doubly_Linked_List () { };
void build_dlist (void);
void Insert_Sort_dlist (void);
void print_dlist (void);
};
void Doubly_Linked_List::init_dlist (void)
{
head_ptr = tail_ptr = curr_ptr = NULL;
}
void Doubly_Linked_List::build_dlist (void)
{
DLLIST_PTR prev_ptr = NULL,
new_ptr;
char buffer[81];
printf ("\n ** OOP FOR INSERTION SORT OF %s \n\n",
"A DOUBLY LINKED LIST **");
while (FOREVER) {
printf ("\nCreate List - <Return> with no Value to Quit");
printf ("\nEnter an Integer: ");
gets (buffer);
if (buffer[0] == '\0') {
tail_ptr = curr_ptr; // initialize tail pointer
return;
}
new_ptr = new DLIST_ELEMENT;
new_ptr->data = atoi (buffer);
new_ptr->next = NULL;
new_ptr->prev = NULL;
curr_ptr = new_ptr;
if (head_ptr == NULL) // initialize head pointer
head_ptr = curr_ptr;
else {
curr_ptr->prev = prev_ptr; // link element
prev_ptr->next = curr_ptr;
}
prev_ptr = curr_ptr;
}
}
void Doubly_Linked_List::Insert_Sort_dlist (void)
{
DLLIST_PTR curr_ptr = head_ptr, search_ptr;
AISD wer. 2 str. 76
while ((curr_ptr = curr_ptr->next) != NULL) {
search_ptr = curr_ptr->prev;
while (search_ptr != NULL &&
curr_ptr->data < search_ptr->data)
search_ptr = search_ptr->prev;
if ((curr_ptr->prev != search_ptr) &&
(search_ptr != NULL ||
curr_ptr->data < head_ptr->data)) {
curr_ptr->prev->next = curr_ptr->next;
if (curr_ptr == tail_ptr)
tail_ptr = curr_ptr->prev;
else
curr_ptr->next->prev = curr_ptr->prev;
if (search_ptr != NULL) {
curr_ptr->prev = search_ptr;
curr_ptr->next = search_ptr->next;
search_ptr->next->prev = curr_ptr;
search_ptr->next = curr_ptr;
}
else { // curr_ptr->data < head_ptr->data
curr_ptr->prev = NULL;
curr_ptr->next = head_ptr;
head_ptr->prev = curr_ptr;
head_ptr = curr_ptr;
}
}
}
}
void Doubly_Linked_List::print_dlist (void)
{
DLLIST_PTR tmp_ptr = head_ptr;
printf ("NULL <-> ");
while (tmp_ptr != NULL) {
printf ("%d <-> ", tmp_ptr->data);
tmp_ptr = tmp_ptr->next;
}
printf ("NULL \n");
}
void main (void)
{
Doubly_Linked_List dlist_obj;
dlist_obj.build_dlist ();
printf ("\nDoubly Linked List Before %s \n",
"Insertion Sort is:");
dlist_obj.print_dlist ();
printf ("\nDoubly Linked List After %s \n",
"Insertion Sort is:");
dlist_obj.Insert_Sort_dlist ();
dlist_obj.print_dlist ();
}
Sortowanie przez wybieranie (ang. Selection Sort)
#include <stdio.h>
class Sort {
private:
typedef int DATA_TYPE;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
AISD wer. 2 str. 77
int n; // size of A
public:
Sort (int size) { A = new DATA_TYPE[n=size]; }
~Sort() { delete []A; }
void build_list (DATA_TYPE input[]);
void debug_print (int iteration, int debug, char *hdr);
void Selection_Sort (DATA_TYPE input[]);
};
void Sort::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Sort::debug_print (int iteration, int debug, char *hdr)
{
if (debug == 0)
printf("\n %s \n", hdr);
else
printf(" Pass #%d:", iteration + 1);
for (int i = 0; i < n; i++)
printf(" %d", A[i]); printf("\n");
}
void Sort::Selection_Sort (ARY_LIST input)
{
build_list(input); // Build array A
debug_print (0, 0, "List to be sorted in ascending order:");
if (n > 0) {
for (int j = 0; j < n - 1; j++) {
int lower = j;
for (int k = j + 1; k < n; k++)
if (A[k] < A[lower])
lower = k;
DATA_TYPE swap_area = A[j];
A[j] = A[lower];
A[lower] = swap_area;
debug_print (j, 1, "");
}
}
}
void main(void)
{
Sort select_srt_obj (10);
static ARY_LIST A = {33, 60, 5, 15, 25,
12, 45, 70, 35, 7 };
printf("\n ** OOP IMPLEMENTATION OF %s",
"SELECTION SORT **");
select_srt_obj.Selection_Sort (A);
select_srt_obj.debug_print (0, 0,
"List sorted using selection sort:");
}
Złożoność algorytmu dla sortowania przez wybieranie jest O(n
2
).
Sortowanie bąbelkowe (ang. Buble Sort)
AISD wer. 2 str. 78
#include <stdio.h>
const int TRUE = 1;
const int FALSE = 0;
class Sort {
private:
typedef int DATA_TYPE;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
Sort (int size) { A = new DATA_TYPE[n=size]; }
~Sort() { delete []A; }
void build_list (DATA_TYPE input[]);
void debug_print (int iteration, int debug, char *hdr);
void Bubble_Sort (DATA_TYPE input[]);
};
void Sort::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Sort::debug_print (int iteration, int debug, char *hdr)
{
if (debug == 0)
printf("\n %s \n", hdr);
else
printf(" Pass #%d:", iteration + 1);
for (int i = 0; i < n; i++)
printf(" %d", A[i]);
printf("\n");
}
void Sort::Bubble_Sort (ARY_LIST input)
{
int swap_flag = TRUE;
build_list(input); // Build array A
debug_print (0, 0, "List to be sorted in ascending order:");
for (int iteration = 0; iteration < n &&
swap_flag == TRUE; iteration++) {
swap_flag = FALSE;
for (int i = 0; i < n - iteration; i++)
if (A[i] > A[i + 1]) {
swap_flag = TRUE;
DATA_TYPE swap_area = A[i];
A[i] = A[i + 1];
A[i + 1] = swap_area;
}
debug_print (iteration, 1, "");
}
}
void main(void)
{
Sort bubble_srt_obj (10);
static ARY_LIST A = {33, 60, 5, 15, 25,
12, 45, 70, 35, 7 };
printf("\n ** OOP IMPLEMENTATION OF %s", "BUBBLE SORT **");
bubble_srt_obj.Bubble_Sort (A);
bubble_srt_obj.debug_print (0, 0, "List sorted using bubble sort:");
AISD wer. 2 str. 79
}
Złożoność obliczeniowa dla najgorszego przypadku jest O(n
2
).
Wady metody:
1.
W pojedynczym kroku iteracji tylko jeden element osiąga swoją pozycję.
2.
Liczba operacji wymiany elementów (wzajemnej) może osiągać w kazdym kroku
iteracji wewnętrznej liczbę (n - iteration - i). Duże wymagania na przemieszczanie
elementów czynią sortowanie bąbelkowe nieefektywnym dla złożonych struktur
danych.
3.
Metoda ta silnie zależy od porównywania i zamiany tylko kolejnych elementów.
QUICKSORT
Quicksort oparty jest o 3 główne strategie:
- podział na podtablice
- sortowanie podtablic
- połączenie posortowanych podtablic
Algorytm rekursywny Quicksort.
Algorytm dzielenia tablicy:
1.
Element wybrany Pivot = A[First]
2.
Inicjalizacja dwóch indeksów
i = First (dolny indeks (pod)tablicy
j = Last (górny indeks (pod)tablicy
3.
Dopóki A[i] <= Pivot and i < Last zwiększaj i o 1. W przeciwnym przypadku
zaprzestaj zwiększania.
4.
Dopóki A[j] >= Pivot and j > First zmniejszaj j o 1. W przeciwnym przypadku
zaprzestaj zmniejszania.
5.
Jeśli i < j zamień wartości A[i] i A[j].
6.
Powtarzaj kroki 2. - 4. aż i > j (niespełnienie 5.)
7.
Zamień miejscami Pivot i A[j].
Przykład pierwszego kroku dla
A[] = {33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
#include <stdio.h>
class Sort {
private:
typedef int DATA_TYPE;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
int iter;
public:
Sort (int size) {iter =0; A = new DATA_TYPE[n=size];}
~Sort() { delete []A; }
void build_list (DATA_TYPE input[]);
void debug_print (int iteration, int debug, char *hdr);
void qsort (int First, int Last);
AISD wer. 2 str. 80
void Quick_Sort (DATA_TYPE input[]);
};
void Sort::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Sort::debug_print (int iteration, int debug, char *hdr)
{
if (debug == 0)
printf("\n %s \n", hdr);
else
printf(" Pass #%d:", iteration + 1);
for (int i = 0; i < n; i++)
printf(" %d", A[i]);
printf("\n");
}
void Sort::qsort (int First, int Last)
{
if (First < Last) {
DATA_TYPE Pivot = A[First];
int i = First;
int j = Last;
while (i < j) {
while (A[i] <= Pivot && i < Last)
i += 1;
while (A[j] >= Pivot && j > First)
j -= 1;
if (i < j) { // Swap the Pivots
DATA_TYPE swap_area = A[j];
A[j] = A[i];
A[i] = swap_area;
}
}
DATA_TYPE swap_area = A[j];
A[j] = A[First];
A[First] = swap_area;
debug_print (iter++, 1, "");
qsort (First, j - 1);
qsort (j + 1, Last);
}
}
void Sort::Quick_Sort (ARY_LIST input)
{
build_list(input); // Build array A
debug_print (0, 0, "List to be sorted in ascending order:");
if (n > 0)
qsort (0, n - 1);
}
void main(void)
{
AISD wer. 2 str. 81
Sort quick_srt_obj (10);
static ARY_LIST A = {33, 60, 5, 15, 25, 12, 45, 70, 35, 7};
printf("\n ** OOP IMPLEMENTATION OF %s", "QUICK SORT **");
quick_srt_obj.Quick_Sort (A);
quick_srt_obj.debug_print (0, 0, "List sorted using quick sort:");
}
Złożoność obliczeniowa Quicksort jest dla najlepszego przypadku i średnio O(nlogn). Dla
najgorszego przypadku złożoność obliczeniowa jest O(n
2
). Implementacja wymaga
intensywnego wykorzystywania stosu. Operacja podziału jest złożona, zaś operacja scalania
wyników jest prosta.
Merge Sort
Merge Sort jest metodą stosowaną do danych zewnętrznych (plików). Algorytm zawiera 3
części: podział, sortowanie, łączenie danych. Można wyróżnić 3 wersje Merge Sort:
- iteracyjną
- rekursywną
- ze wskazaniem (ang. link)
Algorytm Merge Sort (wersja iteracyjna dla pliku):
1.
Otwórz plik wejściowy nieposortowany UF do czytania i pisania, oraz dwa pliki
robocze TMP_F1 i TMP_F2 do pisania.
2.
(Split) Kopiuj po 1 (2
0
) elemencie pliku UF naprzemiennie do plików TMP_F1 i
TMP_F2.
3.
(Merge) Porównaj jednoelementowe grupy z TMP_F1 i z TMP_F2, zapisz je po
porównaniu do UF - najpierw mniejszą.
4.
(Split) Kopiuj po 2 (2
1
) elementy pliku UF naprzemiennie do plików TMP_F1 i
TMP_F2.
5.
(Merge) Porównaj dwuelementowe grupy z TMP_F1 i z TMP_F2, zapisz elementy
po porównaniu do UF - najpierw mniejszy.
6.
Powtarzaj proces podziału (Split) i łączenia (Merge) jak dla punktów 4. - 5. dla grup
o rozmiarach 2
i
dla i = 2, 3, ..., log
2
n.
7.
Plik jest posortowany rosnąco. Zamknij pliki i usuń robocze.
Przykład dla
UF = {10, 9, 23, 100, 39, 50, 20, 8, 36, 73, 244, 45, 29}
Wady metody iteracyjnej:
1. Nie jest uwzględniane, że część danych może być posortowana.
2. Metoda wymaga dwóch dodatkowych plików, każdy o rozmiarze n (maksymalnie).
3. Liczba elementów w plikach roboczych może być różna.
#include <stdio.h>
#include <stdlib.h>
AISD wer. 2 str. 82
#define MIN(x,y) ( (x <= y) ? x : y )
typedef int DATA_TYPE;
enum STATUS {UNSORTED, SORTED, DATA_AVAILABLE,
END_OF_FILE};
void Merge_Sort (char *sorted_file_name)
{
FILE *sorted_file, *tmp_file_1, *tmp_file_2;
enum STATUS status = UNSORTED, status_a, status_b;
DATA_TYPE a, b, last = 0;
int file = 1;
if ((sorted_file = fopen (sorted_file_name, "r+"))== NULL ||
(tmp_file_1 = fopen ("tmp_1.fil", "w+")) == NULL ||
(tmp_file_2 = fopen ("tmp_2.fil", "w+")) == NULL ){
printf("\nERROR: Files could not be opened!\n");
exit (-1);
}
while (status == UNSORTED) {
rewind (sorted_file);
fclose (tmp_file_1);
fclose (tmp_file_2);
remove ("tmp_1.fil");
remove ("tmp_2.fil");
tmp_file_1 = fopen ("tmp_1.fil", "w+");
tmp_file_2 = fopen ("tmp_2.fil", "w+");
while (fscanf (sorted_file, "%d", &a) != EOF) {
if (a < last) {
if (file == 1)
file = 2;
else // file == 2
file = 1;
}
last = a;
if (file == 1)
fprintf (tmp_file_1, "%d ", a);
else // file == 2
fprintf (tmp_file_2, "%d ", a);
} // End of while (fscanf...)
fclose (sorted_file);
remove (sorted_file_name);
sorted_file = fopen (sorted_file_name, "w+");
rewind (tmp_file_1);
rewind (tmp_file_2);
status_a = DATA_AVAILABLE;
status_b = DATA_AVAILABLE;
if (fscanf (tmp_file_1, "%d", &a) == EOF) {
status = SORTED;
status_a = END_OF_FILE;
}
if (fscanf (tmp_file_2, "%d", &b) == EOF) {
status = SORTED;
status_b = END_OF_FILE;
}
last = MIN (a, b);
AISD wer. 2 str. 83
while (status_a != END_OF_FILE &&
status_b != END_OF_FILE) {
if (a <= b && a >= last) {
fprintf (sorted_file, "%d ", a);
last = a;
if (fscanf (tmp_file_1, "%d", &a) == EOF)
status_a = END_OF_FILE;
}
else if (b <= a && b >= last) {
fprintf (sorted_file, "%d ", b);
last = b;
if (fscanf (tmp_file_2, "%d", &b) == EOF)
status_b = END_OF_FILE;
}
else if (a >= last) {
fprintf (sorted_file, "%d ", a);
last = a;
if (fscanf (tmp_file_1, "%d", &a) == EOF)
status_a = END_OF_FILE;
}
else if (b >= last) {
fprintf (sorted_file, "%d ", b);
last = b;
if (fscanf (tmp_file_2, "%d", &b) == EOF)
status_b = END_OF_FILE;
}
else
last = MIN (a, b);
} // end of while ( status_a ...)
while (status_a != END_OF_FILE) {
fprintf (sorted_file, "%d ", a);
if (fscanf (tmp_file_1, "%d", &a) == EOF)
status_a = END_OF_FILE;
}
while (status_b != END_OF_FILE) {
fprintf (sorted_file, "%d ", b);
if (fscanf (tmp_file_2, "%d", &b) == EOF)
status_b = END_OF_FILE;
}
} // end of "while (status == UNSORTED)"
fclose (sorted_file);
fclose (tmp_file_1 );
fclose (tmp_file_2 );
remove ("tmp_1.fil");
remove ("tmp_2.fil");
}
void main(void)
{
#ifdef DOS
system ("copy unsorted.fil sorted.fil");
#else
system ("cp unsorted.fil sorted.fil"); // Unix
#endif
Merge_Sort ("sorted.fil");
}
AISD wer. 2 str. 84
Algorytm Merge Sort (wersja rekursywna dla pliku):
1.
Otwórz plik wejściowy nieposortowany UF do czytania i pisania, oraz dwa pliki
robocze TMP_F1 i TMP_F2 do pisania.
2.
(Split) Kopiuj po połowie pliku UF do plików TMP_F1 i TMP_F2.
3.
Wywołaj procedurę sortowania dla lewej połówki (TMP_F1).
4.
Wywołaj procedurę sortowania dla prawej połówki (TMP_F2).
5.
(Merge) Kopiuj posortowane dane z TMP_F1 i z TMP_F2 do UF.
6.
Plik jest posortowany rosnąco. Zamknij pliki i usuń robocze.
Algorytm Merge Sort (wersja ze wskazaniem dla tablicy):
Weźmy rekordy danych o postaci:
typedef int KEY_TYPE;
typedef struct DATA {
KEY_TYPE
key;
int
link;
} ARY_LIST[SIZE];
Chcemy posortować tablicę tak, aby wskazanie (link) było indeksem kolejnego większego
elementu. Użyjemy do tego funkcję:
Link_Merge_Sort (A, First, Last, Index_of_lowest_element)
0.
Wszystkie pola link mają wartość -1 (nieistniejący indeks).
1.
Jeśli First >= Last, ustaw Index_of_lowest_element = First i zakończ. W
przeciwnym przypadku wykonaj kroki 2. - 6.
2.
Podziel tablicę na połowy, Middle = (First + Last) / 2 .
3.
Wykonaj algorytm dla lewej połowy
Link_Merge_Sort (A, First, Middle, Left_Begin)
4.
Wykonaj algorytm dla prawej połowy
Link_Merge_Sort (A, Middle+1, Last, Right_Begin)
5.
Połącz dwie podtablice używając Left_Begin i Right_Begin. Przemieszczanie
wartości nie jest konieczne.
6.
Ustaw Index_of_lowest_element na najmniejszy element tablicy A.
Przykład dla:
A[] = {33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
Główne cechy powyższego algorytmu:
1.
Prostota (dzielenie na połowy).
2.
Nie potrzeba dodatkowych podtablic na podział.
3.
Nie wymaga przemieszczania elementów - początkowe pozycje tablicy A pozostają
niezmienione.
4.
A[Index_of_lowest_element] zawiera najmniejszy elemenet. Następna wartość jest
A[A[Index_of_lowest_element].link].
AISD wer. 2 str. 85
Złożoność obliczeniowa Merge Sort dla najgorszego przypadku wynosi O(nlogn). Strategia
podziału jest oparta na dzieleniu na połowy (log
2
n) a łączenie jest liniowe (n).
Sortowanie z pomocą drzewa binarnego (ang. BINARY TREE SORT)
Elementy tablicy (listy) wstawiamy do budowanego drzewa binarnego uporządkowanego ze
względu na wartość kluczy. Następnie przeglądając drzewo kopiujemy elementy do
posortowanej tablicy.
Heap Sort (sortowanie z pomocą sterty)
Sterta jest drzewem binarnym o następujących własnościach:
1.
Jest kompletna, tzn. liście drzewa są na co najwyżej dwóch poziomach i liście na
ostatnim (najniższym) poziomie są umieszane od lewej strony.
2.
Każdy poziom w stercie jest wypełniony od strony lewej do prawej.
3.
Jest częściowo uporządkowana, tzn. wartości kluczy w każdym węźle są w
określonej relacji porządkującej (np. >=, <=) w stosunku do węłów podrzędnych
(dzieci).
Sa trzy główne kategorie stert:
1.
max heap (dzieci <= rodzica)
2.
min heap (dzieci >= rodzica)
3.
min-max heap (poziomy w stercie naprzemiennie spełniają warunki 1. i 2.)
70 (a) Max heap
60 45
35 25 05 12
15 33 07
05 (b) Min heap
07 12
35 15 33 45
70 60 25
05 (c) Min-max heap
70 45
15 07 12 33
60 35 25
Tworzenie sterty (max heap) - przykład.
Zasada sortowania z wykorzystaniem sterty.
Metody obiektu sterty:
Twórz i inicjalizuj stertę.
Buduj stertę (max heap) z elementów tablicy A.
AISD wer. 2 str. 86
Zniszcz stertę (i tablicę A).
Porównuj elementy danych.
Zamień miejscami elementy danych.
Przebuduj stertę (aby zachować jej własności).
Wykonaj sortowanie dla tablicy A z wykorzystaniem sterty.
Drukuj stertę dla każdej iteracji sortowania.
Drukuj stertę.
Sterta często jest przechowywana w tablicy w taki sposób, że korzeń jest umieszczony w
elemencie o indeksie 1, a dzieci każdego węzła o indeksie i mają indeksy 2*i oraz 2*i+1.
#include <iostream.h> // For 'cin' & 'cout'
typedef int DATA_TYPE; // Also the 'key'
class Heap {
DATA_TYPE *heap;
int heap_size;
void Init_Heap (DATA_TYPE A[]);
public:
Heap (int n); // Constructor
~Heap () { delete [] heap; } // Destructor
void ReAdjust_Heap (int Root, int Max_Elem);
void Build_Heap (void);
void Debug_Print (int pass, int reduced_heap_size);
void Heap_Sort (DATA_TYPE A[]);
void Print_Heap (void);
};
Heap::Heap (int n)
{
heap = new DATA_TYPE [n + 1];
heap_size = n;
}
void Heap::Init_Heap (DATA_TYPE A[])
{
for (int i = 1; i <= heap_size; i++)
heap[i] = A[i - 1];
}
void Heap::ReAdjust_Heap (int Root, int Max_Elem)
{
enum BOOLEAN {FALSE, TRUE};
BOOLEAN Finished = FALSE;
DATA_TYPE x = heap[Root];
int j = 2 * Root; // Obtain child information
while ((j <= Max_Elem) && (!Finished)) {
if ((j < Max_Elem) && (heap[j] < heap[j + 1]))
j++;
if (x >= heap[j])
Finished = TRUE;
else {
heap[j/2] = heap[j];
j = 2 * j;
AISD wer. 2 str. 87
}
} // while
heap[j/2] = x;
}
void Heap::Debug_Print (int pass, int reduced_heap_size)
{
cout << " Pass #" << pass << ": ";
for (int i = 1; i <= reduced_heap_size; i++)
cout << heap[i] << " ";
cout << " | ";
for (; i <= heap_size; i++)
cout << heap[i] << " ";
cout << "\n";
}
void Heap::Build_Heap (void)
{
for (int i = heap_size/2; i > 0; i--)
ReAdjust_Heap (i, heap_size);
}
void Heap::Heap_Sort (DATA_TYPE A[])
{
Init_Heap (A);
Build_Heap (); // Build a max heap
for (int i = (heap_size - 1); i > 0; i--) {
int tmp = heap[i + 1]; // swap
heap[i + 1] = heap[1];
heap[1] = tmp;
A[i] = heap[i + 1];
ReAdjust_Heap (1, i); // Rebuild max heap
#ifdef DEBUG
Debug_Print ((heap_size - i), i);
#endif
}
A[0] = heap[1]; // Put last element of heap in A
}
void Heap::Print_Heap (void)
{
cout << "\n ** SORTED IN ASCENDING ORDER USING HEAP SORT"
" **\n";
for (int i = 1; i <= heap_size; i++)
cout << " " << heap[i];
cout << "\n";
}
void main (void)
{
int n;
cout << "\nEnter the number of elements to be sorted: ";
cin >> n;
Heap heap_obj(n);
static DATA_TYPE A[] = {33, 60, 5, 15, 25,
12, 45, 70, 35, 7};
cout << "Unsorted array is: \n";
for (int i = 0; i < n; i++)
cout << A[i] << " ";
cout << "\n\n";
AISD wer. 2 str. 88
heap_obj.Heap_Sort (A);
heap_obj.Print_Heap ();
}
Straight Radix Sort (sortowanie według cyfr)
W systemie liczbowym o podstawie (ang. radix) r jest r cyfr 0, 1, 2, ..., (r-1) i każdą liczbę o
długości n (liczba cyfr) można przedstawić następująco:
k = d
1
d
2
...d
m
d
1
- to MSD (Most Significant Digit)
d
m
- to LSD (Least Significant Digit)
Algorytm dla LSD Radix Sort
1.
Przydziel pamięć na tablicę z sortowanymi danymi.
2.
Utwórz r kolejek, digit_queue[i] zawiera dane, które mają cyfrę i na aktualnie
analizowanej pozycji.
3.
Badaj cyfry danych począwszy od LSD (d
m
) a skończywszy na MSD (d
1
).
Umieszczaj dane w kolejce odpowiadającej wartości cyfry.
4.
(Pętla zewnętrzna). Dla i = 1, 2, ... m, wykonaj kroki 5. i 6.
5.
(Pętla wewnętrzna 1). Dla j = 0, 1, ... (n-1), wykonaj kroki 5.1. i 5.2.
5.1.
Dla A[j] weź cyfrę ostatnią (LSD) w pierwszym kroku (i=1),
przedostatnią w drugim kroku (i=2) itd., aż do cyfry pierwszej (MSD) w
ostatnim kroku (i=m).
5.2.
Wstaw A[j] na koniec kolejki związanej z wartością pobranej cyfry.
6.
(Pętla wewnętrzna 2). Dla qindex = 0, 1, ... (r-1), wpisz zawartości kolejek
digit_queue [qindex] do tablicy A.
Przykład sortowania dla A = {33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
Krok #1
digit_queue[0] 60 70
digit_queue[2] 12
digit_queue[3] 33
digit_queue[5] 5 15 25 45 35
digit_queue[7] 7
A = {60, 70, 12, 33, 5, 15, 25, 45, 35, 7}
Krok #2
digit_queue[0] 5 7
digit_queue[1] 12
digit_queue[2] 25
digit_queue[3] 33 35
digit_queue[4] 45
digit_queue[6] 60
digit_queue[7] 70
A = {5, 7, 12, 15, 25, 33, 35, 45, 60, 70}
AISD wer. 2 str. 89
Złożoność obliczeniowa algorytmu to O(m(n+r)). m zależy od r i od największej (co do
modułu) wartości klucza. Dla tych samych danych różne wartości podstawy liczby dają różne
wydajności.
Radix Exchange Sort (sortowanie według cyfr z wymianą)
Zasada polega na grupowaniu danych według cyfr poczynając od MSD. Potem w grupach
sortujemy wg następnej cyfry itd.
Algorytm dla Binary Exchange Radix Sort
1. Szukaj od prawej danych z kluczem, którego pierwszy bit to 1.
2. Szukaj od lewej danych z kluczem, którego pierwszy bit to 0.
3. Wymień elementy i kontynuuj aż do zrównania wskaźników.
4. W podzielonych zbiorach sortuj rekursywnie wg kolejnego bitu.
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef unsigned DATA_TYPE;
class Sort {
private:
DATA_TYPE *A; // Array list A[]
int n; // size of A
DATA_TYPE extract_bits (unsigned key, int bits, int offset);
void radix_exch_sort1 (int First, int Last, int bitnum);
public:
Sort (int size) { A = new DATA_TYPE[n=size]; }
~Sort() { delete []A; }
void build_list (DATA_TYPE input[]);
void print_ary_list(int first, int last);
void Radix_Exch_Sort (DATA_TYPE input[], int bitnum);
};
typedef DATA_TYPE ARY_LIST[];
void Sort::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Sort::print_ary_list(int first, int last)
{
for (int i = first; i <= last; i++)
printf("%2d ", A[i]);
}
DATA_TYPE Sort::extract_bits (unsigned key, int bits, int offset)
{
return (key >> offset) & ~(~0 << bits);
}
void Sort::radix_exch_sort1 (int First, int Last, int bitnum)
{
DATA_TYPE First_bitval, Last_bitval, swap_area;
if (First < Last && bitnum >= 0) {
int i = First;
AISD wer. 2 str. 90
int j = Last;
while (i != j) { // scanning loop
while (TRUE) {
First_bitval = extract_bits(A[i], 1, bitnum);
if (First_bitval == 0 && i < j)
i += 1;
else break;
}
while (TRUE) {
Last_bitval = extract_bits(A[j], 1, bitnum);
if (Last_bitval != 0 && j > i)
j -= 1;
else break;
}
swap_area = A[j];
A[j] = A[i];
A[i] = swap_area;
} // End of scanning loop
if (extract_bits(A[Last], 1, bitnum) == 0)
j += 1;
printf(" -----------------------------------\n");
printf(" bit = %d | ", bitnum);
print_ary_list (First, j - 1);
printf(" | ");
print_ary_list (j, Last);
printf("\n");
radix_exch_sort1 (First, j - 1, bitnum - 1);
radix_exch_sort1 (j, Last, bitnum - 1);
}
}
void Sort::Radix_Exch_Sort (ARY_LIST input, int bitnum)
{
build_list (input);
printf ("\n List to be sorted %s:\n in ascending order");
print_ary_list (0, n - 1);
printf("\n");
radix_exch_sort1 (0, n - 1, bitnum);
printf ("\n List sorted using %s \n radix exchange sort:");
print_ary_list (0, n - 1);
printf("\n");
}
void main(void)
{
static ARY_LIST A = {33, 60, 5, 15, 25, 12, 45, 70, 35, 7};
Sort radix_srt_obj (10);
printf("\n ** OOP IMPLEMENTATION OF %s",
"RADIX EXCHANGE SORT **");
radix_srt_obj.Radix_Exch_Sort (A, 8);
}
Shell Sort
AISD wer. 2 str. 91
W Shell Sort elementy tablicy wpisujemy do k podtablic (elementy wybierane są z krokiem k),
sortujemy podtablice i kolejno wpisujemy do tablicy pierwsze elementy podtablic, drugie itd.
Następnie zmniejszamy k i powtarzamy algorytm aż k = 1.
Algorytm:
1.
Wybierz wartość kroku k.
2.
Podziel tablicę A na k podtablic tak, aby każda podtablica (j) zawierała elementy o
indeksach j+i*k.
3.
Posortuj wszystkie podtablice (i zapisz do A - de facto te podtablice są zawarte w
A).
4.
Zmniejsz k według jakiejś reguły.
5.
Powtarzaj kroki 2. - 4. aż k = 1.
6.
Tablica jest posortowana.
Przykład
A = [33, 60, 5, 15, 25, 12, 45, 70, 35, 7]
indx: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Krok #1 dla k = 5
1. [33, 12] -> [12, 33]
2. [60, 45] -> [45, 60]
3. [ 5, 70] -> [ 5, 70]
4. [15, 35] -> [15, 35]
5. [25, 7] -> [ 7, 25]
A = [12, 45, 5, 15, 7, 33, 60, 70, 35, 25]
indx: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Krok #2 dla k = 3
1. [12, 15, 60, 25] -> [12, 15, 25, 60]
2. [45, 7, 70] -> [ 7, 45, 70]
3. [ 5, 33, 35] -> [ 5, 33, 35]
A = [12, 7, 5, 15, 45, 33, 25, 60, 70, 35]
indx: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Krok #3 dla k = 1
A = [ 5, 7, 12, 15, 25, 33, 35, 45, 60, 70]
indx: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
#include <stdio.h>
class Sort {
private:
typedef int DATA_TYPE;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
int iter; // iteration
Sort (int size) {iter = 0;A = new DATA_TYPE[n=size];}
~Sort() { delete []A; }
AISD wer. 2 str. 92
void build_list (DATA_TYPE input[]);
void print_list (void);
void Shell_Sort (DATA_TYPE input[]);
};
void Sort::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Sort::print_list (void)
{
for (int i = 0; i < n; i++) {
printf (" %d", A[i]);
if (i != 0 && i % 13 == 0)
printf ("\n"); // break line
}
}
void Sort::Shell_Sort (ARY_LIST input)
{
int i, search,
shell_size = n,
k_sort, k_sort_2, k_sort_1;
build_list (input);
print_list ();
while (shell_size > 1) {
//
// Find value of 'k' to break sort process into
// subarrays by the following rule:
// k_sort = (k sort - 1) * 4 - (k sort - 2) * 3
//
k_sort_2 = 0;
k_sort_1 = 1;
while ((k_sort = k_sort_1 * 4 - k_sort_2 * 3) <
shell_size) {
k_sort_2 = k_sort_1;
k_sort_1 = k_sort;
}
k_sort = k_sort_1;
// Perform insertion sort on 'k' sort subarrays
for (i = 0; i < n; i++) {
DATA_TYPE swap_area = A[i];
search = i - k_sort;
// while (swap_area < A[search] && search >= 0) {
while (search >= 0 && swap_area < A[search]) {
A[search + k_sort] = A[search];
search -= k_sort;
iter++;
}
A[search + k_sort] = swap_area;
}
shell_size = k_sort;
}
}
void main(void)
{
static DATA_TYPE A[]={10, 9, 23, 50, 39, 50, 20, 8, 36, 73, 45, 244, 211, 151,
100, 38, 266, 158, 148, 132, 89, 21, 65, 111, 29, 31, 59,
146, 76, 43, 36, 38, 51, 105, 207, 78, 87, 69};
AISD wer. 2 str. 93
Sort shel_srt_obj (38); // n = 38
printf ("\n ** OOP IMPLEMENTATION %s ** %s",
"OF SHELL SORT **",
"\n\n List to be sorted in ascending order:\n");
shel_srt_obj.Shell_Sort (A);
printf ("\n\n List sorted using Shell sort:\n");
shel_srt_obj.print_list ();
printf ("\n Number of %s sort is %d \n",
"iterations required for",
shel_srt_obj.iter);
}
Złożoność obliczeniowa dla dużych n w najgorszym przypadku wynosi od O(n
1.25
) do
O(1.6n
1.25
) [dane eksperymentalne]. Można tak dobrać sekwencję kroków k, że złożoność
obliczeniowa w najgorszym przypadku wynosi O(n(log
2
n)
2
).
Zlożoność obliczeniowa metod sortowania (najgorsza i najlepsza)
1. Insertion Sort
O(n
2
)
O(n)
2. Selection Sort
O(n
2
)
O(n
2
)
3. Bubble Sort
O(n
2
)
O(n)
4. Quick Sort
O(n
2
)
O(nlog
2
n)
5. Merge Sort
O(nlog
2
n)
O(nlog
2
n)
6. Heap Sort
O(nlog
2
n)
O(nlog
2
n)
7. Straight Radix Sort
O(m(n+r))
8. Shell Sort
O(n(log
2
n)
2
)
Metody wyszukiwania
(A) Proste:
1. Liniowe wyszukiwanie w tablicy.
2. Liniowe wyszukiwanie w liście.
3. Liniowe wyszukiwanie w tablicy uporządkowanej.
4. Liniowe wyszukiwanie w liście uporządkowanej.
(B) Zaawansowane:
1. Binarne wyszukiwanie w tablicy uporządkowanej.
2. Interpolacyjne wyszukiwanie w tablicy uporządkowanej.
3. Wyszukiwanie z podziałem Fibonacciego.
4. Wyszukiwanie w drzewie binarnym
5. Zastosowania funkcji mieszającej (ang. hashing)
class Base_Search {
private:
typedef int DATA_TYPE;
typedef int INDEX;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
AISD wer. 2 str. 94
Search (int size) { A = new DATA_TYPE[n=size]; }
~Search() { delete []A; }
void build_list (DATA_TYPE input[]);
void print_list (char *hdr);
INDEX Linear_Search (DATA_TYPE srch_key);
INDEX Linear_Search_Sorted (DATA_TYPE srch_key);
INDEX Binary_Search (DATA_TYPE srch_key);
INDEX Interpolation_Search (DATA_TYPE srch_key);
INDEX Fibonacci_Search (DATA_TYPE srch_key);
SLLIST_PTR Singly_Linked_List::search_element (SLLIST_PTR lst_ptr,
DATA_TYPE search_key)
BST_PTR Binary_Search_Tree::search_node_in_BST (BST_PTR tree_ptr,
DATA_TYPE Key)
int Hash_Linear_Probe_and_Search(KEY_TYPE srch_key);
CHAIN_PTR Search_Hash_Chain_Node (KEY_TYPE k);
};
Liniowe wyszukiwanie w (nieposortowanej) tablicy
#include <stdio.h>
typedef int DATA_TYPE;
typedef int INDEX;
typedef DATA_TYPE ARY_LIST[];
class Search {
private:
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
Search (int size) { A = new DATA_TYPE[n=size]; }
~Search() { delete []A; }
void build_list (DATA_TYPE input[]);
void print_list (char *hdr);
INDEX Linear_Search (DATA_TYPE srch_key);
};
void Search::build_list (ARY_LIST input)
{
for (int i = 0; i < n; i++)
A[i] = input[i];
}
void Search::print_list (char *hdr)
{
printf("\n %s \n", hdr);
for (int i = 0; i < n; i++)
printf(" %d", A[i]);
printf("\n");
}
INDEX Search::Linear_Search (DATA_TYPE srch_key)
{
int k = 0;
while (k < n) {
if (A[k] == srch_key)
return (k);
k++;
}
printf("\n Linear_Search: %d is not found %s \n",
srch_key, "in the list");
return (-1);
AISD wer. 2 str. 95
}
void main(void)
{
Search seq_srch_obj (10);
static ARY_LIST A = {33, 60, 5, 15, 25, 12, 45, 70, 35, 7 };
printf("\n ** OOP IMPLEMENTATION OF LINEAR %s",
"\n SEARCH IN UNSORTED ARRAY **");
seq_srch_obj.build_list (A);
seq_srch_obj.print_list ("Searching for 45 in array list:");
INDEX i = seq_srch_obj.Linear_Search (45);
if (i != -1)
printf("\n Search data: A[%i] = %d \n", i, A[i]);
}
Liniowe wyszukiwanie w (nieposortowanej) liście
Singly_Linked_List::LIST_PTR
Singly_Linked_List::search_element1 (LIST_PTR lst_ptr, DATA_TYPE search_key)
{
if (!is_sublist_empty(lst_ptr)) {
if (search_key == lst_ptr->data)
return (lst_ptr);
search_element1 (lst_ptr->next, search_key);
}
else {
printf("\n search_element: %s \n",
"Element is not found in list");
return (NULL);
}
}
Liniowe wyszukiwanie w posortowanej tablicy
#include <stdio.h>
class Search {
private:
typedef int DATA_TYPE;
typedef int INDEX;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
Search (int size) { A = new DATA_TYPE[n=size]; }
~Search() { delete []A; }
void build_list (DATA_TYPE input[]);
void print_list (char *hdr);
INDEX Linear_Search_Sorted (DATA_TYPE srch_key);
};
INDEX Search::Linear_Search_Sorted (DATA_TYPE srch_key)
{
int k = 0;
if ((srch_key >= A[0]) && (srch_key <= A[n - 1]))
while (k < n) {
if (A[k] == srch_key)
return (k);
k++;
AISD wer. 2 str. 96
}
printf("\n Linear_Search_Sorted: %d is %s \n",
srch_key, "not found in the list");
return (-1);
}
void main(void)
{
Search seq_srch_srt_obj (10);
static ARY_LIST A = {5, 7, 12, 15, 25, 33, 35, 45, 60, 70};
printf("\n ** OOP IMPLEMENTATION OF LINEAR %s",
"\n SEARCH IN SORTED ARRAY **");
seq_srch_srt_obj.build_list (A);
seq_srch_srt_obj.print_list (
"Searching for 45 in array list:");
INDEX i = seq_srch_srt_obj.Linear_Search_Sorted(75);
if (i != -1)
printf("\n Search data: A[%i] = %d \n", i, A[i]);
}
Złożoność obliczeniowa przeszukiwania liniowego jest O(1) dla najlepszego przypadku, O(n)
dla najgorszego przypadku, średnio O(n/2), czyli O(n).
Binarne wyszukiwanie w posortowanej tablicy
#include <stdio.h>
class Search {
private:
typedef int DATA_TYPE;
typedef int INDEX;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
Search (int size) { A = new DATA_TYPE[n=size]; }
~Search() { delete []A; }
void build_list (DATA_TYPE input[]);
void print_list (char *hdr);
INDEX Binary_Search (DATA_TYPE srch_key);
};
INDEX Search::Binary_Search (DATA_TYPE srch_key)
{
INDEX First = 0,
Last = n - 1,
Middle; // Middle element's index in (sub)array
if ((srch_key < A[0]) || (srch_key > A[n - 1]))
return (-1); // "srch_key" is not found
while (First <= Last) {
Middle = (int) ((First + Last)/2
- (First + Last) % 2); // ?? (RP)
if (srch_key == A[Middle])
return (Middle);
else if (srch_key > A[Middle])
First = Middle + 1;
else // srch_key < A[Middle]
Last = Middle - 1;
AISD wer. 2 str. 97
} // End while (...)
printf("\n Binary_Search: %d is not found %s \n", srch_key, "in the
list");
return (-1);
}
void main(void)
{
Search bin_srch_obj (10);
static ARY_LIST A = {5, 7, 12, 15, 25, 33, 35, 45, 60, 70};
printf("\n ** OOP IMPLEMENTATION OF BINARY %s",
"\n SEARCH IN SORTED ARRAY **");
bin_srch_obj.build_list (A);
bin_srch_obj.print_list ("Searching for 45 in sorted array list:");
INDEX i = bin_srch_obj.Binary_Search (45);
if (i != -1)
printf("\n Search data: A[%i] = %d \n", i,
A[i]);
}
Złożoność obliczeniowa przeszukiwania binarnego wynosi O(log2n) dla najgorszego przypadku.
Wyszukiwanie z podziałem Fibonacciego
Wyszukiwanie z podziałem Fibonacciego jest co do zasady zbliżone do wyszukiwania
binarnego, z tym że podział jest dokonywany wg elementów ciągu Fibonacciego. Na przykład
tablica o rozmiarach 55 jest dzielona na dwie części o 21 i 34 elementach.
#include <stdio.h>
const int NOT_FOUND = -1;
class Search {
private:
typedef int DATA_TYPE;
typedef int INDEX;
typedef DATA_TYPE ARY_LIST[];
DATA_TYPE *A; // Array list A[]
int n; // size of A
public:
Search (int size) { A = new DATA_TYPE[n=size]; }
~Search() { delete []A; }
void build_list (DATA_TYPE input[]);
void print_list (char *hdr);
INDEX Fibonacci_Search (DATA_TYPE srch_key);
};
INDEX Search::Fibonacci_Search (DATA_TYPE srch_key)
{
INDEX Fib_low = 0, Fib_high = 1, offset = 0, location, N = n;
while (Fib_low != 1) {
Fib_low = 0;
Fib_high = 1;
while (offset + (Fib_low += Fib_high) +
(Fib_high += Fib_low) < N - 1) // ?? (RP)
;
location = offset + Fib_low;
if (srch_key == A[location])
return (location);
AISD wer. 2 str. 98
else if (srch_key < A[location])
N = location;
else // srch_key > A[location]
offset = location;
}
while (offset <= N - 1) { // check remainder of A
if (srch_key == A[offset])
return (offset);
++offset;
}
printf("\n Fibonacci_Search: %d is %s \n",
srch_key, "not found in the list");
return (NOT_FOUND);
}
void main(void)
{
Search Fib_srch_obj (10);
static ARY_LIST A = {5, 7, 12, 15, 25, 33, 35, 45, 60, 70};
printf("\n ** OOP IMPLEMENTATION OF FIBONACCI %s",
"\n SEARCH IN SORTED ARRAY **");
Fib_srch_obj.build_list (A);
Fib_srch_obj.print_list (
"Searching for 60 in sorted array list:");
INDEX i = Fib_srch_obj.Fibonacci_Search (45);
if (i != -1)
printf("\n Search data: A[%i] = %d \n", i,A[i]);
}
Wyszukiwanie w (uporządkowanym) drzewie binarnym
Uporządkowanie drzewa binarnego polega na tym, że węzły z mniejszymi kluczami znajdują się
w lewym poddrzewie, a z większymi - w prawym.
Binary_Search_Tree::TREE_PTR
Binary_Search_Tree::search_node_in_BST (TREE_PTR tree_ptr, DATA_TYPE Key)
{
if (tree_ptr != NULL) {
if (Key == tree_ptr->data)
return (tree_ptr);
else if (Key < tree_ptr->data)
search_node_in_BST(tree_ptr->left_childptr, Key);
else // (Key > tree_ptr->data)
search_node_in_BST(tree_ptr->right_childptr, Key);
}
else {
printf("\n search_node_in_BST: Node %d %s \n",
Key, "is not found");
return (NULL);
}
}
void Binary_Search_Tree::search_node(DATA_TYPE srch_key)
{
TREE_PTR srch_ptr = NULL;
srch_ptr = search_node_in_BST(root_ptr, srch_key);
if (srch_ptr != NULL)
printf("\n\n Node: %d is found in the BST\n",
srch_ptr->data);
AISD wer. 2 str. 99
}
Zastosowania funkcji mieszającej (ang. hashing)
Wyszukiwanie danych z wykorzystaniem funkcji mieszającej (ang. hashing function) wymaga
stosowania odpowiednich struktur danych tzw. tablic podziału z porcjami (ang. hash table with
buckets) lub z listami (ang. hash table with linked lists (chains)).
Strategia funkcji mieszającej polega na takim skonstruowaniu struktur danych, w którym
możliwy jest dostęp swobodny. Element przechowywany w tablicy podziału musi posiadać
klucz, według którego jest w tej tablicy wyszukiwany (i składowany).
Tablica podziału ma pewną liczbę porcji (ang. bucket), np. HT_SIZE. Wtedy mamy
hash_table[0], hash_table[1], ... , hash_table[HT_SIZE-1]. Każda porcja zawiera p pozycji (ang.
slot), z których każda może przechowywać daną (ang. record).
Wyróżnia się dwa typy tablic podziału:
1. Tablice podziału z porcjami
2. Tablice podziału z listami (łańcuchami)
Metody stosowane dla tablicy podziału
Skonstruuj tablicę podziału.
Usuń tablicę podziału.
Wstaw daną z kluczem do tablicy podziału.
Wyszukaj daną z kluczem w tablicy podziału.
Usuń daną z kluczem z tablicy podziału.
Drukuj daną z kluczem z tablicy podziału.
Aby zrealizować powyższe metody musi istnieć funkcja odwzorowująca klucz danej na adres w
tablicy podziału i jest to właśnie funkcja mieszająca (ang. hashing function). W wyniku
stosowania funkcji mieszającej dostaje się adres porcji i tam na odpowiedniej pozycji
wykonujemy operację na danej.
Funkcje mieszające
1.
Funkcja modulo dla liczb całkowitych
typedef unsigned HASH_VALUE;
typedef unsigned KEY_TYPE;
HASH_VALUE Modulus_Hash_Func (KEY_TYPE key)
{
return (key % HT_SIZE)
}
Zalecanym rozmiarem tablicy podziału jest liczba pierwsza wyrażona wzorem (4i+3). Na
przykład dla liczb z zakresu 0 .. 999 dobrym rozmiarem tablicy podziału jest 127 ( = 4*31 + 3 ).
AISD wer. 2 str. 100
2.
Funkcja modulo dla danych (np. ciągów znaków) reprezentowanych przez
wskaźnik
HASH_VALUE Mod_Ptr_Hash_Func (KEY_TYPE *key)
{
return ( ((unsigned) key) % 0xFF)
}
Funkcje mieszające wykorzystujące operator modulo są dość efektywne. Dla niewielkiego
zbioru liczb całkowitych wystarczy wybieranie ustalonej cyfry jako rezultatu funkcji
mieszającej.
3.
Łamanie liczb całkowitych (ang. Folding Hash Function)
Łamanie liczb całkowitych polega na wybraniu kilku najbardziej znaczących cyfr i kilku
najmniej znaczących cyfr klucza oraz wykonaniu na nich jakiejś operacji. Metoda ta dobrze
(równomiernie) rozrzuca liczby w tablicy podziału.
typedef unsigned long KEY_TYPE;
HASH_VALUE Fold_Integer_Hash (KEY_TYPE key)
{
return ( (key / 10000 + key % 10000) % HT_SIZE)
}
WeŸmy key = 87629426 i HT_SIZE = 251
(87629426 / 10000 + 87629426 % 10000 ) % 251 =
(8762 + 9426) % 251 = 116
4.
Łamanie dla ciągu znaków
HASH_VALUE Fold_String_Hash (char *key)
{
unsigned sum_ascii_value = 0;
while ( *key != '\0' ) {
sum_ascii_value += *key++;
return (sum_ascii_key % HT_SIZE);
5.
Operacje bitowe
W trakcie umieszczania danych w tablicach podziału może dochodzić do kolizji, gdy dla
różnych danych generowane są takie same adresy. Jeśli w porcji jest kilka pozycji, to są one
zapełniane kolejno. W przypadku listy do porcji dołączany jest kolejno wprowadzany element.
Dla porcji o 1 pozycji rozwiązywanie kolizji może polegać na obliczaniu kolejnego adresu, aż
do wyczerpania wszystkich możliwości.
Liniowe przeszukiwanie (liniowe badanie) (ang. linear search method, linear probing, linear
open addressing) polega na wyliczaniu kolejnego indeksu w cyklicznej tablicy podziału.
circular index = (circular index + wartość f. mieszającej) % (rozmiar tablicy podziału)
AISD wer. 2 str. 101
#include <stdio.h>
const int Empty = ' ';
typedef unsigned KEY_TYPE;
typedef unsigned HASH_VALUE;
typedef unsigned HASH_INDEX;
typedef char DATA_TYPE;
class Hash_Single_Bucket {
private:
typedef struct DATA_RECORD {
DATA_TYPE data;
KEY_TYPE key;
} SINGLE_SLOT_BUCKET;
// SINGLE_SLOT_BUCKET circ_hash_table[HT_SIZE];
int HT_SIZE;
SINGLE_SLOT_BUCKET *circ_hash_table;
void Init_Hash_Tab (void);
public:
Hash_Single_Bucket(int table_size);
~Hash_Single_Bucket();
HASH_VALUE Hash_Function (KEY_TYPE key);
int Hash_Linear_Probe_and_Search (KEY_TYPE srch_key);
void Insert_Hash_Bucket(KEY_TYPE new_key, DATA_TYPE new_data);
void Build_Single_Bucket_Hash_Table (void);
void Print_Hash_Table(void);
};
Hash_Single_Bucket::Hash_Single_Bucket(int table_size)
{
HT_SIZE = table_size;
circ_hash_table = new SINGLE_SLOT_BUCKET[HT_SIZE];
Init_Hash_Tab();
}
Hash_Single_Bucket::~Hash_Single_Bucket()
{
delete []circ_hash_table;
}
void Hash_Single_Bucket::Init_Hash_Tab (void)
{
for (int i = 0; i < HT_SIZE; i++) {
circ_hash_table[i].key = Empty;
circ_hash_table[i].data = Empty;
}
}
HASH_VALUE Hash_Single_Bucket::Hash_Function (KEY_TYPE key)
{
return (key % HT_SIZE);
}
int Hash_Single_Bucket::Hash_Linear_Probe_and_Search
(KEY_TYPE srch_key)
{
int hashed_value = Hash_Function (srch_key);
int circular_index = hashed_value;
AISD wer. 2 str. 102
while ((circ_hash_table[circular_index].key != Empty) &&
(circ_hash_table[circular_index].key == srch_key)) {
circular_index = (circular_index + hashed_value) % HT_SIZE;
if (circular_index == hashed_value) {
printf("\n Hash_Linear_Probe_and_Search: %s \n",
"Full Hash Table");
return (-1); // Return an out of range value
}
}
return (circular_index);
} // -- End of Hash_Linear_Probe_and_Search() --
void Hash_Single_Bucket::Insert_Hash_Bucket
(KEY_TYPE new_key, DATA_TYPE new_data)
{
int hash_index;
hash_index = Hash_Linear_Probe_and_Search(new_key);
if (hash_index != -1) {
circ_hash_table[hash_index].data = new_data;
circ_hash_table[hash_index].key = new_key;
}
}
void Hash_Single_Bucket::Build_Single_Bucket_Hash_Table (void)
{
Insert_Hash_Bucket (23, 'P');
Insert_Hash_Bucket (12, 'R');
Insert_Hash_Bucket (25, 'A');
Insert_Hash_Bucket (28, 'T');
Insert_Hash_Bucket (99, 'I');
Insert_Hash_Bucket (11, 'V');
Insert_Hash_Bucket (12, 'A');
}
void Hash_Single_Bucket::Print_Hash_Table(void)
{
printf ("\n OOP IMPLEMENTATION OF");
printf ("\n Hash Table with %s \n",
"Single-Slot Buckets");
for (int i = 0; i < HT_SIZE; i++)
printf ("\n Hash_Tabl[%d] = %c", i,
circ_hash_table[i].data);
}
void main ()
{
Hash_Single_Bucket ht_bucket_obj(10);
ht_bucket_obj.Build_Single_Bucket_Hash_Table();
ht_bucket_obj.Print_Hash_Table();
printf ("\n");
}
Rozwiązywanie kolizji w tablicach podziału z porcjami o kilku pozycjach.
Analiza wprowadzania i wyszukiwania elementów w tablicy podziału z listami (łańcuchami).
#include <stdio.h>
class Hash_Chain {
private:
AISD wer. 2 str. 103
typedef char DATA_TYPE;
typedef unsigned short KEY_TYPE;
typedef unsigned HASH_VALUE;
typedef struct CHAIN_ELEMENT {
KEY_TYPE key;
DATA_TYPE data;
CHAIN_ELEMENT *next;
CHAIN_ELEMENT *prev;
} *CHAIN_PTR;
int HT_SIZE; // Hash Table Size
CHAIN_ELEMENT **hash_table;
void Init_Hash_Chain (void);
public:
Hash_Chain(int table_size);
~Hash_Chain();
HASH_VALUE Hash_Function (KEY_TYPE key);
CHAIN_PTR Create_Chain_Node (KEY_TYPE k, DATA_TYPE new_data);
void Insert_Hash_Chain_Node (KEY_TYPE k, DATA_TYPE new_data);
void Create_Chained_Hash_Table (void);
void Delete_Hash_Chain_Node (KEY_TYPE k);
CHAIN_PTR Search_Hash_Chain_Node (KEY_TYPE k);
void Retrieve_Hash_Chain_Node (KEY_TYPE k);
};
typedef Hash_Chain::CHAIN_ELEMENT *CHAIN_PTR;
Hash_Chain::Hash_Chain (int table_size)
{
HT_SIZE = table_size;
hash_table = new CHAIN_PTR[HT_SIZE];
Init_Hash_Chain();
}
Hash_Chain::~Hash_Chain()
{
HASH_VALUE chain_index;
CHAIN_PTR chain_head_ptr, next_ptr;
for (chain_index = 0; chain_index < HT_SIZE; chain_index++){
chain_head_ptr = hash_table[chain_index];
while (chain_head_ptr != NULL) {
next_ptr = chain_head_ptr->next;
delete chain_head_ptr;
chain_head_ptr = next_ptr;
}
}
delete [HT_SIZE] hash_table;
}
Hash_Chain::HASH_VALUE Hash_Chain::Hash_Function(KEY_TYPE key)
{
return (key % HT_SIZE);
}
Hash_Chain::CHAIN_PTR Hash_Chain::Create_Chain_Node
(KEY_TYPE new_key, DATA_TYPE new_data)
{
CHAIN_PTR new_ptr = new CHAIN_ELEMENT;
if (new_ptr != NULL) {
new_ptr->key = new_key;
new_ptr->data = new_data;
AISD wer. 2 str. 104
new_ptr->next = NULL;
new_ptr->prev = NULL;
}
return (new_ptr);
}
void Hash_Chain::Init_Hash_Chain (void)
{
int j = HT_SIZE - 1;
while (j >= 0) {
hash_table[j] = NULL;
j--;
}
}
void Hash_Chain::Insert_Hash_Chain_Node (KEY_TYPE new_key,
DATA_TYPE new_data)
{
CHAIN_PTR chain_head_ptr, new_ptr;
HASH_VALUE hash_chain_no = Hash_Function (new_key);
chain_head_ptr = hash_table[hash_chain_no];
new_ptr = Create_Chain_Node (new_key, new_data);
if (new_ptr == NULL) {
printf("\n Insert_Hash_Chain_Node: Out of memory\n");
exit (-1);
}
if (chain_head_ptr != NULL)
new_ptr->next = chain_head_ptr;
hash_table[hash_chain_no] = new_ptr;
} // -- End of Insert_Hash_Chain_Node() --
void Hash_Chain::Delete_Hash_Chain_Node (KEY_TYPE k)
{
CHAIN_PTR chain_head_ptr, srch_ptr;
srch_ptr = Search_Hash_Chain_Node (k);
if (srch_ptr == NULL) // not found
return;
HASH_VALUE hash_chain_no = Hash_Function (k);
chain_head_ptr = hash_table[hash_chain_no];
if (srch_ptr == chain_head_ptr) {
hash_table[hash_chain_no] = chain_head_ptr->next;
delete chain_head_ptr;
return;
}
srch_ptr->prev->next = srch_ptr->next;
delete srch_ptr;
} // -- End of Delete_Hash_Chain_Node() --
Hash_Chain::CHAIN_PTR Hash_Chain::Search_Hash_Chain_Node
(KEY_TYPE srch_key)
{
CHAIN_PTR chain_head_ptr;
HASH_VALUE hash_chain_no = Hash_Function (srch_key);
chain_head_ptr = hash_table[hash_chain_no];
if (chain_head_ptr == NULL) {
printf("\n Search_Hash_Chain_Node: Empty chain.\n");
return (NULL);
}
while (chain_head_ptr != NULL) {
if (chain_head_ptr->key == srch_key)
return (chain_head_ptr);
else
AISD wer. 2 str. 105
chain_head_ptr = chain_head_ptr->next;
}
printf("\n %s %u \n is not found in the %s \n",
"Search_Hash_Chain_Node: Element with key",
srch_key, "chained hash table.");
return (NULL);
} // -- End of Search_Hash_Chain_Node() --
void Hash_Chain::Create_Chained_Hash_Table (void)
{
Insert_Hash_Chain_Node (23, 'P');
Insert_Hash_Chain_Node (12, 'R');
Insert_Hash_Chain_Node (25, 'A');
Insert_Hash_Chain_Node (28, 'T');
Insert_Hash_Chain_Node (99, 'I');
Insert_Hash_Chain_Node (11, 'V');
Insert_Hash_Chain_Node (12, 'A');
}
void Hash_Chain::Retrieve_Hash_Chain_Node (KEY_TYPE k)
{
CHAIN_PTR srch_ptr;
if ((srch_ptr = Search_Hash_Chain_Node (k)) != NULL) {
printf("\n Hash chain search succeeds.");
printf("\n Element's key = %u", srch_ptr->key);
printf("\n Element's data = %c \n", srch_ptr->data);
}
}
void main(void)
{
Hash_Chain hc_obj(5);
printf("\n ** HASH SEARCH IN A HASH %s **",
"CHAINING STRATEGY");
hc_obj.Create_Chained_Hash_Table();
hc_obj.Retrieve_Hash_Chain_Node (12);
hc_obj.Retrieve_Hash_Chain_Node (44);
hc_obj.Delete_Hash_Chain_Node (28);
hc_obj.Retrieve_Hash_Chain_Node (28);
hc_obj.Retrieve_Hash_Chain_Node (11);
}
Kryteria wyboru metod wyszukiwania, sortowania oraz złożoność obliczeniowa dla tych metod.