Wprowadzenie do algorytmów sortowania korespondencji seryjnej w Javie
Algorytmy sortowania korespondencji seryjnej są bardzo ważne w informatyce. Wynikiem sortowania jest ułożenie elementów listy w określonej kolejności (rosnąco lub malejąco). Sortowanie korespondencji seryjnej jest jednym z najbardziej wydajnych dostępnych algorytmów sortowania, ponieważ opiera się na koncepcji dzielenia i zdobywania. Jak sama nazwa wskazuje, najpierw podziel większy problem na małe problemy niż rozwiąż mniejsze problemy, aby rozwiązać większy problem. W tym artykule omówimy algorytmy sortowania korespondencji seryjnej w Javie. Pod względem koncepcyjnym sortowanie metodą scalania jest kombinacją dwóch podstawowych algorytmów o nazwie MERGE i MERGE_SORT, która działa w następujący sposób:
- Podziel nieposortowaną listę na n list podrzędnych zawierających pojedyncze elementy (n to całkowita liczba elementów na nieposortowanej liście).
- Wielokrotnie łącz podlisty w posortowane listy podrzędne, aż pojawi się tylko jedna posortowana lista.
Implementacja algorytmów sortowania korespondencji seryjnej w Javie
Algorytm MERGE to procedura łączenia dwóch posortowanych list w jedną posortowaną listę.
Przykład: Załóżmy, że istnieją dwie listy, tj. Lista 1 (6, 3) i Lista 2 (3, 1, 9).
1. Najpierw posortuj obie listy.
Lista 1
Lista 2
Teraz zastosujemy do tego technikę łączenia.
- Następnie utworzymy nową listę o rozmiarze m + n, gdzie m jest liczbą elementów na liście 1, a n jest liczbą elementów na liście 2.
Lista 3
W naszym przypadku m = 2 i n = 3, więc m + n = 5.
- Teraz mamy dwa wskaźniki. Pierwszy wskaźnik wskazujący na pierwszą pozycję Listy 1 i Drugi wskaźnik wskazujący na pierwszej pozycji Listy 2.
4. Następnie porównamy wartość obu wskaźników. Wskaźnik o mniejszej wartości, skopiuj ten element do listy 3 i przesuń wskaźnik na prawo od listy o mniejszej wartości i wynikowej liście (tj. Liście 1 i liście 3).
5. Podobnie, wykonaj krok 4 raz za razem.
Dalsze przechodzenie…
UWAGA: Jeśli jedna z list (tj. Lista 1 lub lista 2) zostanie w pełni przemierzona, jak w powyższym przypadku, skopiuj całą zawartość innych list ze wskaźnika do listy wyników (tj. Listy 3) w następujący sposób.
Algorytm i pseudokod
Dwa algorytmy używane w algorytmie scalania to:
- MERGE (ARR, F, M, L) to proces, który zakłada, że:
- ARR (F… .M) i ARR (M + 1… .L) to posortowane listy.
- Łączy dwie posortowane listy podrzędne w jeden ARR (F… .L).
- SORT (ARR (), F, L) // tutaj F jest pierwszym, a L jest ostatnim indeksem tablicy.
Jeżeli (L> 1)
- Znajdź środkowy punkt, aby podzielić listę na dwie połowy:
środkowy M = (F + L) / 2
- Call Merge Sort dla pierwszej połowy:
Zadzwoń do SORT (ARR, 1, M)
- Call Merge Sort dla drugiej połowy:
Zadzwoń do SORT (ARR, M + 1, L)
- Scal połówki posortowane w kroku 2 i 3:
Zadzwoń do MERGE (ARR, L, M, R)
Przykład
Weźmy przykład tablicy ARR (10, 6, 8, 5, 7, 3, 4). Użyjemy algorytmu scalania do sortowania tablicy za pomocą jej techniki dzielenia i podbijania. Widzimy poniższy rysunek, że tablica jest rekurencyjnie dzielona na dwie połowy, aż rozmiar osiągnie 1. Gdy rozmiar osiągnie 1, wówczas wywołujemy procesy scalania i rozpoczynamy scalanie list z powrotem, aż cała lista zostanie scalona.
UWAGA: Na poniższym rysunku liczby w kolorze czerwonym wskazują kolejność przetwarzania kroków w celu utworzenia tablicy sortowanej.
Kod programu:
import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)
Wynik:
Wniosek - Scal sortowanie algorytmów w Javie
Scal sortowanie najlepiej, najgorszy i średni czas trwania sprawy są takie same, co czyni go bardziej wydajnym algorytmem. Działa szybciej niż inne techniki sortowania. Sortowanie według scalania można zastosować do plików o dowolnym rozmiarze. Jest wysoce paralelny dzięki zastosowaniu metody dziel i zwyciężaj. Aby rozwinąć solidne podstawy informatyki, zaleca się dokładne zrozumienie różnych algorytmów sortowania.
Polecane artykuły
Jest to przewodnik po scalaniu algorytmów sortowania w Javie. Tutaj omawiamy przykład implementacji algorytmów sortowania korespondencji seryjnej w Javie oraz algorytmu i pseudokodu. Możesz także przejrzeć nasze inne sugerowane artykuły -
- Sortuj zaznaczenia w Javie
- Instrukcja Case w Javie
- Dostęp do modyfikatorów w Javie
- Scal sortowanie w JavaScript
- Co to jest instrukcja Case w JavaScript?
- Dostęp do modyfikatorów w PHP
- Algorytmy szybkiego sortowania w Javie
- Kompletny przewodnik po sortowaniu w C # z przykładami
- Funkcja sortowania w Pythonie z przykładami
- Top 6 algorytm sortowania w JavaScript