Рубрики
Без рубрики

Сортировка слиянием и быстрая сортировка!

В этой статье я подробно объясню два алгоритма сортировки: сортировку слиянием и быструю сортировку… С пометкой алгоритмы, java, новички, программирование.

В этой статье я собираюсь объяснить два алгоритма сортировки, Сортировка слиянием и Быстрая сортировка с подробным анализом, применением и пространственной и временной сложностью.

Прежде чем приступить к теме, давайте узнаем об основных и других алгоритмах сортировки.

Некоторые алгоритмы сортировки являются

  • Сортировка пузырьков

Легко внедряется и легко понимается. Но не эффективная сортировка, она требует O (N ^ 2) временной сложности и O (1) пространства. Означает, что это алгоритм сортировки на месте.(На каждой итерации самый большой элемент занимает правильное положение, и за одну итерацию мы должны выполнить большее количество свопов).

  • Сортировка выборки Меньшее количество свопов по сравнению с пузырьковой сортировкой. Но все равно неэффективно. Это действующий и неспособный алгоритм сортировки с O (N ^ 2) временной сложностью.

  • Сортировка вставки Это также требует O (N ^ 2) временной сложности, но интересная часть этого алгоритма сортировки заключается в том, что для частичной сортировки элементов требуется всего O (N). На месте и стабильная сортировка, алгоритм.

  • Сортировка кучи Это нестабильная сортировка с O(NlogN) временем и O(1) пространственной сложностью.

  • Подсчет Сортировка

Это стабильный алгоритм сортировки с временной сложностью O (N + K), где n – количество элементов в массиве, а k – диапазон элементов. Подсчетная сортировка наиболее эффективна, если диапазон входных значений не превышает количество сортируемых значений. Пространство O(N + K). обр. = [3, 2, 4, 1, 2] здесь – диапазон ввода(N) < количество элементов(K) Если диапазон больше, то его использование будет неэффективным.

Теперь пришло время рассказать о слиянии и быстрой сортировке…

Сортировка слиянием

Он основан на методе “Разделяй и властвуй” с наихудшей временной сложностью O (NlogN), это один из наиболее подходящих алгоритмов.

Сортировка слиянием сначала делит массив на равные половины, а затем объединяет их в отсортированном виде.

Алгоритм

Step 1: If only one element in the list, return it.
Step 2: Divide the list recursively into two halves until it can no more divided.
Step 3: Merge the smaller lists into new lists in sorted order(start comparing the elements from two halves of the list, and choose smaller element each time between them and store it into another list(extra space))

Передать копию исходного массива

import java.util.*;

class Solution {
    public int[] merge_sort(int[] input) {
        if (input.length <= 1) {
            return input;
        }
        int pivot = input.length / 2;
        int[] left_list = merge_sort(Arrays.copyOfRange(input, 0, pivot));
        int[] right_list = merge_sort(Arrays.copyOfRange(input, pivot, input.length));
        return merge(left_list, right_list);
    }

    public int[] merge(int[] left_list, int[] right_list) {
        int[] ret = new int[left_list.length + right_list.length];
        int left_cursor = 0, right_cursor = 0, ret_cursor = 0;

        while (left_cursor < left_list.length && right_cursor < right_list.length) {
            if (left_list[left_cursor] < right_list[right_cursor]) {
                ret[ret_cursor++] = left_list[left_cursor++];
            } else {
                ret[ret_cursor++] = right_list[right_cursor++];
            }
        }
        // append what is remain the above lists
        while (left_cursor < left_list.length) {
            ret[ret_cursor++] = left_list[left_cursor++];
        }
        while (right_cursor < right_list.length) {
            ret[ret_cursor++] = right_list[right_cursor++];
        }
        return ret;
    }
}

class MergeSort {
    public static void main(String args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        // call merge sort function
        arr = merge_sort(arr);
        System.out.print(arr);
    }
}

На месте

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 2, 0, 1, 3};
        mergeSortInPlace(arr, 0, arr.length - 1);
        for (int a : arr)
            System.out.print(a + " ");
    }

    static void mergeSortInPlace(int[] arr, int start, int end) {

        if (start < end) {
            int mid = start + (end - start) / 2;

            mergeSortInPlace(arr, start, mid);
            mergeSortInPlace(arr, mid + 1, end);
            merge(arr, mid, start, end);
        }
    }

    static void merge(int[] arr, int mid, int start, int end) {

        int l = start, r = mid + 1, i = 0;

        int[] mix = new int[end - start + 1];
        while (l <= mid && r <= end) {
            if (arr[l] <= arr[r]) {
                mix[i++] = arr[l];
                l++;
            } else {
                mix[i++] = arr[r];
                r++;
            }
        }
        while (l <= mid) {
            mix[i++] = arr[l++];
        }

        while (r <= end) {
            mix[i++] = arr[r++];
        }

        for (int k = 0; k < mix.length; k++) {
            arr[start + k] = mix[k];
        }

    }
}

Сухой ход

плюсы и минусы

Плюсы

  • Список большого размера, объединенный этой сортировкой.
  • Также используется в связанном списке.
  • Внешняя сортировка
  • Стабильный
  • Экономия времени O(NlogN)

Аферы

  • Это занимает дополнительное пространство Требуется место в стеке (рекурсивный) журнал и дополнительное пространство N. O(N +(N)
  • Не очень эффективно для небольшой проблемы

Быстрая сортировка

Быстрая сортировка использует алгоритм разбиения для поиска сводного элемента и рекурсивного разделения массива на две половины.

Идея этого алгоритма заключается в том, что он аналогичен сортировке слиянием, но не занимает дополнительного места. Здесь поворотный элемент играет важную роль.

Что такое поворотный элемент?

  • выберите ось вращения в качестве 1-го элемента
  • выберите ось вращения в качестве 2-го элемента
  • выберите стержень в качестве среднего элемента (лучший способ)
  • выберите pivot в качестве случайного элемента (лучший способ)

Логика:

Предположим, что arr = [5, 3, 1, 2, 4] Шаг 1: Выберите элемент pivot (выбрал pivot как случайный, поэтому) Шаг 2: За один проход мы обнаруживаем, что ось поворота находится в правильном положении, это означает, что все элементы, которые меньше оси поворота, расположены слева, а все элементы, которые больше оси поворота, расположены справа. (для этого применяется некоторая логика) Теперь массив является: 2, 1, 3, 5, 4

Возьмите стержень в качестве конечного элемента

public class QuickSort {
    public static void quickSort(int [] nums, int start, int end) {
        if (start <  end) {
            int partitionIndex = partition(nums, start, end);
            quickSort(nums, start, partitionIndex - 1);
            quickSort(nums, partitionIndex + 1, end);
        }
    }

    public static int partition(int [] nums, int start, int end) {
        int pivot = nums[end];
        int partitionIndex = start;
        for (int i=start; i

Возьмите стержень в качестве среднего элемента

package com.example.helloworld;

public class QuickSort {
    public static void quickSort(int [] nums, int start, int end) {
       if(start >= end)return;
       int left = start, right = end;
       int mid = start + (end - start) / 2;
       int pivot = nums[mid];
       while(left <= right){

           while(nums[left] < pivot)left++;
           while(nums[right] > pivot)right--;

           if(left <= right) {
               swap(nums, left, right);
               left++;
               right--;
           }
       }
      //now my pivot at its correct position so, apply same for the two halves recursively!
       quickSort(nums, start, right);
       quickSort(nums, left, end);
    }

    public static void swap(int [] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String [] args) {
        int [] nums = {5, 3, 2, 12, 100, 11, 1, 5, 6, 7,83, 4, 45, 56, 7, 4, 3,1};
        quickSort(nums, 0, nums.length - 1);
        for (int number : nums) {
            System.out.print(number + " ");
        }
    }
}

Полезная ссылка

Надеюсь, это поможет, пожалуйста, поделитесь своими мыслями в комментариях ☺️

Оригинал: “https://dev.to/suchitra_13/merge-sort-and-quick-sort-icn”