Алгоритмы сортировки слиянием в Java - Реализация сортировки слиянием

• Введение в алгоритмы сортировки слиянием в Java

Введение в алгоритмы сортировки слиянием в Java

Алгоритмы сортировки слиянием очень важны в информатике. Результатом сортировки является упорядочение элементов списка в определенном порядке (по возрастанию или по убыванию). Сортировка слиянием является одним из наиболее эффективных алгоритмов сортировки, поскольку она основана на концепции разделяй и властвуй. Как следует из названия, сначала разделите большую проблему на маленькие проблемы, чем решайте меньшие проблемы, чтобы решить большую проблему. В этой статье мы обсудим алгоритмы сортировки слиянием в Java. Концептуально сортировка слиянием представляет собой комбинацию двух основных алгоритмов, называемых MERGE и MERGE_SORT, которая работает следующим образом:

1. Разделите несортированный список на n номеров одноэлементных подсписков (n - общее количество элементов в несортированном списке).
2. Повторно объединяйте подсписки в отсортированные подсписки, пока не будет только один отсортированный список.

Реализация алгоритмов сортировки слиянием в Java

Алгоритм MERGE - это процедура объединения двух отсортированных списков в один отсортированный список.

Пример: предположим, что есть два списка, то есть Список 1 (6, 3) и Список 2 (3, 1, 9).

1. Сначала отсортируйте оба списка.

Список 1

Список 2

Теперь мы применим метод слияния.

2. Затем мы создадим новый список размером m + n, где m - количество элементов в списке 1, а n - количество элементов в списке 2.

Список 3

В нашем случае m = 2 и n = 3, поэтому m + n = 5.

3. Теперь у нас есть два указателя. Первый указатель, указывающий на первую позицию списка 1, и второй указатель, указывающий на первую позицию списка 2.

4. Затем мы сравним значение обоих указателей. Указатель с меньшим значением скопируйте этот элемент в Список 3 и переместите указатель вправо от списка с меньшим значением и результирующим списком (т.е. Списком 1 и Списком 3).

5. Аналогично, повторите шаг 4 снова и снова.

Дальнейшее прохождение …

ПРИМЕЧАНИЕ. Если один из списков (т. Е. Список 1 или список 2) будет полностью пройден, как в приведенном выше случае, скопируйте все содержимое других списков из указателя в список результатов (т.е. список 3) следующим образом.

Алгоритм и псевдокод

Два алгоритма, используемые в алгоритме слияния:

• MERGE (ARR, F, M, L) - это процесс, который предполагает следующее:

1. ARR (F… .M) и ARR (M + 1… .L) - отсортированные списки.
2. Объединяет два отсортированных подсписка в одну ARR (F… .L).

• SORT (ARR (), F, L) // здесь F - первый, а L - последний индекс массива.

Если (L> 1)

1. Найдите среднюю точку, чтобы разделить список на две половины:

средний M = (F + L) / 2

2. Вызов сортировки слиянием для первой половины:

Call SORT (ARR, 1, M)

3. Вызов сортировки слиянием для второй половины:

Call SORT (ARR, M + 1, L)

4. Объедините половинки, отсортированные на шаге 2 и 3:

Вызов MERGE (ARR, L, M, R)

пример

Давайте возьмем пример массива ARR (10, 6, 8, 5, 7, 3, 4). Мы будем использовать алгоритм слияния для сортировки массива с использованием его техники разделения и завоевания. На рисунке ниже видно, что массив рекурсивно делится на две половины, пока размер не станет равным 1. Как только размер станет равным 1, мы вызываем процессы слияния и начинаем слияние списков до слияния полного списка.

ПРИМЕЧАНИЕ. На приведенном ниже рисунке цифры красного цвета обозначают порядок обработки шагов для формирования отсортированного массива.

Код программы:

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);
)
)

Выход:

Заключение - Алгоритмы сортировки слиянием в Java

Сложность сортировки по наилучшему, худшему и среднему времени одинакова, что делает его более эффективным алгоритмом. Это работает быстрее, чем другие методы сортировки. Сортировка слиянием может применяться к файлам любого размера. Это очень распараллеливается благодаря использованию метода «разделяй и властвуй». Для того, чтобы развить прочные основы в информатике, советуем вам хорошо разбираться в различных алгоритмах сортировки.

Рекомендуемые статьи

Это руководство по алгоритмам сортировки слиянием в Java. Здесь мы обсуждаем реализацию алгоритмов сортировки слиянием в Java и Algorithm & Pseudocode с примером. Вы также можете просмотреть наши другие предлагаемые статьи -

1. Выбор сортировки в Java
2. Положение в Java
3. Модификаторы доступа в Java
4. Объединить Сортировать в JavaScript
5. Что такое Case Case в JavaScript?
6. Модификаторы доступа в PHP
7. Алгоритмы быстрой сортировки в Java
8. Полное руководство по сортировке в C # с примерами
9. Функция сортировки в Python с примерами
10. Топ 6 Алгоритм сортировки в JavaScript